}
        return num[step][(1 << w) - 1];
    }

}

==
* În $num[i][config]$ ţinem minte câte posibilităţi sunt să acoperim $i - 1$ linii cu piesele date în problemă, iar linia $i$ să fie ocupată aşa cum arată reprezentarea în baza $2$ a numărului întreg $config$. Se observă folosirea variabilei $step$ care de la un pas la altul se transformă astfel $step ^= 1$, aceast mic truc ne face să putem folosi o matrice de doar $2$ linii în loc să folosim $N$ linii. La momentul $i$, în $num[step][config]$ avem informaţia ce ar fi fost în mod normal în $num[i][config]$, iar în $num[1 ^ step][config1]$ vom calcula ce ar fi fost normal în $num[i + 1][config1]$. În şirul $p$ ţinem minte forma pieselor din problemă.
* În procedura $doit$ punem pe două linii consecutive piese în toate modurile posibile. Această procedură face ca pe prima linie să avem o configuraţie de pătrăţele libere $config$ şi o configuraţie de pătrăţele ocupate pe a doua linie $config1$. Dacă pătrăţelele reprezentate de $config$ nu au fost ocupate la pasul curent ele trebuie să fi fost ocupate la pasul anterior. Astfel, pentru fiecare pereche de configuraţii $config$ şi $config1$ trebuie să efectuăm operaţia $num[i + 1][config1] += num[i][config]$.
* Dacă această rezolvare ar fi fost folosită în timpul concursului ea ar fi ieşit din timp. Pentru optimizarea ei putem face mai multe optimizări. Un exemplu ar fi să generăm direct cele două configuraţii de biţi în procedura $backtraking$ şi să nu mai folosim şirul $sol$. O altă idee care ar fi dus la rezolvarea problemei ar fi fost calcularea tuturor rezultatelor posibile în timpul concursului şi trimiterea unei soluţii care returna aceste rezultate precalculate. Această abordare ar fi fost posibilă pentru că numărul de configuraţii iniţiale este mic.

* Menţionăm că această problemă a apărut ca întrebare la miniconcursul online de pe forumul "GInfo":http://www.ginfo.ro.
 
 
 
 
 

* Menţionăm că această problemă a apărut ca întrebare la miniconcursul online de pe forumul "GInfo":http://www.ginfo.ro.