Informatyka UJ forum

Pandunia · Gość

[deleted]

exeman

Pandunia: Bo sie nie wykluciles i dales zrobic w balona. Taka prawda. :/

Robson

Tylko to przeczytałem, ale mam wrażenie ze nie jest to trywialne zadanie... powiedziałbym nawet ze całkiem wymagające...
A tu jeszcze AVL na głowie :(

Yoter

głowa do góry na pewno da się to zrobić w godzinkę :D

Spectro

Właśnie miałem olśnienie na ćwiczeniach z ASD i wymyśliłem, jak zrobić M. Znajdujemy najpierw cykl Eulera, a potem rozwiązujemy zadanie "Lot na Marsa" z 2 etapu XII OI:

[link widoczny dla zalogowanych] - tu jest gdzieś opis
[link widoczny dla zalogowanych] - tu gdzieś jest program firmowy

Ech... stare czasy... zrobiłem to zadanie na 100pkt wtedy. Szkoda, że to był tylko dzień próbny.

Madras

Spectro dokładnie to samo u mnie ;]. A kolejne dni poszły tak, że szkoda gadać ;].

hansu

Przepchnalem to zadanie... Az normalnie uwierzyc w to nie moge... To byla jedna wielka improwizacja... Pod koniec kodowania zorientowalem sie ze w sumie wszystko dobrze wypisuje tylko nie bardzo mam jak znalezc jedna rzecz - kierunek w ktorym jezdzie piaskarka (pierwsze skrzyzowanie przez ktore przejezdza). No i lipa, zalamka, cale "flaki" do przerobki, bo projektujac strukture danych nie pomyslalem w ogole ze to mi moze byc potrzebne... Ale pomyslalem ze raz kozie smierc i zaczalem sztukowac... Dodalem cos do struktury danych, jakies dziwne fory, ktorych zakresy opracowalem metoda prob i bledow na przykladowym tescie i w sumie stwierdzilem, ze przeciez to NIE MOZE dzialac... Ale coz raz kozie smierc, poslalem i.... OK. Normalnie jaja jak berety :D:D:D

Tak wiec uczcie sie na cudzych bledach i DOKLADNIE zaprojektujcie sobie strukture danych do tego... Naprawde, to jest kluczowa czesc tego zadania. Sam algorytm to euler zerzniety z forum TCS i jeden krotki for na wyszukanie elementu minimalnego z tablicy... Niestety jesli chodzi o testy to jest gorzej niz zle... Nawet przykladowy daje mi zupelnie inne wyniki i nie sadze zeby ktos pokusil sie o generator testow do tego (generator moze jeszcze ok ale program ktory sprawdzi czy podany output jest jednym z bardzo wielu poprawnych to juz bedzie ciezko :/) A i konstruowanie samemu testow jest mordercze... Takze zadanie w stylu totolotek: albo dziala za pierwszym razem, albo piszemy od nowa :/ W kazdym razie powodzenia w pisaniu tego zadanka, jakby co to postaram sie tutaj na forum odpowiadac na ewentualne pytania...

jagm

Jakoś udało mi się przepchnąć to zadanie, choć nie obyło się bez głupich błędów. Pierwszy i chyba najpoważniejszy, to złe obliczanie ilości piasku w piaskarce. Dlatego jak będziecie to robić, to pamiętajcie, że piaskarka jedzie od połowy pierwszej drogi do połowy drugiej, itd. Ja pamiętałem o tej połowie tylko dla drogi, od której zaczynała, a potem już się wszystko sypało. Druga sprawa, to dodawanie piasku w odpowiednim momencie, bo to również na początku miałem źle. No i na koniec to wybranie odpowiedniego elementu, od którego należy zacząć, bo z tym nigdy nie wiadomo ;]
Poza tym wszelkie uwagi, które podał hansu, a przede wszystkim prawidłowa struktura danych, bo ja w trakcie musiałem dodawać pełno zmiennych pomocniczych i dodatkowych tablic.

mateo

jagm

Makros

A ja mam pytanie... u kogo/gdzie znajdują się testy poprawnościowe do tego zadanka... bo chętnie bym je sobie oblookał... :)

hansu

Jesli chodzi o testy z Quicktesta to wszystkie sa u Matea (odkad mu quote powiekszyli to moze chlopak szalec :P) w katalogach do ktorych sciezek nie pamietam, ale sa one w topicu o testerce 2.0...

Rogal

