Informatyka UJ forum

Spectro

[link widoczny dla zalogowanych]

W tym tygodniu rządzą spójne składowe :P .

Rogal

To już zadanie O? Jeszcze trochę i wyczerpiemy alfabet :shock:

Ale zawsze zostają jeszcze literki greckie, cyrylica, ew. jakieś znaczki chińsko - japońskie 8)

+1 :twisted: :lol:

Żeby nie było, że OT... Na początku się przeraziłem z tym Sokobanem. Ale jak się wykorzysta te spójnie silne składowe(czy coś takiego 8) ) to chyba będzie całkiem proste.

kap00ch

po samym przeczytaniu to ja tu za bardzo nie wiem po co silne skladowe spojne (czy inne :P). Po prostu bym stworzyl ladna nav-mape a potem zapuszczal Dijkstre ze sprawdzaniem zakretow az do momentu kiedy przejdzie albo droga zostanie zablokowana ;] proste szybkie i skuteczne...no ale oni chca jakies sss :D

kap00ch

ludzie dobrej woli...prosbe mam...mianowicie od przeszlo 1 dnia nic nie robie tylko siedzie i klepie se szachownice do sokobana :P i poki co po 100 najbardiej kur#$%# testach na jakie wpadlem ciagle mam dobre wyniki a athina pyk i w pierwszej sek daje mi juz ANS;/ sam juz nie mam pomyslu co by tu poprawic bo...prawde powiedziawszy nei ma co poprawiac:P

no ale jako ze moja kap00chowatosc omylna czesto bywa...dobrzy ludzie jak macie jakis poj$#%#%#% test to z checia go zapuszcze;]

Rogal

Spróbuj tego:

Spectro

To jest zadanie z finału VI OI - [link widoczny dla zalogowanych]

Poszukaj testów gdzieś tu: [link widoczny dla zalogowanych]

Aha, no i opracowanie jest gdzieś w niebieskiej książeczce ;) : [link widoczny dla zalogowanych]

kap00ch

no fajnie ze dopiero teraz to napisales jak juz 2 dni na to stracilem :P ale mam chociaz satysfakcje ze sam rozkminilem :] (probably jeszcze 2 bugi:P ale to juz hcyba jutro...) ;]

Spectro

Nie chciałem Ci odbierać tej satysfakcji :mrgreen: . A swoją drogą to dziwne, że się nie rozniosło - Cedric znalazł to zadanie już we wtorek :P .

Rogal

@Spectro: O żesz ty siło nieczysta! Masz szczęście że sam to rozkminiłem zanim wrzuciłeś rozwiązanie.

A swoją drogą to wygląda na to, że zostało do zrobienia już tylko 5 zadań w 2 seriach. Ciekawe ile jeszcze dorzucą bonusowych?

kap00ch

hurrej...moj behemot na 1100 linii wlasnie sie wywalil na wszystkich testach z OI z zawracaniem :P (reszta git:P) tak wiec chyba jednak chociaz przeczytam co tam doktorki pisza:>

[EDIT 1:22]
a jednak :] poszlo po mojemu:D behemot na 800 linii :}}}} a to rozwiazanie z OI niech se w du&^ wsadza:P wolne i nieoptymalne ;] w kazdym razie takie wrazenie odnioslem po 2 min lektury po czym olalem :P

Spectro

Mój algorytm przechodzi wszystkie moje testy oraz te z oi, a Athina wypisuje ANS :? .

Inna sprawa, że napisałem jedną w nim rzecz tak magiczną, że aż sam nie wierzę, że działa :P . I bądź tu mądry człowieku...

Rogal

LOL, jak się korzysta z tej wzorcówki z OI. Po jej skompilowaniu na pierwszym teście z OI dostaję dostaję error 202 :shock: Bo rozumiem, że poprawne odpowiedzi trzeba uzyskać na podstawie ich wzorcówki?

A wogóle to ja zauważyłem, że ona (wzorcówka) pliki jakieś otwiera. Nie jest to zabronione na OI? :shock:

Robson

bo to była 6 oi... tam sie jeszcze samemu wejscie na plikach obsługiwało... to są zamierzchłe czasy...

Rogal

To czy ktoś mógłby mnie w takim razie oświecić jak tą wzorcówkę przystosować do normalnych standartów? Mi ta wzorcówka zawsze zwraca 'NIE', niezależnie od wejścia, a nie mam siły debugować wzorcowych programów :?

