Fişierul intrare/ieşire:hiccup.in, hiccup.outSursăOlimpiada pe scoala 2015
AutorCristian FrancuAdăugată deIsabela_comanComan Isabela Patricia Isabela_coman
Timp execuţie pe test1 secLimită de memorie3072 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Hiccup (clasa a 7-a)

Deoarece laptopul lui Hiccup a venit preinstalat cu diabolicul sistem de operare Macrohard Doors el a pierdut toate numerele de telefon din agenda sa păstrată într-un fişier pe disc. Încercînd să regăsească numărul iubitei sale Astrid, el a folosit un program de recuperare numit dd (Dumb Data). După ce a rulat o zi şi o noapte, programul a putut recupera din agendă doar cifrele, pe care le-a scris sub forma unui şir într-un fişier, afişînd apoi pe ecran un mesaj în care specifica un număr de control pentru operaţia de salvare realizată. Acel număr de control reprezintă suma tuturor cifrelor recuperate.

Hiccup este însă ferm convins că numărul lui Astrid este acolo. El îşi aduce aminte că numărul ei foloseşte fix K cifre distincte, repetate ori de cîte ori. De asemenea speră că numărul nu a fost fragmentat şi împrăştiat, fiind o secvenţă de cifre una după alta, astfel încît el poate fi căutat în şirul de cifre obţinut.

Cerinţă

Hiccup fiind obişnuit mai mult cu dragonii decît cu calculatoarele vă roagă pe voi să găsiţi în noianul de cifre secvenţele de lungime maximă formate din K cifre distincte repetate, în speranţa că printre ele se află numărul de telefon al lui Astrid. El ar vrea de asemenea să verifice numărul de control afişat pe ecran de programul de recuperare dd.

Date de intrare

Fişierul de intrare hiccup.in conţine două linii. Pe prima linie se află K, numărul de cifre distincte din care este format numărul lui Astrid (care se pot repeta). Pe a doua linie se află cifrele recuperate din agendă, fără spaţii între ele. Ambele linii se termină cu caracterul sfîrşit de linie.

Date de ieşire

Fişierul de ieşire hiccup.out va conţine pe prima linie numărul de control x afisat de programul de recuperare iar pe a doua linie lungimea numărului de lungime maximă format din exact K cifre repetate. Dacă nu există nici un astfel de număr lungimea se consideră zero (iar Hiccup va fi foarte, foarte trist).

Restricţii

  • 1 ≤ lungimea şirului de cifre ≤ 4.000.000
  • 1 ≤ K ≤ 10
  • Zero este o cifră validă cu care poate să înceapă un număr de telefon, ea neavînd nici un fel de proprietăţi speciale.
  • Se acordă punctaje parţiale, astfel: 20% pentru cifra de control, 80% pentru lungimea maximă.
  • Pentru a obţine punctaje parţiale trebuie să afişaţi răspunsul pe linia corespunzătoare.
  • Pentru 50% din teste şirul va avea maxim 200 000 de cifre.
  • Pentru 80% din teste şirul va avea maxim 2 000 000 de cifre.
  • Dimensiunea maximă a sursei: 10Kb

Exemplu

hiccup.inhiccup.outExplicaţie
2
12123233
17
5
Suma cifrelor recuperate este 17.
Numărul cel mai lung care este format din două cifre este 23233,
avînd lungime 5. Următorul este 1212 dar are lungime mai mică, 4.
3
02920992020102010201020020303
52
19
Suma cifrelor recuperate este 52.
Numărul cel mai lung format din trei cifre repetate este
2020102010201020020
şi începe la poziţia 8. El are lungime 19.
Trebuie sa te autentifici pentru a trimite solutii. Click aici