Fişierul intrare/ieşire:ppal.in, ppal.outSursăLot Cluj 2009, Baraj 4
AutorZoltan SzaboAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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ă:

  1. a b b bab aca
  2. a bbb a b aca
  3. a bbb aba c a
  4. 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.inppal.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content