Fişierul intrare/ieşire:decod.in, decod.outSursăONI 2009, Baraj Gimnaziu
AutorAna IntunericAdăugată deandrici_cezarAndrici Cezar andrici_cezar
Timp execuţie pe test0.075 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/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:

  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

Cum se trimit solutii?

remote content