Fişierul intrare/ieşire:rest.in, rest.outSursăOlimpiada locala 2014, Clasa a 5-a
AutorAutor NecunoscutAdăugată defrancuCristian Francu francu
Timp execuţie pe test1 secLimită de memorie1024 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Rest (clasa a 5-a)

Andrei, mare pasionat de matematică, compune adesea probleme cu numere mari: fie N un număr natural care poate avea maxim 100 000 de cifre în scrierea în baza 10, pe un astfel de număr se defineşte prefix al lui N ca fiind un număr format din primele cifre ale lui N, în ordine de la stânga la dreapta. Prefixul poate avea minim o cifră şi maxim tot atâtea cifre ca N. Restul modulo K al unui număr natural este restul obţinut la împărţirea întreagă a acelui număr la K.

Cerinţă

Ajutaţi-l pe Andrei sa rezolve următoarea problemă: considerând resturile modulo K ale tuturor prefixelor lui N, determinaţi care este restul maxim care apare şi pentru câte dintre aceste prefixe se obţine.

Date de intrare

Fişierul de intrare rest.in conţine pe prima linie numărul natural K, iar pe a doua linie un şir de cifre, despărţite printr-un spaţiu, reprezentând cifrele numărului natural N.

Date de ieşire

Fişierul de ieşire rest.out va conţine pe prima linie două numere naturale r nr, despărţite printr-un spaţiu, reprezentând restul maxim modulo K determinat şi numărul de prefixe pentru care se obţine acest rest.

Restricţii

  • 1 ≤ K ≤ 100
  • 1 ≤ numărul de cifre ale lui N ≤ 100 000

Exemplu

rest.inrest.outExplicaţie
3
2 4 5 3
2 3
Prefixele ce se pot obţine sunt: 2, 24, 245 şi 2453,
iar resturile modulo 3 sunt în ordine: 2, 0, 2, 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici