1190 - Sipet

Enunt

Un arheolog a găsit un sipet interesant. După ce l-a deschis cu grijă, a constatat cu surprindere că sipetul conține bănuți de aur. Uitându-se mai atent a mai găsit ceva: un pergament ascuns într-un compartiment secret al sipetului, cu un text scris într-o limbă antică, pe care, din fericire, arheologul o cunoștea. Din text a reieșit că un grup de negustori foarte bogați a vrut să ascundă în mare secret averea breslei lor, formată din monede de aur, deoarece se prevestea un război cumplit. Negustorii știau că există șanse ca această comoară să fie găsită și confiscată de dușmani, deci s-au sfătuit cum e mai bine să procedeze, cum să ascundă comoara. Arheologul a reușit să deducă din text următoarele:

a) Cele N monede, care formau averea breslei, au fost împărțite în maximum trei feluri de grămezi, formate din p1, p2 și p3 bănuți, p1, p2 și p3 fiind numere prime consecutive, p1<p2<p3. Fiecare grămadă a fost pusă în întregime într-un sipet. b) Este posibil să existe 0 (zero) grămezi formate din p1 sau p2 sau p3 monede, scopul fiind să se obțină o împărțire în care numărul monedelor rămase nedistribuite să fie minim, iar dacă există mai multe posibilități, se alege aceea pentru care numărul de grămezi este mai mare. Dacă există mai multe astfel de soluții, se consideră corectă oricare dintre ele. c) Monedele care nu au putut fi distribuite conform regulilor stabilite, au fost donate bisericii.

Cerinţa

Scrieți un program care determină numărul maxim S de sipete și numărul sipetelor cu p1, p2 respectiv p3 monede, precum și suma donată bisericii.

Date de intrare

Fișierul de intrare sipet.in conține pe prima linie numărul natural T, iar pe următoarele T linii câte două numerele naturale N și p1, despărțite printr-un singur spațiu.

Date de ieșire

Fișierul de ieșire sipet.out va conține pe prima linie pe primele T linii câte 5 numere naturale, separate prin câte un spațiu: S, x, y, z și r, reprezentând numărul maxim S de sipete, numărul x de sipete cu p1 monede, numărul y de sipete cu p2 monede, respectiv numărul z de sipete cu p3 monede și numărul r de monede donate bisericii, corespunzătoare datelor de intrare de pe linia T+1 a fișierului sipet.in. Dacă există mai multe soluții corecte, este acceptată oricare dintre ele.

Restricţii şi precizări

• 1 ≤ N ≤ 10.000.000
• 2 ≤ p1 < p2 < p3 ≤ N
• 1 ≤ T ≤ 10 – în fișierul de intrare nu vor fi mai mult de 10 perechi de numere N p1

Exemplu

sipet.in

3
15 5
10 3
41 11

sipet.out

3 3 0 0 0
2 1 0 1 0 
3 1 1 1 0

Explicație

• numărul maxim de sipete este 3, toate cu câte 3 monede;
• sau: 2 0 2 0 0 (1*3+1*7=2*5=10); (ambele soluții sunt corecte!)
• numărul maxim de sipete este 3; 1 sipet cu 11, unul cu 13 și unul cu 17 monede.

Rezolvare

<syntaxhighlight lang="python" line> def is_prime(num):

   if num < 2:
       return False
   for i in range(2, int(num ** 0.5) + 1):
       if num % i == 0:
           return False
   return True

def next_prime(num):

   while True:
       num += 1
       if is_prime(num):
           return num

def main():

   with open("sipet.in", "r") as fin:
       T = int(fin.readline())
       queries = [tuple(map(int, line.split())) for line in fin]

   primes = [2, 3, 5]
   results = []

   for N, p1 in queries:
       p2 = next_prime(p1)
       p3 = next_prime(p2)

       remaining_coins = N - p1 - p2 - p3

       # Calculate the number of coins for each pile
       x = (remaining_coins // p1) + 1
       y = (remaining_coins // p2) + 1
       z = (remaining_coins // p3) + 1

       # Calculate the number of satchels
       S = min(x, y, z)
       
       # Calculate the remaining coins after distributing them into piles
       remaining_coins -= (S - 1) * min(p1, p2, p3)

       # Calculate the number of coins donated to the church
       r = max(remaining_coins, 0)

       results.append((S, x, y, z, r))

   with open("sipet.out", "w") as fout:
       for result in results:
           fout.write(" ".join(map(str, result)) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>