ŠIOM — Saldus pasirinkimas 2

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Saldus pasirinkimas 2

Jonukui šiandien vėl gera diena - jis vėl rado keturias krūveles saldainių! Šįkart berniukas yra vyresnis ir nusprendė pakeisti savo krūvelės rinkimosi strategiją. Dabar jis nori išsirinkti tą krūvelę, kurią įmanoma išskaidyti į mažesnes vienodas krūveles kuo daugiau skirtingų būdų. Pavyzdžiui, jei krūvelėje yra 12 saldainių, tai šią krūvelę įmanoma išskirstyti šešiais būdais:

12 krūvelių po 1 saldainį
6 krūvelės po 2 saldainius
4 krūvelės po 3 saldainius
3 krūvelės po 4 saldainius
2 krūvelės po 6 saldainius
1 krūvelė po 12 saldainių

Jei yra kelios krūvelės, kurias įmanoma išskaidyti tiek pat būdų, Jonukas pasirinks tą krūvelę, kurioje yra mažiau saldainių. Padėkite berniukui atsakyti, kiek saldainių jis šiandien galės suvalgyti!

Patarimas

Rekomenduotina pasirašyti dvi pagalbines funkcijas:

$\\texttt{intbuduSkaicius(intkruvelesDydis)}$ , kuri atsakytų, keliais būdais įmanoma išskaidyti krūvelę, kurioje yra $kruvelesDydis$ saldainių
$\\texttt{intgeriausiaKruvele(inta,intb,intc,intd)}$ , kuri išrinktų, kurią krūvelę pasirinks Jonukas

Pradiniai duomenys

Pirmoje eilutėje įvestas vienas natūralusis skaičius $Q$ - užklausų kiekis ( $1\\leqQ\\leq1000$ ).

Tolimesnėse $Q$ eilučių įvesta po keturis natūraliuosius skaičius $s_1$ , $s_2$ , $s_3$ , $s_4$ - saldainių kiekis krūvelėse ( $1\\leqs_i\\leq1000$ ).

Rezultatai

Kiekvienai užklausai jūsų programa turi išspausdinti po vieną natūralųjį skaičių eilutėje - pasirinktos krūvelės dydį.

Pavyzdžiai

Pradiniai duomenys	Rezultatai
4 1 2 3 4 10 12 6 24 10 8 6 9 2 3 5 7	4 24 6 2

Paaiškinimas

Pirmoje užklausoje pirmą krūvelę įmanoma išskaidyti 1 būdu, antrą krūvelę - 2 būdais, trečia krūvelę - 2 būdais, o ketvirtą krūvelę - 3 būdais. Todėl renkamės ketvirtąją krūvelę.

Antroje užklausoje pirmą krūvelę įmanoma išskaidyti 4 būdais, antrą krūvelę - 6 būdais, trečia krūvelę - 4 būdais, o ketvirtą krūvelę - 8 būdais. Todėl renkamės ketvirtąją krūvelę.

Trečioje užklausoje pirmas tris krūveles įmanoma išskaidyti 4 būdais, o ketvirtąją - 3 būdais. Todėl renkamės tarp pirmų trijų krūvelių. Mažiausios iš jų dydis yra 6, todėl toks ir atsakymas.