Informatyka UJ forum

mateo · Wysłany: Czw 19:40, 09 Mar 2006 Temat postu: C - Zabawa karnawałowa

Ma ktos jakies ciekawe testy do tego zadania ?

Mnie juz powoli zaczyna szlag trafiac przy tym bo caly czas dostaje RTE, a nie mam pojecia na czym. Ze zwalnianiem pamieci mam raczej wszystko dobrze bo na testach wielkosci ponad 70MB nie przepelnia mi sie stos.
Jakby ktos chcial to moge tez udostepnic moje testy...

mateo · Wysłany: Pią 0:23, 10 Mar 2006 Temat postu:

Moj problem z RTE jest juz nieaktualny bo sie okazalo, ze byl jeden test niezgodn ze specyfikacja zadania na sprawdzaczce (mial cyferke w jednej z nazw pociagow)...

Ale co do testow to jak ktos cos ma to niech mi zapoda, a ja dorzuce do mojej tesreki - wtedy wszyscy beda miec latwiej z debugowaniem tego zadanka.

exeman · Wysłany: Sob 16:13, 11 Mar 2006 Temat postu:

No to ja juz jestem na polmetku, z Heap Overflowem sie uporalem, teraz tylko ANS trza znalesc :P

Czy ma ktos moze jakiekolwiek testy do tego zadania?

Btw. Czy nie uwazacie, ze bez sensu jest stosowanie tam listy z glowa? :/

mateo · Wysłany: Sob 16:34, 11 Mar 2006 Temat postu:

No ja tez zaliczylem Heap Overflow bo zapomnialem ze w zwyklym pascalu typ string nie jest dynamiczny i ma zawsze 256 znakow :/.
A co do tescikow to w sumie moze cos umieszcze w testerce za pare dni... Tyle ze w tym zadaniu jest troche wiekszy problem z generatorem testow, bo nie jest tak latwo wygenerowac test ktory spelnia warunki zadania - trzeba na bierzaco podczas generowania testu symulowac poprawnym programem jak zmieniaja sie pociagi, aby naprzyklad nie bylo w tescie polecenia zlaczenia pociagow ktore juz nei istnieja, itp.

exeman · Wysłany: Sob 17:01, 11 Mar 2006 Temat postu:

A jednak, nie ma ANS, ale jest overflow :/ Teoretycznie wszystko dobrze, no i kurde nie ma jak sprawdzic czemu zle

Gość · Wysłany: Sob 19:30, 11 Mar 2006 Temat postu:

e tam nie ma jak sprawdzic... dodaj w kodzie przed kazda operacja new(wskaznik) instrukcje postaci: writeln('tworzenie czegos tam o imieniu jakims tam'); a przed kazda operacja dispose(wskzanik) instrukcie postaci: writeln('usywanie kolesia/pociagu o imieniu: ', wskaznik^.name); Zapusc program i posprawdzaj do ktorych linijek oznaczajacyh tworzenie czegos tam brakuje odpowiadajych im linijek oznaczajaych usuwanie z pamieci. Wtedy bedziesz wiedzial gdzie nie zwalniasz pamieci i po klopcie.

A apropo testow to dodalem kilka do testerki, ale nie wiem czy sa poprawne... posprawdzajcie, a jak by sie wam wydawalo ze cos nie gra to dajcie znac.

exeman · Wysłany: Sob 19:40, 11 Mar 2006 Temat postu:

A myslisz, ze nie robilem tak? :P Polowa mojego kodu to wykomentowane writeln debugowe :)

Co do testow, to wszystkie przechodze w czasie zerowym, ale na asd.tcs.ii.uj.edu.pl Heap Overflow :/

mateo · Wysłany: Sob 19:47, 11 Mar 2006 Temat postu:

Zapomnialem sie zalogowac na forum poprzednio.... :)

No te moje tety sa bardzo malutkie wiec na nich nie da sie miec wiecej niz 0.00. Jesli chodzi o heap_overflow... no to zaraz dorzuce jeden tescik na to bo wiecej i tak juz mi sie nie zmiesci na koncie.

exeman · Wysłany: Sob 19:57, 11 Mar 2006 Temat postu:

