Racja. W ferworze walki z innymi zadaniami przeoczyłem fakt, że uczniowie są już ustawieni w szereg i myślałem, że sami możemy ustawić ich w dowolnej kolejności.

Dziękuję za wyjaśnienie :-)

Musisz jednak stworzyć taki podział na drużyny, w której członkowie poszczególnych drużyn będą _obok siebie_. Tak więc nie możesz zrobić grupy zawierającej np. drugą i szóstą osobę.

Nietrudno zauważyć, że są 2 możliwości wybrania 5 sąsiadujących drużyn:
(1 2 3) (4) (5) (6 7 8) (9)
(1) (2 3 4) (5) (6 7 8) (9)

Dzięki za odpowiedź.

Czy ktoś mógłby mi wyjaśnić, dlaczego w przykładzie z zadania maksymalna liczba drużyn wynosi 5?

Przecież wśród 9 uczniów jest pięcioro takich, którzy akceptują drużyny 1-osobowe, natomiast pozostałych czterech uczniów akceptuje drużynę 4-osobową. Mamy zatem podział na 6 drużyn...

Potwierdzam :)

Można udowodnić, że jeśli istnieje jakakolwiek poprawna kolejność pokonywania potworów, to podana poniżej kolejność też jest poprawna.

Zatem wystarczy sprawdzić poniższą kolejność i jeśli jest OK to ją wypisać, a jeśli nie jest, to żadna kolejność nie jest poprawna.

Kolejność o której mowa jest taka:
* w pierwszej kolejności potwory pozytywne (czyli takie, które zabierają nie więcej życia niż później dają)
* na końcu potwory negatywne (czyli takie, które zabierają więcej życia niż później dają).
* wśród potworów pozytywnych w pierwszej kolejności te, które zabierają mniej życia - w przypadku takiej samej liczby zabieranego życia kolejność dowolna
* wśród potworów negatywnych w pierwszej kolejności te, które dają więcej życia - w przypadku takiej samej liczby dawanego życia kolejność dowolna.

słabe limity, u mnie 10f 2.94/15s
Szkoda, że tak mała różnica punktowa między O(n^2 2^n) a wzorcówką :/

Jaka była wzorcówka? Mógłby ktoś opisać?

To ja dorzucę dwa nieco bardziej losowe testy.

http://speedy.sh/B5hC5/dru-tests.tar.gz

Moje outy:
drut.in --> 1757 954565754
drun.in --> NIE

Ktoś jest w stanie potwierdzić?

Jedno z moich n^2*2^n przeszło na 10 i to wcale nie na styk :)
Z tego co widziałem to bardzo dużo mu dawało przesortowanie przedmiotów rosnąco.

Hej,
polecicie jakieś fora? Powiedzmy, że chciałbym tam zapytać o wskazówki rozwiązania któregoś z archiwalnych zadań (forum potyczek byłoby super, gdyby nie to, że istnieje krócej niż miesiąc w ciągu roku :))

Dało się na 9 (tak mój pierwszy submit punktował).

Ale potem poprawiłem i u mnie chodziło ~30-40% szybciej, ale u nich 1.1 do 3 razy wolniej... i ostatecznie dostałem tylko 8 pkt. Może jakieś kwestie innego rozmiaru cache'a albo coś, a może sam źle pomierzyłem se czasy... no cóż trudno konkursować i pracować jednocześnie (szczególnie jak i tak do finału się nie zakwalifikuje...).

W każdym razie za O(N**2 * 2**N) dało się 9 pkt uzyskać.
W pierwszym submicie tylko 10-ty test mi uwaliło i to tylko na 3 podtestach [10b, 10e, 10f], być może dałoby się to trochę jeszcze wyżyłować i zaliczyć na 10 (choć 10a mi rozwiązywało też bardzo na styk: 14.17s/15s, i 9a: 4.42s/5s).

Update:

rozwiązanie O(N**2 * 2**N) za 9 pkt, oficjalne czasy:
0..9 OK
10a OK 14.17s/15.00s
10b TLE 15.12s/15.00s
10c OK 5.42s/15.00s
10d OK 3.10s/15.00s
10e TLE 15.14s/15.00s
10f TLE 15.11s/15.00s

Ile chodzi u mnie [i5-2520M CPU @ 2.50GHz, 3MB cache]:
Test 10a: 6.315s
Test 10b: 8.542s
Test 10c: 2.450s
Test 10d: 1.415s
Test 10e: 7.929s
Test 10f: 7.094s

Jak widać jakoś 2.25 razy szybciej.
Wniosek: 8.5s u mnie to pewnie ~19.1s czasu oficjalnego.

Nie wiem czy aż 25% czasu dałoby się jeszcze z tego wyżyłować...
Być może? Trzeba by pewnie trochę pokombinować...

Potwierdzam wszystkie testy. (zzz...)

Także potwierdzam oba.

Potwierdzam wszystkie jak do tej pory.