# Herbata

## Zadanie
Mamy ciąg objętości kubków z herbatą $v_1, \ldots, v_n \in \mathbb{Z}$ i odpowiadające im temperatury początkowe $p_1, \ldots, p_n$ i końcowe $k_1, \ldots, k_n$. Mamy dostępne dwie operacje:
1. łącz($(v_i, t_i), (v_j, t_j)$), która bierze dwa kubki o objętościach $v_i, v_j$ i temperaturach $t_i, t_j$ i zwraca jeden kubek o objętości $v_i+v_j$ i średniej ważonej temperatur.
2. dziel($(v_i, t_i), k$), $0 < k < v_i, k\in \mathbb{R}$, która z jednego kubka o objętości $v_i$ i temperaturze $t_i$ robi dwa, o objętościach $k$ i $v_i$ i tej samej temperaturze $t_i$.

Pytanie w zadaniu to czy za pomocą skończonej liczby operacji i zamiany kubków miejscami w ciągu można przekształcić początkowy ciąg kubków na końcowy.

Zauważmy, że dla dwóch kubków $i, j$ o różnych temperaturach możemy zdefiniować operację przelej($i, j$), która zachowa ich objętość, a sprawi, że cieplejszy kubek stanie się chłodniejszy, a chłodniejszy cieplejszy: dzielimy chłodniejszy kubek na pół, łączymy połowę z cieplejszym, dzielimy powstały kubek na trzy części, jedną z nich łączymy z pozostałą połową a dwie ze sobą. Można w ten sposób wymienić dowolnie mało energii (dzieląc chłodniejszy kubek na nierówne części).

## Rozwiązanie
Dla uproszczenia zapisu załóżmy, że $\forall_i v_i = 1$: jako początkowe operacje możemy podzielić każdy $i$-ty kubek na $v_i$ kubków o objętości $1$. Dzieje się to bez straty ogólności, bo dzielenie kubków można odwrócić: jeśli istniał ciąg operacji $C$, dla który przekształcał oryginalne kubki początkowe na końcowe, to po wykonaniu podziału na kubki unitarne da się je przekształcić zgodnie z zasadami: wystarczy je połączyć spowrotem, wykonać $C$, a następnie podzielić końcowe kubki na unitarne. Jeśli nie istniał ciąg $C$, to nie istnieje ciąg $D$ dla unitarnych kubków: gdyby $D$ istniał, można zdefiniować $C$ przez dzielenie i łączenie jak powyżej.

Dalej, ponieważ kubki można zamieniać miejscami i mają tę samą objętość, ustalmy $p_0 \le p_1 \le \ldots \le p_n$ i $k_0 \le k_1 \le \ldots \le k_n$.

Nazwijmy $a_0 \le a_1 \le \ldots \le a_n$ dowolny ciąg temperatur, który możemy uzyskać z początkowych kubków przy założeniu, że kubki $a_i$ też mają unitarną objętość.

Zadanie polega na ustaleniu, czy da się osiągnąć ciąg $\forall_i a_i = k_i$. Rozwiążmy prostsze zadanie: czy da się osiągnąć ciąg $\forall_i a_i \le k_i$. Twierdzenie w drugą stronę jest analogiczne.

### Twierdzenie
Twierdzenie jest takie, że da się doprowadzić do takiego ciągu $a_i$ wtedy i tylko wtedy, gdy aktualnie nasz ciąg $b_n$ spełnia:
$$
\forall_m \frac{1}{m}\sum_{i=0}^{m-1} b_i \le \frac{1}{m} \sum_{i=0}^{m-1} k_i
$$
czyli w szczególności zadanie da się rozwiązać, gdy ciąg $p_n$ spełnia ww. nierówność (w miejsce $b_n$).

Jest stosunkowo jasne, że jest to warunek konieczny: jeśli dla jakiegoś $m$ nie jest spełniony to znaczy, że średnia temperatura najzimniejszych $m$ litrów jest początkowo większa niż powinna być na końcu, a żadna z operacji nie zmniejsza średniej temperatury najzimniejszych $m$ litrów herbaty (mieszanie z cieplejszą ją tylko ogrzeje).

Fakt, że jest to warunek wystarczający udowodnię niewprost: załóżmy, że nierówność jest spełniona to znaczy mam ciąg $b_n$, który ją spełnia, ale wciąż nie da się go przekształcić do $a_i \le k_i$, a więc dla każdego możliwego ciągu $b_n$ do którego da się doprowadzić, $\exists_i b_i > k_i$. Weźmy taki ciąg $b_n$, że $i$ jest najmniejsze możliwe, czyli pozycja, na której jest nadwyżka temperatury jest jak najwcześniej.

Jeśli $i=0$, nierówność nie jest spełniona dla $m=1$, sprzeczność z założeniem. A więc $i > 0$.

Niech $B = \sum_{j=0}^{i-1} k_j - b_j$. Z twierdzenia mamy $B \ge 0$.
Albo $b_i - k_i > B$ albo nie.

Jeśli $b_i - k_i > B$, to:
$$b_i - k_i - B = \sum_{j=0}^i b_j - k_j > 0 \Rightarrow \sum_{j=0}^i b_j > \sum_{j=0}^i k_j
$$
sprzeczność z założeniem.

A więc $b_i - k_i \le B$. Z założenia niewprost $b_i - k_i > 0$, a więc $B>0$. Wykonujemy następujące operacje na ciągu $b_i$:
1. przelewamy $X_{i-1} = min(b_i - k_i, k_{i-1} - b_{i-1}) \ge 0$ energii z kubka $b_i$ do $b_{i-1}$.

Jeśli $X_{i-1} = b_i - k_i \le k_i - b_i$, to otrzymamy ciąg w którym $b_i = k_i$ oraz $b_{i-1} \le b_i$, (bo $b_{i-1} \le k_{i-1} \le k_i = b_i$) a więc sprzeczność z założeniem niewprost.

Jeżeli $X_{i-1} = k_{i-1} - b_{i-1}$, to $b_{i-1} = k_{i-1}$, zachowując $b_{i-1} \le b_i$ (bo $b_{i-1} = k_{i-1} \le k_i < b_i$) oraz $b_i > k_i$. Przechodzimy wtedy do kolejnej operacji:
1. przelewamy $X_{i-2} = min(b_i - k_i, k_{i-2} - b_{i-2}) \ge 0$ energii z kubka $b_i$ do $b_{i-2}$.

Analogicznie, jeśli $X_{i-2} = b_i - k_i$ to dostajemy ciąg spełniający $b_i \le k_i$.

Jeśli nie, to $X_{i-2} = k_{i-2} - b_{i-2}$. Z założenia indukcyjnego $b_{i-1} = k_{i-1}$, a więc $b_{i-2} = k_{i-2} \le k_{i-1} = b_{i-1}$.

Powtarzając tę operację dla wszystkich $j < i$, przelejemy $\sum X_{j} = B$ energii: sprzeczność z $B < b_i - k_i$.