Ok, z gory dzieki.
Hm, a w tym momencie cos sie testerka pokrzaczyla, robisz cos przy tym, czy cos sie rzeczywiscie popsulo :P

exeman · Wysłany: Sob 20:25, 11 Mar 2006 Temat postu:

Mateo, nie mam RTE tylko RCB :/ (na tej oficjalnej ujotowskiej sprawdzarce)

kap00ch · Wysłany: Nie 11:44, 12 Mar 2006 Temat postu:

swoja droga ma ktos jakis sprytny sposob wczytywania danych do tego zadania? jest jakas cudowna funkcja w pascalu ktora czyta string do delimitera?
albo nie wiem ...czytacie znak po znaku do spacji i zamieniacie na stringa czy inne pascalowe cuda? :]

hansu · Wysłany: Nie 12:38, 12 Mar 2006 Temat postu:

Ja zamiast stringow[8] uzywam tablicy charow[1..8]. Wczytuje swoja procedurka znak po znaku, dopoki sa literami. A wypisywanie dzial normalnie, przez write(...); W takim razie jaka roznica? A taka ze w tablicy nie mam pola 0 ktore na nic nie jest potrzebne a miejsce zajmuje. A obawiam sie ze przy tym zadaniu to moze miec znaczenie... Bo limit pamieci jest moooocno niewystarczajacy :/

kap00ch · Wysłany: Nie 12:44, 12 Mar 2006 Temat postu:

A porownywanie tablic charow w przeszukiwaniu listy po nazwach tez masz procedura czy pascal jest tak cfany ze sie polapie przy if tab1=tab2 ? bo prawde poweidziawszy moj sie nieco nie lapie :P no chyba ze cos spieprzylem, a pisanie procedurki do porownywania wydaje mi sie conajmneij malo efektywne...

hansu · Wysłany: Nie 13:36, 12 Mar 2006 Temat postu:

Normalnie mozna porownywac = i <>. Wszystko piknie chodzi.

exeman · Wysłany: Nie 16:41, 12 Mar 2006 Temat postu:

ja wczytuje po calej linii a potem parsuje.

mateo · Wysłany: Nie 19:47, 12 Mar 2006 Temat postu:

A nie latwiej napisac cos w rodzaju funkcji:
function read_word: string;

ktora wczytuje pokolei znaki az napotka jakis "bialy znak" i wtedy zwraca to co wczytala.
Takie cos sie w kazdym zadanku przyda i oszczedza sporo pracy przy ewentualnym pozniejszym parsowaniu - w tym zadaniu akurat nie ma liczb do wczytania, ale jakbysmy mieli potem parsowac liczby to znowu sami musielibysmy przetwarzac tekst na liczbe. A jesli z gory wiemy ile jest na poczatku kazdej linii wyrazow to zapuszczmy tyle razy taka funkcje read_word a potem normlanie wczytujemy liczby - to apropo zadania R4 i R5.

Szkoda ze nie mozna uzywac c++:/ bo tam to by sie to normlanie bez problemu wczytywalo, a tutaj sie trzeba bawic z takimi pierdolami. Wogole ten pascal to porazka.

Robson · Wysłany: Pon 20:59, 13 Mar 2006 Temat postu:

Mam pytanie do tych którym juz zaliczyło ten program: Czy po każdej zabawie (nowym zestawie dancyh) czyścicie całą pamięć(wszystkie wskaźniki)?? Bo mi sie wydaje że to moze mieć narzut dość spory na złozoność... czy testy/limity TCSowców to uwzględniają?
myslałem żeby zaimplementować swoj przydział pamięci (śłusarek pokazywał jak sie takie cos robi na tablicy), ale i tak trzeba przeglądnąć całą żeby wyzerować wskaźniki (w takim przypadku zerowanie jest jednak bardzo proste)...

hansu · Wysłany: Pon 22:10, 13 Mar 2006 Temat postu:

No niestety, trzeba to wszystko podisposowac, bo w przeciwnym wypadku sie nam pamiec przepelni... Ja to robie identyczna prawie prodecura jak PRINT (tak usuwam pociag) no a usuniecie listy pociagow to jeden while. Nie robie zadnych cudownych optymalizacji a przeszlo mi spokojnie...

