Laiko ribojimas: 0.5s

Atminties ribojimas: 16MB

Jei norite pateikti savo sprendimą - prisijunkite.

Grąža

Parduotuvė "Krepšelis" ruošiasi atsinaujinimui. Vienas pagrindinių jų planų - įrengti savitarnos kasas. Itin svarbi savitarnos kasos funkcija - teisingai paskaičiuoti grąžą klientams. Be to, kasa turėtų duoti grąžą kaip įmanoma stambesnėmis kupiūromis, nes tyrimai rodo, kad žmonėms stambios kupiūros patinka labiau nei smulkios. Galimos kupiūros yra 500, 200, 100, 50, 20, 10 ir 5. "Krepšelio" vadovai paprašė jūsų pagalbos - parašykite programą, apskaičiuojančią, kaip reikia išskaidyti grąžą nurodytomis kupiūromis. Galite tarti, kad kiekvienos kupiūros turite neribotą kiekį, o bendra grąžos suma visada yra penkių kartotinis.

Pradiniai duomenys

Pirmoje ir vienintelėje eilutėje įvestas vienas natūralusis skaičius x - grąža, kurią reikia išskaidyti kupiūromis (5\\leqx\\leq100000).

Rezultatai

Programa turi išvesti tekstą, nurodantį grąžos skaidymą kupiūromis. Išvesties formatas: n_{500}\\times500+n_{200}\\times200+n_{100}\\times100+n_{50}\\times50+n_{20}\\times20+n_{10}\\times10+n_{5}\\times5, kur n_i nurodo, kiek i vertės kupiūrų reikia duoti. Išvestyje reikia praleisti narius, lygius nuliui. Svarbu: išvestyje nepamirškite padėti tarpų tinkamose vietose, nes kitaip atsakymas nebus priimtas (žiūrėkite pavyzdžius, kad atitaikytume tikslų išvesties formatą).

Pavyzdžiai

Pradiniai duomenys Rezultatai 
575
 
1 x 500 + 1 x 50 + 1 x 20 + 1 x 5
 
1345
 
2 x 500 + 1 x 200 + 1 x 100 + 2 x 20 + 1 x 5
 
20
 
1 x 20