Fişierul intrare/ieşire:sipet.in, sipet.outSursăONI 2015, clasa a 9-a
AutorBudai IstvanAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test1.3 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sipet

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:

  1. 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.
  2. 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.
  3. Monedele care nu au putut fi distribuite conform regulilor stabilite, au fost donate bisericii.

Cerinta

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 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 sipet.out va conţine 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

  • 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.insipet.outExplicatie
3
15 5
10 3
41 11
3 3 0 0 0
2 1 0 1 0
3 1 1 1 0
  • numărul maxim de sipete este 3, toate cu câte 5 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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?