1223 - Magic1

Enunț

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ța

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

Date de intrare

Fișierul de intrare magic1.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 de ieșire magic1.out va conține un număr natural reprezentând numărul de rețete publicate în ultimul tratat.

Restricții și precizări

1<C≤10^7; 2≤N≤10^7; 1≤P≤10^7, numere naturale; pentru 30% dintre teste, C≤10 și N<10, iar pentru 70% dintre teste, N≤10^4.

Exemplu

Exemplu1

magic1.in <syntaxhighlight lang="python"> 4 2 3 </syntaxhighlight>

magic1.out <syntaxhighlight lang="python"> 1 </syntaxhighlight>

Rezolvare

<syntaxhighlight lang="python">

def validare(C: int, N: int, P: int) -> bool:

   """
   Funcția de validare.
   """
   if not 1 < C <= 10 ** 7:
       return False
   if not 2 <= N <= 10 ** 7:
       return False
   if not 0 <= P <= 10 ** 7:
       return False
   return True

def rezolvare(reteta: list, C: int, N: int, P: int) -> int:

   """
   Funcția de rezolvare.
   """
   total_picaturi = 0
   tratate = 0
   for picaturi in reteta:
       total_picaturi += picaturi
       if total_picaturi >= C:
           total_picaturi = 0
           tratate += 1
   if total_picaturi > 0:
       tratate += 1
   if N * P > tratate:
       return 1
   return tratate // (N * P) + (1 if tratate % (N * P) != 0 else 0)

def main():

   with open("magic1.in") as fin:
       C, N, P = map(int, fin.readline().split())
       reteta = list(map(int, fin.readline().split()))
   if not validare(C, N, P):
       print("Valorile introduse sunt invalide!")
       return
   with open("magic1.out", "w") as fout:
       fout.write(str(rezolvare(reteta, C, N, P)))

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicații

Codul implementează o soluție pentru problema Magic1, care cere calcularea numărului minim de tratate necesare pentru a aplica o serie de rețete pe un creuzet cu o anumită capacitate și cu anumite caracteristici de aplicare a rețetelor. Conform enunțului problemei, fiecare rețetă este aplicată în două etape și produce un anumit număr de picături, iar un tratament conține un anumit număr de rețete și se consumă P pagini. Problema cere determinarea numărului minim de tratate necesare pentru a aplica toate rețetele pe creuzet, ținând cont de caracteristicile acestora.

Funcția validare verifică dacă valorile de intrare respectă cerințele problemei (adică dacă C, N și P sunt în intervalul [1, 10^7], iar N și P sunt în intervalul [2, 10^7]) și returnează True dacă valorile sunt valide și False în caz contrar.

Funcția rezolvare primește ca argumente lista de rețete și valorile C, N și P și calculează numărul minim de tratate necesare pentru a aplica toate rețetele. Pentru fiecare rețetă, numărul de picături este adăugat la numărul total de picături, iar dacă acesta depășește capacitatea creuzetului, numărul de tratamente necesare este incrementat și totalul picăturilor este resetat. Dacă la final numărul de picături rămase în creuzet este nenul, un tratament suplimentar este necesar. Rezultatul final este calculat prin împărțirea numărului de tratamente la numărul total de rețete care se pot include într-un tratament (adică N * P) și adăugarea unui tratament suplimentar dacă numărul de tratamente este divizibil cu N * P.

Funcția main citeste datele de intrare din fișierul "magic1.in", verifică dacă acestea sunt valide folosind funcția validare, apoi calculează și afișează în fișierul "magic1.out" rezultatul obținut prin apelul funcției rezolvare.