Spectro

@Rogal:
Wywal wszystkie dyrektywy kompilatora oraz czytanie z pliku (zmienna f typu txt przy wczytywaniu i wypisywaniu danych). Przy read i write wystarczy wyrzucić zmienną f.

Kurczę, wszystkie testy mi przechodzi tak samo jak wzorcówka O_o . I dalej mi szybko wywala ANSa na Athinie...

Wynik NA PEWNO mieści się w integerze? A może to jakiś patologiczny przypadek, którego nie uwzględniłem? :?

edit: Wzorcówka z OI używa integera... Hmm...

A może Broniek używa za wzorcówkę na Athinie swojego algorytmu, który NIE DOSTAŁ maksa? :P

Rogal

@Spectro: Tak też zrobiłem, wzorcówka wszędzie wywala 'NIE'. Trudno się mówi.

W każdym razie już mi przeszło, 291 linii nie licząc komentarzy.

Spectro

](*,) :toimonster:

Nie mogę. Gdyby nie jeden_pierdolony_exit_zamiast_continue_w_jednym_szczególnym_przypadku, to zadanie przeszłoby mi już wczoraj. Pół dnia kurwa myślenia... To nie na moje nerwy :evil: .

Ale jest wreszcie OK i to się liczy :roll: . 170 linijek.

hansu

A mi sie przydarzyla taka historia... Napisalem sobie programik, potestowalem pod winda, ucieszony bylem ze mam wszystkie wyniki takie same jak insa (testowalem na tych testach z olimpiady i przykladowym ze strony). Juz mialem submitowac... ale pomny doswiadczen z A stwierdzilem ze sprawdze sobie na virgo jeszcze. I tu ZONK! Prawie same zle odpowiedzi O_o Po 2 godzinach debugingu udalo mi sie naprawic. Otoz wstawilem w jednym miejscu linijke

Rogal

@hansu: Intrygujące. To w takim razie co było źle, tj. dlaczego nie działało na virgo? Bo rozumiem, że po wstawieniu warunkowo wykonywanej instrukcji pustej zaczęło działać? Wiesz może dlaczego?

krzycho

Moglby ktos rzucic kilka wskazowek na temat tego zadania?(np. jak wykorzystac dwuspojne skladowe)

kap00ch

np. do tego zeby sprawdzac czy chlopek jest w stanie dosjc do pola z ktorego moze pchnac skrzynke dalej...:] no bo jesli dane pole na ktorym stoi chlopek ma ten sam BIC co przeciwne do pola na ktore mamy pchnac to znaczy ze mozna pchnac;]

Rogal

@Alibaba: Zwykły BFS z tym dodatkowym mykiem o którym napisał Kap00ch i obsługą zawracania w szczególnych przypadkach (może się zdarzyć tak, że będziesz musiał dopchać paczuszkę do pewnego miejsca, okrążyć ją, i zacząć pchać spowrotem) No i jeszcze kilka innych drobiazgów, ale generalnie idea jest taka jak zostało napisane.

kap00ch

zamiast obslugi zawracania mozna odpalic podwojnego BFSa...sie znaczy BFSa ktory ma dwie flagi odwiedzin i moze wlazic na pole jesli ma chozby jedna flage nie odfajkowana + dodatkowe warunki z myku o BICu...wyjdzie na to samo :}

Spectro

Mój algorytm można opisać w pięciu punktach:

1. Wczytanie i konstrukcja grafu początkowego.
2. DFS określający przynależność krawędzi grafu wejściowego do konkretnej dwuspójnej składowej.
3. Konstrukcja grafu stanów gry (wzajemne położenie dozorcy i paczki) w oparciu o przynależność krawędzi do dwuspójnych.
4. BFS na grafie stanów.
5. Wypisanie z jednego ze stanów końcowyh najmniejszej ilości ruchów.

Oczywiście po punkcie drugim i w punkcie piątym da się łatwo sprawdzić, czy odpowiedź nie powinna brzmieć: NIE. Dokładne omówienie tego sposobu znajduje się w niebieskiej książeczce z VI OI, której adres przytoczyłem w jednym z wcześniejszych postów.

kap00ch

mowilem ze sposob z OI jest nieoptymalny i pamieciozerny :P wystarczy jeden graf a nie jakies cudaki :P ale to tak btw... :}