Czy mógłby ktoś się podzielić swoim rozwiązaniem do herbaty?
Z góry dzięki.

Sprawdzam, czy dla każdego k: k najzimniejszych litrów herbaty w stanie początkowym ma co najwyżej taką samą ważoną sumę temperatur jak w stanie końcowym oraz, czy ważona suma całości jest taka sama przed i po. Jak tak, to się da, jak nie, to nie.
Przez ważoną sumę rozumiem: suma po różnych kubkach: temperatura * objętość

Właśnie zrobiłem coś podobnego, ale albo zwaliłem implementację, albo czegoś nie uwzględniłem - 5/10.

Edit: pozdrawiam long longi... :C

long longi?

Polecam flagę -fsanitize=undefined

Ładnie graficznie można to sobie zinterpretować tak:
Zróbmy wykres objętość->energia (energia to objetość * temperatura ).
Zróbmy łamaną składając się z kolejnych wektorów odpowiadających kubkom, posortowanym malejąco po temperaturze:
(zaznaczamy 0, mając kubek t=50, v=2 punkt to 2,100, łączymy go linią, drugi kubek to np t=20, v=2, czyli energia 40, wiec kolejnym punktem łamanej będzie 4,140).
Teraz, da sie rozlać wtedy i tylko wtedy, gdy oba wykresy
-kończą w tym samym punkcie.
-wykres zamówionych herbatek zawsze jest pod wykresem rozlanych herbatek.
(przypominam, że maja być posortowane po temperaturze, wtedy wykresy to ładne łamane łuki).

Oprócz sortowania sprawdzanie jest liniowe, dla każdego punktu wykresu zamówionych odczytuje sobie wartość na drugim wykresie (interpolując między punktami).
I tu wchodzi zapotrzebowanie na int64_t. Nie tylko energia takiej zmiennej potrzebuje, ale i objętość może 2^32 przekroczyć;-)

Sprawdziłem liniowo, również pozdrawiam long longi...

Ciekawostka: dla dowolnej funkcji wypukłej f suma po wszystkich kubkach pojemność * f(temperatura) tylko maleje z czasem (jak robimy dzielenie, to wartość ta się nie zmienia, jak mieszanie, to z wypukłości maleje). Zatem jeżeli jest spełniony warunek, że zawsze k najzimniejszych litrów herbaty ma łączną energię mniejszą w stanie początkowym niż w końcowym, to zachodzi nierówność między tymi sumami, a dokładnie to mówi nierówność Karamaty.

Ja zapomniałem o long longu w jednym miejscu. Także pozdrawiam.

To ja jeszcze tylko dodam, że zrobiłem bardzo nieprzyzwoicie, czyli na double'ach, symulując rozlewanie herbaty od najgorętszego docelowego kubka, zakładając, że każdy docelowy kubek opłaca się wypełniać z kubków o najbliższej mu temperaturze.

Niestety źle ustaliłem numeryczny ε (1e-11), więc 9/10. Przy 1e-10 byłoby 10/10 :-)