Informatyka UJ forum

Spectro

TLE można wyeliminować przez binsearcha, który znajduje najwyższą wieżę, która wymaga aktualizacji (choć złożoności asymptotycznej nie poprawia :P ). Piszę o tym, bo już kilka osób mnie o to pytało.

Fidel

jagm

Madras

Ale jeśli musisz zaktualizować tylko dane oznaczone iksem:

XXXXXXXXXXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

To binsearch oszczędza sporo czasu. Jak napisal Jasko na forum TCSu, asymptotycznej to nie poprawia, ale czasem robi różnicę.

jagm

wrrr...
nie robiłem jeszcze tego zadania, nie wiem, jaki tam ma być dokładnie warunek, ale zakładam, że dopóki masa żółwia nie jest większa niż wytrzymałość wieży, więc:

Skrobocik

Jagmusiu, ten binsearch to jest do wersji odwrotnej do Twojej, że zaczynamy od najmniejszych żółwi, a potem dokładamy od spodu ;)

jagm

mhm. jak tak, to ok ;] ale skoro mamy jakiś warunek w binsearchu, to i tak pewnie jakoś by się go dało obsłużyć przy while'u :P

Madras

Ale w tej odwrotnej wersji też się da iść od lewej do prawej, Jagm ma rację. Trzeba tylko pamiętać poprzednie tab[i].

Skrobocik

Nie wiem, po prostu nie zagłębiałem się w sposób rozwiązania z dokładaniem na górze i tak mi się pomyślało, że skoro Jagm robi tym sposobem i nie widzi miejsca na bina, to pewnie nie ma ;)
Wiem - faceci uogólniają ;p

kg86

skodowalem to tak, jak pisal Jasko na forum TCS'u, bez zadnych usprawnien i binsearch'ow i zielone OK pojawilo sie bardzo szybko :)

jagm

no dobra, już widzę sens stosowania binsearcha ;] zapomniałem, że fajniej się idzie od drugiej strony po wieżach, bo od lewej jest dużo zabawy z tmpami ;] ale i tak przechodzi :P

liffe

mam problem.
chodzi, ale źle. Wiem, gdzie mam problem, ale nie wiem jak się go poprawia. Otóż, śledzimy działanie programu na przykładowym teście:
5
1 2
3 4
5 6
7 1
2 3
Idziemy od góry:
1 krok: tab[1]=WagaZolwia[1];
2 krok: tab[2]=tab[1]+WagaZolwia[2];
3 krok: tab[3]=tab[2]+WagaZolwia[3];
4 krok: stwierdzamy, że wytrzymałość żółwia jest zamała, a waga za duża, by coś sensownego z nim zrobić.
5 krok: tab[2]=tab[1]+WagaZolwia[5]; i tyle.. bo pod żadną większą wieżą on się nie zmieści, a mniejszej nie zaktualizuje;

Takim oto sposobem otrzymujemy wysokość wieży 3, mimo że miałaby być 4. Gdzie mam błąd? help! 100 minut zostało. Chcę zdążyć

jagm

bo tab[2] nie musi się równać tab[1]-zolw1
dla kazdego zolwia przechodzisz przez cala tablice tab, czyli moze sie okazac, ze zolw nr 3 jest lepszy na pozycji tab[1] niz zolw nr 1, ktorego tam wstawiles.
czyli inaczej mowiac: bierzesz zolwia i sprawdzasz, od tab[1] az do konca (albo dopóki tab[i]-zolw >=0) czy nie poprawisz wytrzymalosci wiezy dodajac go na sama gore

liffe

w tym momencie już się zgubiłem. Może, nie dopisałem do końca, co robię w kolejnym kroku. Najpierw szukam binSearchem najwyższej wieży, którą można postawić na danym żółwiu. Od tej wieży idąc do dołu sprawdzamy czy jeśli podstawimy pod nią tego żółwia, to nam się o 1 większa wieża się nie polepszy. Jeśli się polepszy, to polepszamy ją. A jak tutaj być takim wrednym żółwiem (krok 5ty), który miałby być gdzieś u góry wieży?

nathaniel

liffe

o, kurczę... zwykle patrzę na termin tylko jeden raz... teraz też tak... No to jeszcze mam szansę :)

kafex

Szkoda ci setnych punkta ? ;]

jagm