== include(page="template/taskheader" task_id="decod") ==
Poveste şi cerinţă...
Numim $k-p-platou$ un număr $n$ de forma c{~1~}c{~2~}...c{~p~} 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 {$d{~1~}d{~2~}...d{~p~}$}, unde $d{~i~}$ = {$1+$}numărul de cifre din stânga cifrei c{~i~} care sunt mai mici decât $c{~i~}$ 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,…$ }.
h2. Cerinţe
Scrieţi un program care:
# cunoscând numerele {$k$}, $p$ şi un $α-cod$ , determină $k-p-platoul$ căruia $i$ s-a aplicat $α-codificarea$ .
# pentru un şir de cifre $s$ dat, determină lungimea celui mai lung $val$ .
h2. Date de intrare
Fişierul de intrare $decod.in$ ...
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$
h2. Date de ieşire
În fişierul de ieşire $decod.out$ ...
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$
h2. Restricţii
* $... ≤ ... ≤ ...$
* {$1 ≤ k ≤ 9$}
* {$1 ≤ p ≤ 9$}
* {$k+p-1 ≤ 9$}
* {$1 ≤ di ≤ 9$}
* şirul $s$ are cel mult $800.000$ de caractere
h2. Exemplu
table(example). |_. decod.in |_. decod.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 5
12124
1111012124100111234511151
|57346
20
|
| 8 2
12
10121011101012101110111011101110
|89
20
|
h3. 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 11110{*12124{+10011+}{*12345*}{+11151+}*} avem un val de lungime 20.
# Numărul $12$ este un α-cod a numărului $89$. În şirul 10{*12{+10+}{*11*}{+10+}*}10{*11{+10+}{*11*}{+10+}{*11*}{+10+}{*11*}{+20+}{*11*}{+10+}*} avem două valuri, iar valul maxim are lungimea egală cu $20$.
== include(page="template/taskfooter" task_id="decod") ==
