== include(page="template/taskheader" task_id="sipet") ==
Poveste şi cerinţă...
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:
# 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.
# 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.
# Monedele care nu au putut fi distribuite conform regulilor stabilite, au fost donate bisericii.
h2. 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.
h2. Date de intrare
Fişierul de intrare $sipet.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $sipet.out$ ...
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.
h2. 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$
h2. Exemplu
table(example). |_. sipet.in |_. sipet.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. sipet.in |_. sipet.out |_. Explicatie |
| 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.
|
== include(page="template/taskfooter" task_id="sipet") ==
