Fişierul intrare/ieşire:blis.in, blis.outSursăOJI 2012 - clasele 11-12
AutorDan PracsiuAdăugată deSpiderManSimoiu Robert SpiderMan
Timp execuţie pe test0.6 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Blis

Se consideră un şir de biţi şi un număr natural K. Şirul se împarte în secvenţe astfel încât fiecare bit din şir să aparţină unei singure secvenţe şi fiecare secvenţă să aibă lungimea cel puţin 1 şi cel mult K. După împărţire, fiecare secvenţă de biţi se converteşte în baza 10, obţinându-se un şir de valori zecimale. De exemplu, pentru şirul de biţi 1001110111101010011 şi K = 4, se poate obţine 1 0011 101 111 0 1010 011, apoi în baza 10: 1, 3, 5, 7, 0, 10, 3. O altă împărţire poate fi 1 00 1 1 10 11 110 1010 011, adică 1, 0, 1, 1, 2, 3, 6, 10, 3.

Cerinţă

Scrieţi un program care:

  • determină valoarea maximă (în baza 10) care se poate obţine dintr-o secvenţă de cel mult K biţi
  • împarte şirul iniţial în secvenţe de cel mult K biţi astfel încât şirul zecimal obţinut să conţină un subşir strict crescător de lungime maximă posibilă.

Date de intrare

Prima linie a fişierului de intrare blis.in conţine numărul natural K, iar pe linia a doua se află şirul de biţi, şirul neconţinând spaţii.

Date de ieşire

Fişierul de ieşire blis.out va conţine pe prima linie un număr natural reprezentând valoarea maximă care se poate obţine dintr-o secvenţă de cel mult K biţi, iar pe linia a doua un singur număr natural reprezentând lungimea maximă a subşirului strict crescător care se poate obţine din şirul de biţi prin împărţirea sa în secvenţe de cel mult K biţi.

Restricţii

  • 3 ≤ lungimea şirului de biţi ≤ 100 000
  • pentru 70% din teste, lungimea şirului de biţi ≤ 1000
  • 1 ≤ K ≤ 30
  • Un subşir se obţine dintr-un şir prin eliminarea a zero, unul, două sau mai multe elemente;
  • O secvenţă este formată din elemente aflate pe poziţii consecutive în şir;
  • Pentru rezolvarea corectă a primei cerinţe se acordă 20% din punctaj, iar pentru rezolvarea corectă a celei de-a doua se acordă 80%.

Exemplu

blis.inblis.outExplicaţie
4
1001110111101010011
15
6
Secvenţa de valoare maximă de cel mult 4 biţi este 1111, adică 15 în baza 10.
Pentru cerinţa a doua, şirul binar se împarte astfel:
1 00 1 1 10 11 110 1010 011,
Se obţine şirul zecimal:
1, 0, 1, 1, 2, 3, 6, 10, 3.
Subşirul strict crescător maximal de lungime 6 este 0, 1, 2, 3, 6, 10
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content