semipal

Por Costel si Semipalindroamele

== include(page="template/taskheader" task_id="semipal") ==

Poveste şi cerinţă...

%{float: right;}!problema/semipal?por_costel_computer.jpg! %
 
Programatorul nostru in devenire, Por Costel, tocmai s-a intors din tabara de programare de la Petrozaporksk. Acolo a invatat multe lucruri: cum sa fiarba un cocean de porumb, cum sa foloseasca tastatura sa se scarpine pe burta etc. Parca isi aminteste si o problema de programare:
 
Se defineste un semipalindrom ca fiind un cuvant c pentru care exista un subcuvant <tex>w</tex> astfel incat <tex>w</tex> este prefix al lui <tex>c</tex> iar <tex>w_r</tex>(cuvantul invers) este suffix al lui <tex>c</tex>.
 
De exemplu ‘ababba’ este semipalindrom deoarece exista un subcuvant ‘ab’ prefix al cuvantului iar ‘ba’ este sufix al cuvantului.
 
Considerand doar semipalindroamele care contin literele ‘a’ si ‘b’, problema cerea sa gasiti al <tex>K</tex>-lea lexicografic semipalindrom de lungime <tex>N</tex>.
Por Costel nu isi aminteste daca enuntul era exact asa la Petrozaporksk, dar totusi problema i se pare interesanta si va roaga sa il ajutati cu ea.
 

h2. Date de intrare

Fişierul de intrare $semipal.in$ ...

Fişierul de intrare $semipal.in$ va contine pe prima linie numarul <tex>T</tex>, numarul de teste, iar pe urmatoarele <tex>T</tex> linii cate doua numere, <tex>N</tex> si <tex>K</tex>.

h2. Date de ieşire

În fişierul de ieşire $semipal.out$ ...

În fişierul de ieşire $semipal.out$ va contine <tex>T</tex> linii, pe linia <tex>i</tex> aflanduse raspunsul la al <tex>i</tex>-lea test.

h2. Restricţii

* $... ≤ ... ≤ ...$

* <tex>1</tex> &le; <tex>T</tex> &le; <tex>3000</tex>
* <tex>2</tex> &le; <tex>N</tex> &le; <tex>63</tex>
* <tex>1</tex> &le; <tex>K</tex> &le; numarul de semipalindroame de lungime <tex>N</tex>

h2. Exemplu
table(example). |_. semipal.in |_. semipal.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
5 1
5 14
| aaaaa
bbabb

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="semipal") ==

10329