decod

Decod

== include(page="template/taskheader" task_id="decod") ==

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,…$ }.

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:

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$ .

 
# 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$ 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$

 
* 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
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$

 
* 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 $800000$ de caractere

* {$1 ≤ k ≤ 9$}
* {$1 ≤ p ≤ 9$}
* {$k+p-1 ≤ 9$}
* {$1 ≤ di ≤ 9$}
* şirul $s$ are cel mult $800.000$ de caractere

h2. Exemplu

|57346
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 1111012124100111234511151 avem un val de lungime 20.
 
table(example). |_. decod.in |_. decod.out |

| 8 2
12
10121011101012101110111011101110

h3. 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$.

# 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") ==

3921