Informatyka UJ forum

Robson

Wiecie to chyba tylko kwestia podejscia - w tamtym roku tez były proste przez pierwsze 3 dni... tylko dzieki temu mam z PA koszulke ;)

jagm

No ja niestety na koszulke się nie załapałem. Ale to były moje początki. Wtedy nawet nie wiedziałem, co to stos jest, więc i tak jestem z siebie dumny, że udało mi się większość zadań zrobić (co prawda brutalem, ale zawsze coś ;])

mateo

Pierwsze 2 rundy PA zawsze byly na poziomie takim ze kazdy w zasadzie te zadaia robil na maxa punktow. A co do tego zadania `odcinki ' to swoja droga ciekaw jestem czy ktos z was potrafilby udowodnic ze algorytm ktory macie jest ok:) bo ja podejrzewam ze mam ten sam algorytm co wy, ale nie umiem pokazac ze on dobrze dziala.

Robson

Niestety nie da się zastosować dowodu przez athinę ;)
no ale za to dowód "z rysunku to widać" na razie przechodzi ;)

jagm

Rogal

Mam duży problem z tartakami. Wymyśliłem prosty i działający (chyba :roll: ) algorytm, ale daje inne wyniki na teście przykładowym, mianowicie:

1 1
2 3
3 2

co jest też imho wynikiem poprawnym.
Ale niestety sprawdzarka daje mi: "Błędna odpowiedź na teście przykładowym". Próbowałem różnych rozwiązań z wypisywaniem na wyjście, straciłem 10 podejść na wysyłanie różnych wersjii, ostatnia wysłana też ma ten błąd - i się zastanawiam czy to jest wina ich sprawdzarki czy to coś u mnie.

No nic, dzisiaj się przekonam :twisted:

Madras

Ja używam do wypisywania odpowiedzi "writeln( pierwszaLiczba, ' ', drugaLiczba );", odpowiedź mam inną, niż w przykładowym teście, a dostałem OK.
Jeśli Twój program wypisuje taki wynik ze znakiem końca linii na końcu i bez spacji przed nim, to powinno być ok... Jak wygląda Twoja funkcja wypisująca?

Rogal

printf("%d %d\n",i,res[i])

opcjonalnie próbowałem też cout << i << " " << res[i] << endl;

Próbowałem też te 2 powyższe bez znaku końca linii po wypisaniu ostatniego elementu.

Czy jest możliwe, że pod Linuxem mój program w C++ działa inaczej niż pod Windows, ewetualnie że inaczej wypisuje znaki na wyjście?

Madras

No to nie bardzo wiem, co może być nie tak :/.

Rogal

Mam nadzieję, że dzisiaj się dowiem 8)

W zasadzie już i tak pogodziłem się z faktem, że pomimo proprawnego algorytmu za Tartaki będzie 0 pkt z powodu jakiegoś głupiego błędu. Chciałbym się tylko dowiedzieć gdzie ten błąd jest co by następnym razem go nie zrobić albo przynajmniej szybko wykryć.

jagm

Madras

Może nie inicjalizujesz którejś zmiennej? Używasz tego samego kompilatora, co PA?

Rogal

Używam Dev'a, a on jest na g++ więc jestem kompatybilny z serwerem Potyczek.

W zasadzie to chyba są tylko 2 możliwości: albo jest jakaś rozbieżność wynikająca z systemu operacyjnego (Windows / Linux) albo ich testerka nie uznaje takiego rozwiązania zadania.

Co do inicjalizacji zmiennych to oczywiście jest. Jakaś luka mogła być z tego powodu, że używałem STL, konkretnie stosu. Nie wiem jak tam z inicjalizacją, więc po nieudanym submicie na wszelki wypadek wstawiłem kod:

jagm

To może mają testerkę zrypaną. Bo dla mojego rozwiązania:

Madras

Z tego, co widzę, to nie tylko Ty masz ten problem... Ale na forum PA ludzie też nie bardzo wiedzą, co się dzieje oO.

Rogal

No, zobaczymy.

Nawet jeśli ich testerka jest zrypana to i tak wolałbym wiedzieć dlaczego moje 1 1, 2 3, 3 2 nie przechodzi, a innych tak.

Tymczasem dzisiejsze zadania są znacznie ciekawsze :twisted:

Madras

Uff, 4 godziny i lot wysłane, chociaż czy rzeczywiście poprawne okaże się za 24h ;].
Czas na żuczki ;].

Rogal

@Madras: Na początku lioteria wyglądała na dużo ciekawszą, tymczasem jak się okazało, że te same wyniki do których dochodzi się na k sposobów liczą się k razy to sprowadza się do zadania banalnego.

A szkoda. 8)

jagm

Rogal

@jagm
No ja właśnie rozkminiłem jak to zrobić z w miarę przystępną złożonością a tu się okazało że tak właśnie jest i że myślałem na darmo :lol:

Więc np. dla danych wejściowych

Madras

No jakby trzeba było liczyć wynik każdego losowania, to by się raczej sprowadziło do zadania wykładniczego ;p.

Rogal

@Madras:
Nie koniecznie. Miałem algorytm o trudnej do określenia złożoności, ale coś pomiędzy O(n^2) a O(nlgn).

Madras

Licząc wynik każdego możliwego losowania? Przecież każda kula może być albo nie być wybrana, czyli dla k kul wyników losowań jest 2^k oO.
No chyba, że masz jakiś inny sposób na określenie, czy wynik należy odrzucić, czy dodać do reszty oO.

Rogal

@Madras:
Jestem prawie pewny, że wystarczyłoby dla każdej kuli sprawdzić, czy da się jej numer uzyskać z wymnożenia jakiejś ilości innych kul. A to można łatwo zrobić w n^2.

Jakby co to zapraszam na gg co by innym nie ułatwić za bardzo naszą rozmową rozwiązania tego zadania

Madras

Ok nvm, są już wyniki 2 rundy. Jak tam? U mnie okrągło, trzeba się teraz za żuczki zabrać.