Fișierul intrare/ieșire decod.in, decod.out Sursă ONI 2009 baraj gimnaziu
Autor Ana Întuneric Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.15 sec Limită de memorie 640 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in decod.out Explicații
3 5
12124
1111012124100111234511151
57346
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
 
1111012124100111234511151
 
avem un val de lungime 20.
8 2
12
10121011101012101110111011101110
89
20
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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii