Informatyka UJ forum

Spectro

Fakt, że zmieściłem się w pamięci, graniczyło z cudem :P . Inna sprawa, że ten sposób z OI jest stosunkowo łatwy w implementacji i nie trzeba kombinować z zawracaniem, bo to jest już określone w grafie stanów. Nie trzeba też za wiele debuggować, no chyba że się popełnia takie błędy jak ja i wychodzi się z programu przed wczytaniem wszystkich danych z testu :P .

kap00ch

dla mnie to on nieintuicyjny jest...chociaz moze wynika to z tego ze czytalem go cale 2 min po czym pomyslalem "a ch** z tym...moje lepsze:P" ale to nei zmienia faktu ze smierdzi i jest wolniejszy niz roziwazania BFSowe na jednym grafie :p

Spectro

Kap00ch, ale Twoje rozwiązanie jest bardziej kombinowane i podatne na błędy :P . A co do prędkości to nie jestem przekonany, że Twoje rozwiązanie jest znacząco szybsze. Oba algorytmy są w końcu liniowe względem ilości pól w hurtowni.

kap00ch

nie wiem jak to z OI ale moje jest n*m*3 :] (a na bledy to i owszem...:P ale pominmy ta kwestie gdyz aksjomatem jest ze kap00chowe programy same w sobie sa bugiem:P) ...chociaz i tak wg mnie mozna to jeszcze przyspieszyc...tutaj akurat by pasil idealnie jakis A* albo cos z IDSow...no al uparli sie na ta swoja dwuspojna :P chociaz w sumie przyznam sie ze na poczatku jej nie docenialem :]

Spectro

Szczerze mówiąc, to jak zobaczyłem to zadanie, to użycie dwuspójnej wydało mi się w miarę oczywiste. No a Ty się upierałeś, że Twoje Dijkstry są bardziej intuicyjne - Twoja sprawa :P . Tak to jest, jak się zna bardziej zaawansowane metody i nie widzi się przez to najprostszych rozwiązań... (ale: najprostsze<>najbardziej intuicyjne)

hansu

To ja moze troche bardziej szczegolowo opisz moj algorytm. Moj main wyglada tak (tylko nie zrzynac :P):

Spectro

No to mamy, hansu, bardzo podobne rozwiązania. Z tym, że ja w BIC od razu sprawdzam to, co Ty w osobnym DFSie. No i jawnie konstruuję graf stanów, a nie na bieżąco, przy czym wynik wypisuję po przeglądnięciu całego grafu.

Rogal

hansu:
Zamiast pisać osobnego DFS-a można sprawdzić BFS-em (który i tak napisać trzeba) czy dozorca może dojść do paczki. Trochę wolniej, ale za to kod krótszy. Wystarczy BFS-owi dorobić parametr bool'owski.

trywialna

hansu

No bo jako odpowiedz masz podac ilosc przesuniec paczki. I ta moja "odleglosc" to wlasnie to. Jesli w tym "wirtualnym grafie" krawedz odpowiada przesunieciu to ma wage 1, a jesli tylko obejsciu paczki, to wtedy 0.

trywialna

ehh no tak... od nastepnego razu czytam dokladnie tresc zadan:] dzieki hansu :wink:

krzycho

hansu

Nie musza miec tej samej bcc. Bo magazynier nie obchodzi paczki. Wystarczy sprawdzic czy pole po drugiej stronie paczki (w stosunku do magazyniera) jest wolne (czyli nie jest sciana ;))

Spectro

[link widoczny dla zalogowanych]

Enjoy! ;)

trywialna

Ma ktos moze jakies testy wlasnej roboty do tego zadanka? na virgo mam wszysto Ok a athina mowi ANS...

Edited: a jednak przeszlo, nie wyzerowalam jednej zmiennej:]

chlebek

Mam prośbe, czy mógłby mi ktoś przesłac na e-maila wzorcówke z finału przerobiną, żeby działała pod fp, bez wczytywania z pliku, bo coś mi nie wychodzib :cry: , jakieś blędy wyskakują, nawet jeśli wrzucam kompatybilność z TP.

Bylbym wdzięczny

hansu

Nie wiem czy ktos ja przerabial, bo strasznie kijowa jest ta wzorcowka... Jakies rekurencje przez goto i inne archaizmy. Jak chcesz to moge wystawic mojego execa... Znajdziesz go [link widoczny dla zalogowanych]

kg86

rowniez mam schematyczne rozwiazanie:
1) czytaj dane
2) BIC
3) BFS
jednak nie tworze zadnego grafu 'grafu', tylko moja plansze[1..100,1..100] of Pole traktuje jak graf, czyli wszystkie 4 drogi prowadza do pola, ktore rozni sie jedna wspolrzedna o |x|=1, takze wystarczy ze sprawdze czy dane pole to nie sciana, oraz czy nie zostalo odwiedzone [wszystko wartosci logiczne]
natomiast moj BFS w zasadzie nie zwraca uwagi czy pole odwiedzone czy nie, tylko sprawdza czy dana droga juz szedlem, dlatego mam 4 drogi w kazdym polu, reprezentowane przez wartosci logiczne :) wiec defacto tworze graf zorientowany, kazda krawedz niezorientowana stanowia dwie drogi... na stosie w BFS odkladam aktualna pozycje dozorcy, paczki, ile paczka przebyla juz drogi, oraz dla ulatwienia nr drogi ktora laczy dozorce z paczka...
na pewno nie jest to najoptymalniejsze rozwiazanie, co prawda nie trace czasu na budowe grafu, a po BIC nie musze aktualizowac zadnych wartosci logicznych, czy tez tworzyc jakiegos nowego grafu, ale dochodzi conajmniej jeden warunek wiecej do sprawdzenia za kazdym razem... [nie mam porownania - na virgo mialem w sumie 0,03 s.], w kazdym badz razie to rozwiazanie wydaje mi sie moze nie najprostsze, ale dosc intuicyjne ;)

swiecmich

Mam dosyc dziwny problem z tym zadaniem. Przy kompilacji poleceniem "fpc O.pas" moj program daje dokladnie takie wyniki jak w plikach *.out z testerki matea. Jesli jednak skompiluje go z parametrami "fpc -Sgic -Xs -viwnh -OG2p3 O.pas" to daje zupelnie inne wyniki, czasami sie zapetla itp. Jesli usune parametr -OG2p3 to chyba dziala juz poprawnie. Niestety athina i testerka kompiluja z tym parametrem. Wie ktos moze dlaczego tak sie dzieje ?

Spectro

Niestety padłeś kolejną ofiarą optymalizatora FreePascala. Trzeba gdzieś wstawić linijkę typu:

Robson

Najprawdopodobniej któryś wskaźnik. Najlepiej jesli masz jakąś procedurę zerojącą to jej kod wrzucić w takie miejsce zeby ktoś na 100% skorzystał z tych zmiennych które wyzerowałeś.

:-)

Pomocy, pomocy! Słoń, straszliwy Słoń!
Pomocy, pomocy! Słoniowy Strach! Słoniocy! Słoniocy! Strachowy Pom! Pomocny Strach! Słoniocy!

M... m... ma ktoś może jakieś złośliwe testy do tego? Koniecznie złośliwe, bo tylko takie są skuteczne w walce ze Słoniem! Te na virgo (z oi) nie sa wystarczająco wredne - same OK, a athinowy Słoń nieugięcie broni się ANSem!

r4ku

poszlo, po wielogodzinnej walce z debugerem w dloni... zadanie paskudne, ale rozwiazanie zapewnia duza satysfakcje... pomimo ze przez magazyniera nie umiem nic na algebre i analize a jutro kolos poprawkowy z jednego i kartkoweczka z drugiego...

kg86

@:-)
na virgo kazdy test sklada sie z jednego zestawu, natomiast testy na Athinie skladaja sie z wielu zestawow, wiec moze nie ustawiasz jakis poczatkowych wartosci zmiennych? tez mialem taki blad, okazalo sie, ze nie ustawialem wartosci niektorych zmiennych logicznych [no skoro zawsze ustawiaja sie na false ;)]

Makros

Skoro kap00cha nie ma :P to pozwole sobie zamieścić test jego autorstwa który dość ułatwia sprawe :) Przynajmniej mi pomógł...

[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]