== include(page="template/taskheader" task_id="ppal") ==
Un cuvânt format din literele mici ale alfabetului englezesc este palindrom dacă citind de la stânga la dreapta sau de la dreapta la stânga avem acelaşi cuvânt. De exemplu, $ghihg$ sau $lool$ sunt palindroame.
Să considerăm un şir format numai din litere mici ale alfabetului englez. În acest şir se pot introduce pe alocuri câte un spaţiu astfel încât să se transforme într-un text ce conţine doar cuvinte palindroame. De exemplu, $abbbabaca$ se poate despărţi în cuvinte palindrom în mai multe moduri, dintre care exemplificăm toate descompunerile în $5$ palindroame în ordine lexicografică:
# $a b b bab aca$
# $a bbb a b aca$
# $a bbb aba c a$
# $abbba b a c a$
Să considerăm toate descompunerile unui şir în exact $p$ palindroame, soluţiile obţinute fiind aranjate în ordine lexicografică. Caracterul $’ ’$ (spaţiu) este mai mic lexicografic decât orice literă.
h2. Cerinţă
Fiind date un şir de litere mici şi două numere naturale $p$, respectiv $q$, se cere să se determine descompunerea cu numărul de ordine $q$ din mulţimea tuturor soluţiilor ordonate lexicografic formate din $p$ palindroame.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $ppal.in$ conţine pe prima linie numărul natural $n$. Pe cea de a doua linie se află un şir de $n$ litere mici ale alfabetului englez. Începând cu linia a $3$-a până la sfârşitul fişierului fiecare linie conţine câte o pereche de numere naturale $p$ şi $q$ separate prin câte un spaţiu.
Fişierul de intrare $ppal.in$ ...
h2. Date de ieşire
Fişierul de ieşire $ppal.out$ va conţine pentru fiecare pereche de numere $p q$ a fişierului de intrare câte o linie pe care se va scrie descompunerea cu numărul de ordine $q$ din mulţimea tuturor soluţiilor formate din $p$ palindroame, aranjate lexicografic, sau $0$ (zero) în cazul în care soluţia cu numărul de ordine $q$ nu există.
În fişierul de ieşire $ppal.out$ ...
h2. Restricţii şi precizări
h2. Restricţii
* $0 < p ≤ n ≤ 500$
* $0 < q ≤ 10^18^ - 1$
* Numărul maxim de perechi $p q$ nu va depăşi $50 000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. ppal.in |_. ppal.out |
| 9
abbbabaca
5 3
5 1
5 5
3 1
3 2
| a bbb aba c a
a b b bab aca
0
abbba b aca
0
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Primele două rezulte corespund celei de a treia descompunere din exemplul anterior, respectiv a primei descompuneri din exemplul anterior. Pentru perechea $5 5$ nu există $5$ soluţii, deci se scrie $0$. Pentru perechea $3 1$ există o singură descompunere de $3$ palindroame. Pentru $3 2$ a doua soluţie nu există, deci se scrie $0$.
...
== include(page="template/taskfooter" task_id="ppal") ==
