Fişierul intrare/ieşire:cuvinte3.in, cuvinte3.outSursă.campion 2008, Runda 12
AutorMircea Bogdan PasoiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cuvinte 3

Fie C o multime de cuvinte, toate de o lungime fixa L. Spunem ca un sir de caractere S poate fi scris folosind multimea de cuvinte C, daca pentru orice caracter din S exista o secventa de L caractere din S, care este un cuvant din C si care contine caracterul respectiv.
Se da un sir de caractere S format numai din litere din alfabetul englez, in care marimea literelor alterneaza (Exemple: aBcDeF, AbCd). Sa se determine o multime C de cardinal minim care contine numai cuvinte de lungime 2, multime cu care poate fi scris sirul S.

Date de intrare

Pe prima linie a fisierului de intrare cuvinte3.in se va gasi sirul S.

Date de iesire

Prima linie a fisierului cuvinte3.out va contine un singur numar natural min reprezentand cardinalul minim al multimii C. Urmatoarele min linii vor contine cate un cuvant de lungime 2 din multimea C determinata. Cuvintele se vor afisa in ordine alfabetica.

Restrictii

  • Lungimea sirului S este mai mica sau egala cu 100 000
  • Se considera ca a < b < ... < z < A < B < ... < Z
  • C, fiind o multime, va fi formata numai din cuvinte distincte
  • Daca exista mai multe seturi de cardinal minim se va afisa acela care este minim lexicografic. Spunem ca un set A=(A1,A2...AN) de cuvinte este mai mic decat un set B=(B1,B2...BN) daca exista o pozitie 1 ≤ i ≤ N astfel incat A1=B1, A2=B2 ... Ai-1=Bi-1 si Ai<Bi.

Exemplu

cuvinte3.incuvinte3.out
aAaAbAbAbBbB
3
aA
bA
bB
pQpQ
1
pQ
LoL
2
oL
Lo

Explicatie

Pentru primul test, o alta solutie, mai mare din punct de vedere lexicografic, este:
aA
bB
Ab

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content