Roata

roata

== include(page="template/taskheader" task_id="roata") ==

p<>. Una dintre atracţiile celebrului parc de distracţii Prater din Viena este Marea Roată Vieneză. Din ea se poate admira priveliştea întregii Viene.

Una dintre atracţiile celebrului parc de distracţii Prater din Viena este Marea Roată Vieneză. Din ea se poate admira priveliştea întregii Viene.

p<>. Roata are $n$ cabine, numerotate de la $1$ la $n$ în sens orar şi dispuse simetric pe circumferinţa roţii. Îmbarcarea clienţilor se face în cabina în care roata este tangentă cu solul, iar rotirea începe cu cabina $1$ aflată în poziţia de îmbarcare şi se face în sens antiorar. Un client plăteşte pentru o rotire $1 EUR$ şi poate cumpăra un număr oarecare de rotiri.

Roata are $n$ cabine, numerotate de la $1$ la $n$ în sens orar şi dispuse simetric pe circumferinţa roţii. Îmbarcarea clienţilor se face în cabina în care roata este tangentă cu solul, iar rotirea începe cu cabina $1$ aflată în poziţia de îmbarcare şi se face în sens antiorar. Un client plăteşte pentru o rotire $1 EUR$ şi poate cumpăra un număr oarecare de rotiri.

p<>. Cei $p$ clienţi care doresc utilizarea roţii trebuie să respecte următoarea procedură: clientul cu numărul de ordine $i$ îşi cumpără un bilet pe care sunt înscrise numărul său de ordine şi numărul de rotiri $c$~$i$~, $1 &le; i &le; p$, apoi se aşează la rând. Când în poziţia de îmbarcare este o cabină liberă sau se eliberează o cabină, roata se opreşte şi urcă următorul clientul. Un client coboară după ce se efectuează numărul de rotiri înscris pe bilet.

Cei $p$ clienţi care doresc utilizarea roţii trebuie să respecte următoarea procedură: clientul cu numărul de ordine $i$ îşi cumpără un bilet pe care sunt înscrise numărul său de ordine şi numărul de rotiri ci, $1 ≤ i ≤ p$, apoi se aşază la rând. Când în poziţia de îmbarcare este o cabină liberă sau se eliberează o cabină, roata se opreşte şi urcă următorul clientul. Un client coboară după ce se efectuează numărul de rotiri înscris pe bilet.

h2. Cerinţă

Să se scrie un program care, cunoscând numărul $n$ de cabine al roţii, numărul $p$ de clienţi, precum şi numărul de  rotiri cumpărate de fiecare client, $c$~$i$~, $1 ≤ i ≤ p$, să calculeze:

Să se scrie un program care, cunoscând numărul $n$ de cabine al roţii, numărul $p$ de clienţi, precum şi numărul de  rotiri cumpărate de fiecare client, ci , $1 ≤ i ≤ p$, să calculeze:

* suma totală încasată de administratorul roţii de la clienţi;
* ordinea în care coboară clienţii din roată;
* numărul cabinei din care coboară ultimul client.

{*}	suma totală încasată de administratorul roţii de la clienţi;
{*}	ordinea în care coboară clienţii din roată;
{*}	numărul cabinei din care coboară ultimul client.

h2. Date de intrare

h2. Date de ieşire

Fişierul de ieşire $roata.out$ va conţine pe prima linie suma totală încasată, pe a doua linie numerele de ordine ale clienţilor, în ordinea coborârii, separate printr-un spaţiu, iar pe a treia linie numărul cabinei din care va coborî ultimul client.

În fişierul de ieşire $roata.out$ ...

h2. Restricţii

* $2 ≤ n ≤ 360$
* $1 ≤ p ≤ 100 000$
* $1 ≤ c{~i~} ≤ 100 000$
* pentru rezolvarea primei cerinţe se acordă $20%$ din punctaj, iar pentru celelalte două cerinţe se acordă câte $40%$ din punctaj fiecare.

* $... ≤ ... ≤ ...$

h2. Exemplu

table(example). |_. roata.in |_. roata.out |_. Explicaţie |
| 4
7
6 4 1 5 2 8 3
| 29
3 5 2 4 1 7 6
3
| Roata are n = 4 cabine şi numărul de clienţi este p = 7.
Primul client cumpără 6 rotiri, al doilea 4 rotiri , ... , iar al şaptelea client cumpără 3 rotiri. Suma totală
încasată este de 29 EUR. După ce primii 4 clienţi se urcă în roată şi se efectuează o rotire completă, primul care
coboară este clientul al 3-lea şi imediat se urcă clientul al 5-lea. După încă 2 rotiri, clientul al 5-lea coboară
şi se urcă clientul al 6-lea. După încă o rotire coboară clientul al 2-lea şi se urcă al 7-lea client. Ultimii 4
clienţi coboară în ordinea 4, 1, 7, 6.
Cabina din care coboară ultimul client este cabina cu numărul 3 |

table(example). |_. roata.in |_. roata.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
h3. Explicaţie
...

== include(page="template/taskfooter" task_id="roata") ==

7679