Potwierdzam wszystko i dorzucam od siebie mały teścik, w którym samochodziki są ostro nadziubdziane obok siebie :D
http://www69.zippyshare.com/v/54179416/file.html

Potwierdzam wszystko i dorzucam coś od siebie:
http://students.mimuw.edu.pl/~kl319367//dru_max2.in
http://students.mimuw.edu.pl/~kl319367//dru_max2.out

Mogę prosić o małe testy na NIE?

http://pastebin.com/7S5PByW4

W skrócie:
Dla ustalonej liczby plecaków próbuję pakować plecaki od najmniejszego. W jednym ruchu pakuję od razu cały plecak pewnym podzbiorem przedmiotów, przy czym:
- do danego plecaka pakuję tylko maksymalne ze względu na zawieranie podzbiory, które się w nim mieszczą
- jeżeli dla plecaka istnieje para podzbiorów tej samej mocy, które różnią się dokładnie jednym elementem to nie sprawdzam tego o mniejszej wadze
- podzbiory sprawdzam w kolejności malejącej ze względu na pary (liczba przedmiotów, łączna waga)
- obcinam jak wiem że w pozostałych plecakach zabraknie mi miejsca na resztę przedmiotów.

Czasami na max testach przeszukiwanie trwało zbyt długo dla liczby plecaków za małej o 1, wtedy po przekroczeniu limitu iteracji zakładałem, że się nie da. Porównując 2 ostatnie zgłoszenia, tylko na teście 10e miałem taką sytuację.

Wystarczające jak się wie jak zrobić:) Musiałem się wczoraj trochę pogapić na ten kod aby go rozszyfrować i zrozumieć;)
Było parę innych metod. Np chciałbym zobaczyć, jak wygląda dobry backtrack dla tego zadania - Piotrowi taka metoda weszła 10/10. Obejrzenie heurystyk też może być ciekawe.

również potwierdzam

Nazwijmy opisaną przeze mnie kolejność "idealną". Załóżmy, że mamy dowolną poprawną kolejność walki z potworami.
Dopóki potrafimy znaleźć parę sąsiadujących potworów P i Q (P jest przed Q) takie, że w kolejności idealnej Q występuje przed P, dopóty dokonujemy zmianę kolejności potworów P i Q (za chwilę dowód, że taka zmiana jest ok). Gdy nie znajdziemy pary potworów P i Q, to mamy kolejność idealną.

Niech z będzie liczbą jednostek życia przed walką z potworem P. P = (a, b), tzn. aby pokonać potwora P najpierw tracimy a jednostek życia, a po wygranej otrzymujemy b jednostek życia. Podobnie Q = (c, d).

Ciąg z, z-a, z-a+b, z-a+b-c, z-a+b-c+d obrazuje stan życia przed walką z P, bezpośrednio po walce z P (ale przed regeneracją), stan po regeneracji po walce z P, stan po walce z Q (przed regeneracją) i stan po walce z Q.
Gdy zmienimy kolejność potworów otrzymamy analogiczny ciąg: z, z-c, z-c+d, z-c+d-a, z-c+d-a+b.

Ponieważ początkowa kolejność była poprawna zatem wiemy, że z-a > 0 oraz z-a+b-c > 0.
Wystarczy udowodnić, że po zamianie potworów wartości z-c oraz z-c+d-a są dodatnie.


1 przypadek: P jest negatywny (czyli a>b), Q jest pozytywny (czyli c<=d)

z-c = (z-a+b-c) + (a-b) > 0, bo z-a+b-c > 0 oraz a > b
z-c+d-a = (z-a) + (d-c) > 0, bo z-a > 0 oraz d >= c

2 przypadek: P i Q są pozytywne (czyli a <= b, c <= d) oraz P zżera więcej życia (tzn. a > c)
z-c > z-a > 0, bo a > c, tzn. -c > -a
z-c+d-a = (z-a) + (d-c) > 0, bo z-a > 0 oraz d >= c

3 przypadek: P i Q są negatywne (czyli a > b, c > d) oraz P daje mniej życia niż Q (tzn. b < d)
z-c = (z-a+b-c) + (a-b) > 0, bo z-a+b-c > 0 oraz a > b
z-c+d-a = (z-a+b-c) + (d-b) > 0, bo z-a+b-c > 0 oraz d > b.

Wydawało mi się, że już rzuciłem kodem. Tam jest raptem kilkanaście linii do "analizowania", a opis "Dynamik po podzbiorach, dla każdego wyliczasz ile musisz wziąć plecków i ile miejsca zostaje w ostatnim. I wychodzi O(n * 2^n). " praktycznie wyczerpuje temat.

Edit: No właśnie ;)

Zaczynasz od jakiegoś żyćka. Jeśli możesz wstawić jakiegokolwiek potwora, to możesz wstawić najmniejszego. Potwór ma bilans leczący, więc niczego nie popsujesz. Załóżmy, że nie możesz wstawić k-tego (w zaproponowanym sortowaniu po obrażeniach) potwora. Czy dałoby się zmienić kolejność tak, aby jednak go wstawić? Nie, ponieważ kolejność potworów przed tą walką nie gra roli, bilans jest taki sam. Żaden potworów ustawionych za k-tym nie może walczyć wcześniej, bo ma niemniejsze obrażenia. Nie może więc walczyć w chwili k, nie może też walczyć wcześniej, bo z założenia o dodatnim bilansie potworów mieliśmy wtedy jeszcze mniej HPków.

Na potwory o ujemnym bilansie patrzymy tak samo, tylko jedziemy od końcowego życia (początkowe - obrażenia + miksturki) i zamieniamy rolami obrażenia i leczenia (jadąc palcem po wykresie zdrowia od tyłu to leczenia powodują spadek, a obrażenia wzrost funkcji).

BTW, 100 000* 100 000 > maxint i kosztuje to 2 punkty :/

Random też dawał niemało punktów, bo aż 6 maksymalny czas 0.24s/15.00s.

dokładnie 256 osób ma w rankingu B nie mniej niż 8. liczba pierwsza punktów.

Rozumiem, że nie chce się nikomu opisywać szczegółowiej rozwiązanie, ale rzućcie kodami rozwiązań na 8-10;)
U mnie kiepski backtracking z limitem iteracji (zwraca najlepsze co znalazł) prostą heurystyką od góry (pakuj pierwsze co pasuje) i dolnym oszacowaniem "L2" stąd http://www.or.deis.unibo.it/kp/Chapter8.pdf Pewnie jakby zaimplementować całość z tej pracy działałoby lepiej (tylko być może, bo tam plecaki są równej wielkości) a tak 4 punkty (mogło być 5 jakbym limitów nie podbił:)


Edit: Jest rozwiązanie oficjalne, dynamiczne, takie jak w podanym przez Przemysława kodzie.
https://www.youtube.com/watch?v=-b1WqgSr2vk

Potwierdzam :)

w sumie wystarczy udowodnić, że takowe fakty można udowodnić

"Można udowodnić" brzmi jak słowo klucz w tym zadaniu. W szczególności kawałek "Można".