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

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.

Dzięki za odpowiedź.

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

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

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 :/

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.