Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | decod.in, decod.out | Sursă | ONI 2009, Baraj Gimnaziu |
| Autor | Ana Intuneric | Adăugată de |  Andrici Cezar •andrici_cezar |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 4736 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Decod
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:
a) cunoscând numerele k , p şi un α-cod , determină k-p-platoul căruia i s-a aplicat α-codificarea .
b) 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 800000 de caractere
Exemplu
| decod.in | decod.out |
|---|---|
| 3 5 12124 1111012124100111234511151 | 57346 20 |
Explicaţie
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 .
| decod.in | decod.out |
|---|---|
| 8 2 12 10121011101012101110111011101110 | 89 20 |
Explicaţie
Numărul 12 este un α-cod a numărului 89.
În şirul 10121011101011101110111011201110 avem două valuri, iar valul maxim are lungimea egală cu 20.
