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.

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.

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≤ i ≤ 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.

Cerinţa

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:

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.

Date de intrare

Fișierul de intrare roata.in conține pe prima linie numărul natural n, pe al doilea rând numărul natural p iar pe al treilea rând numerele naturale c_i, 1 ≤ i ≤ p, separate printr-un spaţiu, cu semnificaţiile de mai sus.

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.

Restricții și precizări

2 ≤ n ≤ 360
1 ≤ p ≤ 100 000
1 ≤ c_i ≤ 100 000

Exemplu

roata.in

4
7
6 4 1 5 2 8 3

roata.out

29
3 5 2 4 1 7 6 
3

Explicație

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Roata:

// sursa de 100 p - prof. Chesca Ciprian
#include <fstream>

#define nmax 361
#define pmax 100001

using namespace std;


ifstream f("roata.in");
ofstream g("roata.out");

// n = numarul de cabine, p = numarul de persoane

int main()
{
// o - ordinea la urcare, c - costul biletului  

int n,p,i,k,pozmax,pozmin,o[nmax],c[pmax];
long long s=0;

f>>n>>p;

// initializez numerele de ordine ale primilor n clienti
for(i=1;i<=n;i++) 
    o[i]=i;

// citesc numarul de rotiri si calculez suma totala incasata
for(i=1;i<=p;i++) 
    {f>>c[i];s+=c[i];}

// afisez suma totala incasata
g<<s<<"
";

if (n<p)
    for(k=n+1;k<=p;k++)
        {
        // determin clientul care urmeaza sa coboare
        pozmin=1;
        for(i=2;i<=n;i++)
            if (c[i]<c[pozmin]) pozmin=i;   
        
        // afisez ordinea la coborare
        g<<o[pozmin]<<" ";
                
        // resetez toate valorile lui c[i] pentru ca sunt prea mari
        if (c[pozmin]>10000000)
            for(i=1;i<=n;i++)
                    c[i]-=10000000;
        
        c[pozmin]+=c[k]; // o mica smecherie - in loc sa scad din toate minimul, am adunat      
        o[pozmin]=k; 
        }
    else
        n=p;
    
// determin numarul cabinei din care va cobora ultimul client
pozmax=1;
for(i=2;i<=n;i++)
    if (c[i]>=c[pozmax]) pozmax=i;
        
for(k=1;k<=n;k++)
        {
        // determin clientul care urmeaza sa coboare
        pozmin=1;
        for(i=2;i<=n;i++)
            if (c[i]<c[pozmin]) pozmin=i;   
        
        // afisez ordinea la coborare
        g<<o[pozmin]<<" ";
                
        c[pozmin]+=100001; 
        }   

// afisez numarul cabinei din care va cobora ultimul client
g<<"
"<<pozmax<<"
";  

f.close();
g.close();
return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1034 Roata

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1034 Roata de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1034 Roata