Runda 3: Magiczny prostokąt (rozwiązanie)

Autor zadania: Mateusz Piwnicki

Zauważmy, że dużo prościej będzie patrzeć na problem, jeśli założymy, że liczby wpisywane są w prostokat w kolejnosci rosnacej (pomijajac liczby juz wpisane). Dalej, oczywiscie chcielibyśmy, aby w kazdym
wierszu wpisane liczby tworzyly spojny fragment - jesliby tak nie bylo, wpisane liczby nie spelniałyby naszych warunkow.

Stąd możemy opisać stan problemu trzema liczbami. Wystarczy, że bedziemy wiedzieć, ile liczb wpisaliśmy do kazdego z wierszy. Jesli do wiersza pierwszego wpisalismy a liczb, do drugiego - b liczb, natomiast do trzeciego - c, to nastepna wpisywana liczba bedzie a + b + c + 1. Musimy podjac decyzje, do ktorego wiersza chcemy ja wpisac. Od razu nasuwa sie tutaj metoda programowania dynamicznego. Niech A[a][b][c] oznacza na ile sposobow mozemy wypelnic reszte prostokata, jesli w pierwszym wierszu
wpisalismy juz a liczb, w drugim - c, a w trzecim - c.

Wówczas A[a][b][c] = A[a + 1][b][c] + A[a][b + 1][c] + A[a][b][c + 1]. Oczywiscie przyjmujemy, ze A[n][n][n] = 1. Musimy tez pamietac, aby zawsze zachodzilo a >= b >= c. Rozwiazanie problemu to A[0][0][0]. Jedyne, z czym jeszcze trzeba sobie poradzic, to juz wpisane liczby. Mozemy jednak na bieżżco sprawdzac zgodność wpisywanych liczb z tymi bedacymi w prostokącie od początku.