| Fişierul intrare/ieşire: | ppal.in, ppal.out | Sursă | Lot Cluj 2009, Baraj 4 |
| Autor | Zoltan Szabo | Adăugată de |  Marius Stroe •Marius |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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ă.
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.
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.
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ă.
Restricţii şi precizări
- 0 < p ≤ n ≤ 500
- 0 < q ≤ 1018 - 1
- Numărul maxim de perechi p q nu va depăşi 50 000
Exemplu
| 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 |
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.
