\begin{yl}{4}{Kõrgeim torn}{torn}{1 sek / 3 sek}{60 punkti}
\emph{Idee, teostus ja lahenduse selgitus: Semjon/Sona Kravtšenko}

\begin{quote}
Antud risttahukakujuliste klotside jada pikkusega $N \le 1\,000$.
Leida maksimaalse kindlalt püsiva ortogonaalselt pööratud klotside osajadast (samas järjekorras) torni kõrgus.
Alamülesanded: $N \le 12$ ja/või kõik klotsid on kuubid.
\end{quote}

Naiivne viis selle ülesande lahendamiseks on vaadata läbi kõik klotside osajadad koos kõikide klotside orientatsioonidega,
jättes vahele need kombinatsioonid, mis ei anna kindlalt püsivat torni. Läbivaatuseks sobib hästi rekursioon, kuna siis pole vaja kirjutada koodi, mis genereerib kõiki osajadasid ja orientatsioone, vaid piisab kirjeldamisest, milliseid
tehteid saab ühe klotsiga teha. Rekursiooni tehes tuleb pidada meeles praeguse toetuspinna mõõtmeid (alguses laua mõõdud)
ja praegust torni kõrgust (alguses $0$).
Olgu käesoleva klotsi mõõdud $A_i$, $B_i$ ja $C_i$, praeguse toetuspinna mõõdud $(X, Y)$ ning senini ehitatud torni kõrgus $H$.
Osutub, et saab teha neli tehet:
\begin{xenum}
    \item Kasutada klotsi nii, et uus torni kõrgus oleks $H + A_i$. Siis on toetuspind $(B_i, C_i)$.
          See on lubatud vaid siis, kui tahk mõõtudega $(B_i, C_i)$ mahub alale $(X, Y)$.
          Kuna mitte-ortogonaalne keeramine pole lubatud, mahub tahk alale üksnes juhul,
          kui ala pikem serv pole väiksem tahu pikemast servast ning ka ala laua lühem serv pole väiksem tahu lühemast servast.
    \item Uus torni kõrgus on $H + B_i$ ja uus toetuspind $(A_i, C_i)$. See on lubatud vaid siis, kui $(A_i, C_i)$ mahub $(X, Y)$-sse.
    \item Uus kõrgus on $H + C_i$ ja uus toetuspind $(A_i, B_i)$. Lubatud, kui $(A_i, B_i)$ mahub $(X, Y)$-sse.
    \item Klots jäetakse vahele. Torni kõrgus ega toetuspind ei muutu.
\end{xenum}
See lahendusviis on piisav, alamülesannetes $1$ ja $2$, kuna (sõltuvalt detailidest) võib selle keerukus olla näiteks $O(4^{N})$.
Üks võimalik implementatsioon on toodud failis \verb'sol_comb.cpp'.

Kuna paigutamise lubatavuse kontroll on keeruline, on ülesandes alamülesannetes $1$ ja $3$ sätestatud, et $A_i = B_i = C_i$.
See tähendab, et kõik klotsid on kuubid. Siis mahub üks klots teise peale, kui alumise klotsi mõõt pole väiksem kui ülemise klotsi mõõt.
Esimese klotsi puhul tuleb selle mõõtu võrrelda laua lühema servaga, nagu on tehtud failis \verb'sol_comb_cube.cpp'.

Täislahendus eeldab, et klotsi paigutamist tuleb katsetada vaid üks kord. Selleks tuleb määrata, millised on maksimaalsed võimalikud tornide kõrgused, kui klots on asetatud
tahule $(A_i, B_i)$, $(A_i, C_i)$ või $(B_i, C_i)$. Selleks võib vaadata läbi kõik juba saavutatud olekud $(H, X, Y)$ (mida peab jooksvalt salvestama).
Esimene salvestatud olek on $(0, W, L)$, kus $W$ ja $L$ on laua mõõdud.
Kui iga klotsi orientatsiooni kohta salvestada vaid parema kõrgusega olekuid, tekitab iga klots ülimalt $3$ uut salvestatud olekut, mida tuleb iga järgmise klotsi paigutamiseks läbi vaadata.
Seega selle lahenduse keerukus on $O(N^2)$.
Lisaks tuleb hoolikalt jälgida, et mitte salvestada uut olekut juhul, kus klotsi ei õnnestunudki ühelegi varasemale olekule paigutada, ning ka seda, et
klotsi ei lisataks olekule, mis on saavutatud sama klotsi endaga (ehk klotsi ei tohi panna iseenda peale).
Täislahenduse üks võimalik implementatsioon on toodud failis \verb'sol.cpp' ning samal ideel põhinev lahendus, mis töötab vaid kuupide jaoks, on failis \verb'sol_cube.cpp'.

Boonusülesanne: kirjutada $O(N \cdot \log(N))$ programm, mis lahendab sama ülesannet kuupide jaoks.

Lisaküsimus: kuidas tuleb lahendust muuta, et see lubaks klotse panna mitte-ortogonaalselt (st. mistahes nurga all)?

Veel üks lisaküsimus: kas on võimalik seda lahendust kohandada viiemõõtmelistest klotsidest torni kõrguse leidmiseks?
Mitme mõõtmeline on sel juhul laua ``pindala''?

\end{yl}
