Fişierul intrare/ieşire:magic3.in, magic3.outSursăONI 2015 clasa a 8-a
AutorLivia TocaAdăugată decella.florescuCella Florescu cella.florescu
Timp execuţie pe test0.1 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Magic3 (clasa a 8-a)

Pentru obţinerea Pietrei Filosofale, un alchimist a preparat un elixir folosind un creuzet de capacitate C, în care a turnat picături de metal topit, într-o ordine bine stabilită, în N etape. Numărul de picături turnate într-o etapă este cuprins între 0 şi C - 1, iar procesul începe când în creuzet s-a turnat prima picătură (în prima etapă numărul de picături turnate este nenul). Picăturile se adună în creuzet una câte una şi, de fiecare dată când acesta se umple complet, alchimistul rosteşte o formulă magică, provocând transformarea întregului conţinut într-o singură picătură, apoi continuă procesul. O reţetă de obţinere a elixirului se exprimă printr-un şir de N numere, reprezentând numărul de picături turnate în cele N etape.

De exemplu, aplicând reţeta 5 6 1 0, cu un creuzet de capacitate C = 7, în cele N = 4 etape procesul este:
- etapa 1: se toarnă 5 picături;
- etapa a 2-a: se toarnă 6 picături, astfel: după primele 2 picături se umple creuzetul ( 5 + 2 = 7 ) şi deci se rosteşte formula magică, în creuzet rămânând o picătură; se continuă cu celelalte 4 picături; la finalul etapei în creuzet sunt 5 picături ( 1 + 4 = 5 );
- etapa a 3-a: se toarnă o picătură; la finalul etapei în creuzet sunt 6 picături ( 5 + 1 = 6 );
- etapa a 4-a: se toarnă 0 picături; după ultima etapă creuzetul conţine 6 picături ( 6 + 0 = 6 ).

O reţetă care corespunde Pietrei Filosofale trebuie să conducă, la finalul aplicării ei, la obţinerea unei singure picături, chintesenţa metalelor amestecate. Bineînţeles, sunt mai multe astfel de reţete. Fiind un tip responsabil, alchimistul a lăsat posterităţii un set de tratate, care cuprind toate aceste reţete. El a scris pe fiecare pagină câte o reţetă, astfel încât niciuna să nu se repete în cadrul întregii lucrări. Pe vremea aceea erau meşteri pricepuţi, care fabricau tratate de dimensiuni corespunzătoare, încât fiecare pagină să poată cuprinde o reţetă ca a noastră, oricât de lungă ar fi ea. Fiecare tratat are P pagini şi doar după ce completează toate cele P pagini ale unui tratat, alchimistul începe un nou tratat.

Cerinţă

Se cere numărul de reţete publicate în ultimul tratat.

Date de intrare

Fişierul de intrare magic3.in conţine pe prima linie, în această ordine, numerele naturale C, N, P, separate prin câte un spaţiu şi având semnificaţia din enunţ.

Date de ieşire

Fişierul magic.out conţine un număr natural reprezentând numărul de reţete publicate în ultimul tratat.

Restricţii

  • 2 ≤ C, N, P ≤ 10.000.000, numere naturale.
  • pentru 30% din teste, C ≤ 10 si N ≤ 9; iar pentru 70% din teste, N ≤ 10.000.

Exemplu

magic3.inmagic3.out
4 2 3
1

Explicaţie

Creuzetul are capacitatea C = 4, sunt N = 2 etape de aplicare a fiecărei reţete, tratatele au câte P = 3 pagini. Reţetele aplicate în două etape, în urma fiecărui astfel de proces rămânând în creuzet câte o singură picătură, sunt: 1 0; 1 3; 3 1; 2 2. Pentru acestea sunt necesare două tratate, primul conţinând trei reţete, iar al doilea (ultimul) o singură reţetă.

Trebuie sa te autentifici pentru a trimite solutii. Click aici