Fişierul intrare/ieşire:decod.in, decod.outSursăONI 2009 baraj gimnaziu
AutorAna IntunericAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.15 secLimită de memorie640 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Decod (baraj gimnaziu)

Numim k-p-platou un număr n de forma c1c2...cp cu proprietatea că cifrele sale sunt distincte şi aparţin mulţimii { k,k+1,...,k+p-1 }. O α-codificare constă în transformarea numărului n în numărul d1d2...dp, unde di = 1+numărul de cifre din stânga cifrei ci care sunt mai mici decât ci pentru 1 ≤ i ≤ p. Aplicând o α-codificare unui număr obţinem un α-cod. Fie s un şir format din secvenţe de cifre, în care fiecare secvenţă are aceeaşi lungime p. Un val este o succesiune de astfel de secvenţe în care orice secvenţă care este un α-cod, este urmată de o secvenţă care nu este un α-cod şi orice secvenţă care nu este un α-cod, este urmată de o secvenţă care este un α-cod, cu excepţia ultimei secvenţe. Un val începe obligatoriu cu o secvenţă ce reprezintă un α-cod şi se termină cu o secvenţă care nu este un α-cod. Primul caracter al unui val se poate afla pe o poziţie din s care aparţine mulţimii { 1, 1+p, 1+2p, 1+3p, … }.

Cerinţe

Scrieţi un program care:

1. cunoscând numerele k, p şi un α-cod, determină k-p-platoul căruia i s-a aplicat α-codificarea.
2. pentru un şir de cifre s dat, determină lungimea celui mai lung val .

Date de intrare

Fişierul de intrare decod.in conţine:

  • pe prima linie cifrele k şi p separate printr-un spaţiu;
  • pe a doua linie un α-cod a unui k-p-platou;
  • pe a treia linie un şir de cifre s.

Date de ieşire

Fişierul de ieşire decod.out va conţine:

  • pe prima linie k-p-platoul căruia i s-a aplicat α-codificarea;
  • pe a doua linie lungimea celui mai lung val.

Restricţii

  • 1 ≤ k ≤ 9;
  • 1 ≤ p ≤ 9;
  • k-p+1 ≤ 9;
  • 1 ≤ di ≤ 9;
  • şirul s are cel mult 800.000 de caractere.

Exemplu

decod.indecod.out
3 5
12124
1111012124100111234511151
57346
20
8 2
12
10121011101012101110111011101110
89
20

Explicaţie

1. Numărul 57346 este un 3-5-platou, deoarece cifrele sale aparţin mulţimii { 3, 4, 5, 6, 7 }. Aplicându-i o α-codificare se obţine 12124, 1 deoarece în stânga lui 5 nu există nici o cifră mai mică decât 5 ( 1+0 ), 2 deoarece în stânga lui 7 există o cifră mai mică decât 7 ( 1+1 ) etc. În şirul 1111012124100111234511151 avem un val de lungime 20.
2. Numărul 12 este un α-cod a numărului 89. În şirul 10121011101011101110111011201110 avem două valuri, iar valul maxim are lungimea egală cu 20.

Trebuie sa te autentifici pentru a trimite solutii. Click aici