W końcu poszło. Ciągle się zastanawiam jak mogłem zrobić tyle błędów w zadaniu na 96 linii :shock:

Spectro

kap00ch

hehe...taki maly lol :P sprapralem tez sprawe z kierunkiem czytaj wypisywaniem pierwszego skrzyzowania...sam porobilem nie wiem co i moim zywczajem a noz widelec sie uda poszlo :D pomimo ze nie mam pojecia jakim cudem bo wg mnie jest zle...ale co tam :p

tak wiec jeszcze raz...LUDZIE PRZEMYSLCIE SPRAWE WYPISANIA KIERUNKU! oraz sama STRUKTURE :]

Spectro

To zadanie jest zwalone. Teraz już nawet nie wiem, czemu mi działa (przepchnąłem przez Athinę i mam same OK na testerce matea O_o). A program ma tylko 80 linijek.

Historia błędów w tym algorytmie jest długa i kręta. Łatałem je na chama (weryfikator skrzyżowania na końcu, zmiana jednej zmiennej z głębokości rekurencji na wielkość stosu, itd.). Miałem: ANS (3 rodzaje: "skończył się piasek", "błędne skrzyżowanie", "ścieżka niespójna"), TLE, RD9, R29, R30 i R32 (cztery ostatnie - WTF??).

No i czemu wystarcza JEDEN cykl Eulera?

Rogal

Spectro

@Rogal: Twoje wyjaśnienie co prawda potwierdza moje przypuszczenia, ale ja tego ani nie udowadniałem, ani nikt mi nie wyjaśnił, że to jest prawda. Czysta intuicja, ale za to jak skuteczna :P . Jeszcze to na spokojnie przeanalizuję...

Krisowski

Mam prośbę. Czy ktoś mógłby opisać jak zrobił to zadanie, bo ja nawet nie bardzo wiem od czego zacząć :?

Makros

Przed chwilką dostałem OK'eja więc spróbuje wytłumaczyc...

Gdy masz już wczytane dane, to musisz znaleźć wśród tych skrzyżowań cykl eulera... jakikolwiek... to nie ma znaczenia... najprościej można to zrobić algorytmem podanym dziś na wykładzie (to samo jest podane na forum tcs...)...

Gdy już mamy ten cykl to trzeba teraz znaleźć skrzyżowanie z którego będziemy startować... (od razu zaznaczam, że nie trzeba sprawdzać tego cyklu w obie strony... wystarczy w jedną... ponieważ w każdym kierunku istnieje taki conajmniej jeden najlepszy do startu punkt...) :D

Robisz to tak:
wybierasz losowy wierzchołek z którego zaczniesz sprawdzanie... Idziesz tym cyklem ciągle uaktualniając stan piaskarki, gdy w pewnym momencie stan piasku spadnie poniżej zera, to nie przerywasz, ale kontynuujesz... a ten minimalny stan i miejsce w którym to nastąpiło zapamiętujesz... gdy sytuacje gdzieś za chwilkę się powtórzy to sprawdzasz gdzie mniałeś mniej piasku i wtedy zapamiętujesz... Potem wystarczy wypisać ten cykl zaczynając w punkcie gdzie miałeś najwiekszy debet piasku...

Mam nadzieje, że ująłem to w miare zrozumiale...

Wiem, że to brzmi to troszke podejrzanie, ale przeanalizuj sobie jakiś przykład i zobaczysz, ze to rozwiązanie jest całkiem logiczne... :)

Rogal

@Krisowski
Trzeba jeszcze dodać, że jak dojdziesz ponownie do punktu początkowego (a napewno w końcu dojdziesz bo cykl Eulera jest cyklem :roll: ) to musisz sprawdzić, czy ilość piasku która ci została w piaskarce po przejechaniu całej trasy jest większa (równa) od zera. Jeśli tak to znaczy że starczy Ci piasku na przejechanie całej trasy i wypisujesz trasę tak jak napisał Makros, wpp nie da się całej trasy przejechać i wypisujesz 'NIE'.

smh · [świeżak] Dołączył: 05 Mar 2006 Posty: 21 Przeczytał: 0 tematów

Ja powiem tyle...

[link widoczny dla zalogowanych]

Madras

Haha dobre ;].

Spectro

No to wszystko sprowadza się do innej niebiekiej książeczki niż podałem po prostu :P .

Swoją drogą, zadanie pasuje na finał... nie jest wcale takie oczywiste.

mateo