Problem D
Deildadrottnun

Mynd eftir Randall Munroe, xkcd.com

Ríkið er nú að endurskipuleggja fjármál háskólanna. Í síðustu keppni var skipulagið sem svo að allar deildir fengu jafnt fjármagn. Þetta ásamt öðrum takmörkunum varð til þess að það nýttist ekki allt fjármagn, eitthvað sem þarf klárlega að bæta. Að þessu sinni ætlar ríkið að úthluta hverri deild visst fjármagn og sleppa umsóknarferlinu. Þetta er vegna þess að sumum prófessorum leiddist svo að skrifa umsóknir að þeir voru farnir að múta öðrum til að sjá um það fyrir þeirra hönd.

Til þess að plútóníumbirgðir háskólanna falli ekki í rangar hendur er mikilvægt að þetta sé gert vel.

Deildum háskólanna er raðað eftir stærð og eiga að fá fjármagn í hlutfalli við það, svo engar tvær deildir sem fá pening mega fá jafn mikinn pening. Enn fremur verður fyrsta deildin sem fær pening að fá einar eða tvær milljónir nákvæmlega. Næsta verður að fá tvær eða þrjár milljónir, þriðja þrjár eða fjórar milljónir og þar fram eftir götunum.

Inntak

Fyrsta og eina lína inntaksins inniheldur eina heiltölu $n$, fjármagnið sem á að dreifa á deildir, talið í milljónum íslenskra króna. Gefið er að $1 \leq n \leq 10^{10}$.

Úttak

Fyrsta lína úttaksins skal innihalda eina heiltölu, fjölda deilda sem fá pening. Á næstu línu skal prenta peninginn sem hver deild fær, gefið í vaxandi röð og tölurnar aðskildar með bilum, allt gefið í milljónum króna. Ef til er meir en ein leið til að dreifa fjármagninu þannig að öllum skilyrðum að ofan sé uppfyllt má prenta hverja sem er þeirra. Gefið er að inntakið sé þannig að til sé að minnsta kosti ein lausn

6

3
1 2 3 

16

5
1 2 3 4 6