exeman · Wysłany: Wto 21:54, 14 Mar 2006 Temat postu:

Jakie macie czasy w C na virgo?

hansu · Wysłany: Wto 22:55, 14 Mar 2006 Temat postu:

Fidel · Wysłany: Wto 22:55, 14 Mar 2006 Temat postu:

hmm.. a ja mam moze glupie pytanie ale jakos nie moge tego znalezc na wykladzie

czym sie rozni lista podwojna od pojedynczej i lista z glowa od bez glowy :oops:

a tak poza tym to wypisywanie chyba nie ma byc w O( 1 ) :?:
i tak sie zastanawiam... Union da sie zrobic w O( 1 ) :?: zalozmy ze mamy jedna liste z porzadkime "w lewo" a druga po reversie wiec chyba do polaczenia ich musimy pokombinowac ze wskaznikami :?: chyba ze jak laczymy to nie moga isc w roznych kierunkach :?:

exeman · Wysłany: Wto 23:26, 14 Mar 2006 Temat postu:

Ja mam ostro namieszane, troche nagiąłem definicje kolejek, ale teoretycznie jest poprawne. Union mam w czasie stałym O(1), bez zadnej petli w srodku, natomiast print oczywiscie wymaga przejazdu przez elementy, wiec de facto nie jest w czasie stalym. Mysle, ze to niescislosc w zadaniu i chodzilo tu o zlozonosc liniowa.

Moje czasy:
ID TEST_NAME LIMIT TIME SCORE RESULT
1: 00_example 1.00s 0.00s 10/10 OK
2: 10_20 1.00s 0.00s 10/10 OK
3: 11_20 1.00s 0.00s 10/10 OK
4: 12_20 1.00s 0.00s 10/10 OK
5: 13_20 1.00s 0.00s 10/10 OK
6: 30_1000 2.00s 0.01s 10/10 OK
7: 31_1000 2.00s 0.04s 10/10 OK
8: 32_1000 2.00s 0.03s 10/10 OK
9: 33_1000 2.00s 0.05s 10/10 OK
10: 34_1000 2.00s 0.03s 10/10 OK
11: 70_100000 3.00s 0.26s 10/10 OK
12: 70_heap 3.00s 0.65s 10/10 OK
13: 90_heap 20.00s 5.94s 10/10 OK

hansu · Wysłany: Wto 23:27, 14 Mar 2006 Temat postu:

Lista pojedyncza to taka w ktorej masz wskaznik tylko do nastepnego elementu. Bez glowy tzn. ze masz gdzies wskaznik do pierwszego elementu. (L->(1)->(2)->nil). Z glowa bylaby taka ze ta glowa to takie zerowe pole z nieistotna wartoscia info (L->(glowa)->(1)->(2)->nil). Dlaczego zapytasz? Ulatwia to pare algorytmow np szukania...
A w podwojnej masz w kazdym polu wskazniki next i prev. Glowa przy podwojnej znaczy ze masz pole w ktorym trzymasz nieistotne co (w tym przykladzie podpowiem nazwe pociagu) i masz z niej wskazniki do pierwszego i do ostatniego elementu...

Jesli zas chodzi o laczenie to tak jak jest napisane muszisz to zrobic w O(1). Laczac dwa pociagi jeden moze byc reversed a drugi nie ale to ma Ciebie nie obchodzic. Laczysz na chama, ze tak powiem. I dopiero przy wypisywaniu musisz tak zrobic zeby wylapac te, nazwijmy to, nieciaglosci. zeby sie nie zapetlic i nie wypisywac w kolko dwoch sasiednuch pol bo one nextami na siebie nawzaje wskazuja....

Fidel · Wysłany: Wto 23:39, 14 Mar 2006 Temat postu:

Hmm
to zalozmy ze mam dwa pociagi

hansu · Wysłany: Wto 23:43, 14 Mar 2006 Temat postu:

Nie. Union dziala na odwrot.

Bedzie

A->B->C->F->E->D

@exeman: niezle czasy wyciagnales. Brawo. Jestem pod wrazeniem :D