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, daca am continua sesiunea pana la finalul sirului, această combinaţie ar 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?