Fişierul intrare/ieşire:	text5.in, text5.out	Sursă	ONI 2015 Clasele 11-12
Autor	Rodica Pintea	Adăugată de	Andrei Stanciu •assa98
Timp execuţie pe test	0.2 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Text5

Un şir format din cifre trebuie să fie tastat în una sau mai multe sesiuni.
Există două tastaturi: tastatura A care conţine taste cu toate combinaţiile de exact două cifre: tasta 00, tasta 01, 02, …, 98, 99 şi tastatura B care conţine taste cu toate combinaţiile de exact trei cifre: tasta 000, tasta 001, …, 998, 999. Cifrele se vor introduce în una sau mai multe sesiuni, pentru o sesiune putându-se folosi o singură tastatură. Datorită unei ordonanţe de urgenţă, dacă o combinaţie de taste a fost introdusă cu una din tastaturi în sesiunea curentă şi, continuând sesiunea, această combinaţie poate fi introdusă din nou, este necesar să continuăm sesiunea cel puţin până când o vom introduce din nou. În cazul în care introducem până atunci şi alte taste, trebuie să continuăm sesiunea până când vom introduce ultima apariţie a lor.
Astfel, dacă şirul 255222255257 este început folosind tastatura A, se va scrie obligatoriu într-o sesiune 25 52 22 25 52 . Suntem obligaţi să tastăm până la ultima apariţie a tastei 25 în sesiunea curentă, şi când folosim tasta 52 suntem obligaţi să continuăm până la ultima apariţie a acesteia. A se observa că cifrele de pe poziţiile subliniate sunt tot 2 şi 5, însă nu formează o tastă care se poate apăsa în sesiunea curentă. Deoarece se doreşte un număr cât mai mare de sesiuni, se va începe o nouă sesiune în care se va scrie doar 57.

Cerinţa

Cunoscându-se numărul total de cifre şi secvenţa de cifre ce formează şirul, să se determine o modalitate de a despărţi textul astfel încât el să poată fi scris într-un număr maxim de sesiuni.

Date de intrare

Din fişierul text5.in se citesc:
- de pe prima linie un număr natural N reprezentând numărul de cifre
- de pe următoarea linie N cifre, scrise fără spaţii, reprezentând şirul de tastat

Date de ieşire

În fişerul text5.out se afişează:
- pe prima linie S, reprezentând numărul maxim de sesiuni
- pe fiecare dintre următoarele S linii, câte două numere p, k, scrise cu spaţiu între ele, fiecare astfel de pereche descriind, în ordinea în care apar în text, secvenţele tipărite în sesiuni: p_i – poziţia din şirul de cifre dat unde începe sesiunea i şi k_i – tipul de tastatură folosită în sesiunea i ( 2 pentru tastatura A, 3 pentru tastatura B)

Restrictii

• 3 ≤ N ≤ 1 000 000
• cifrele din secvenţă sunt între 0 şi 9
• testele propuse asigură existenţa unei soluţii pentru cerinţa dată
• dacă există mai multe soluţii, se va furniza oricare dintre ele.
• pentru numărul corect de sesiuni, fără liniile care descriu soluţia completă şi corectă se acordă 50% din punctaj.

Exemplu

Explicaţie

In primul exemplu şirul poate fi scris în maximum 5 sesiuni astfel: 233, 32, 333 333, 33, 22
- prima sesiune, începe cu prima cifră şi foloseşte tastatura B
(cu taste de 3 cifre)
- următoarea sesiune începe la cifra a 3-a şi foloseşte tastatura A
- a treia sesiune începe la cifra a 6-a şi foloseşte tastatura B
- a patra sesiune începe la cifra a 12-a şi foloseşte tastatura A
- ultima sesiune începe la cifra a 14-a şi foloseşte tastatura A

In al doilea exemplu soluţia corespunde secvenţelor 462 34 623

Cum se trimit solutii?