Fişierul intrare/ieşire:	sipet.in, sipet.out	Sursă	ONI 2015, clasa a 9-a
Autor	Budai Istvan	Adăugată de	Tatomir Alex •atatomir
Timp execuţie pe test	0.65 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/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

Cum se trimit solutii?