Editing 1034 - Roata

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 <code>n</code> cabine, numerotate de la <code>1</code> la <code>n</code> î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 <code>1</code> aflată în poziţia de îmbarcare şi se face în sens antiorar. Un client plăteşte pentru o rotire <code>1 EUR</code> şi poate cumpăra un număr oarecare de rotiri.

Cei <code>p</code> clienţi care doresc utilizarea roţii trebuie să respecte următoarea procedură: clientul cu numărul de ordine <code>i</code> îşi cumpără un bilet pe care sunt înscrise numărul său de ordine şi numărul de rotiri <code>c<sub>i</sub></code>, <code>1≤ i ≤ p</code>, 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 <code>n</code> de cabine al roţii, numărul <code>p</code> de clienţi, precum şi numărul de  rotiri cumpărate de fiecare client, <code>c<sub>i</sub></code>, <code>1≤ i ≤ p</code>, 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 <code>roata.in</code> conține pe prima linie numărul natural <code>n</code>, pe al doilea rând numărul natural <code>p</code> iar pe al treilea rând numerele naturale <code>c<sub>i</sub></code>, <code>1 ≤ i ≤ p</code>, separate printr-un spaţiu, cu semnificaţiile de mai sus.

= Date de ieșire =
Fișierul de ieșire <code>roata.out</code> 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 =

* <code>2 ≤ n ≤ 360</code>
* <code>1 ≤ p ≤ 100 000</code>
* <code>1 ≤ c<sub>i</sub> ≤ 100 000</code>

= Exemplu: =
<code>roata.in</code>
 4
 7
 6 4 1 5 2 8 3
<code>roata.out</code>
 29
 3 5 2 4 1 7 6 
 3

= Explicație =
Roata are <code>n=4</code> cabine şi numărul de clienţi este <code>p=7</code>.

Primul client cumpără <code>6</code> rotiri, al doilea <code>4</code> rotiri, … , iar al şaptelea client cumpără <code>3</code> rotiri. Suma totală încasată este de <code>29 EUR</code>.

După ce primii <code>4</code> clienţi se urcă în roată şi se efectuează o rotire completă, primul care coboară este clientul al <code>3</code>-lea şi imediat se urcă clientul al <code>5</code>-lea. După încă <code>2</code> rotiri, clientul al <code>5</code>-lea coboară şi se urcă clientul al <code>6</code>-lea. După încă o rotire coboară clientul al <code>2</code>-lea şi se urcă al <code>7</code>-lea client. Ultimii <code>4</code> clienţi coboară  în ordinea <code>4,1,7,6</code>.

Cabina din care coboară ultimul client este cabina cu numărul <code>3</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

nmax = 361
pmax = 100001

f = open("roata.intxt", "r")
g = open("roata.outtxt", "w")

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

def main():
    # o - ordinea la urcare, c - costul biletului
    n, p = map(int, f.readline().split())
    o = [0] * nmax
    c = [0] * pmax
    s = 0

    # initializez numerele de ordine ale primilor n clienti
    for i in range(1, n+1):
        o[i] = i

    # citesc numarul de rotiri si calculez suma totala incasata
    for i in range(1, p+1):
        c[i] = int(f.readline())
        s += c[i]

    # afisez suma totala incasata
    g.write(str(s) + "\n")

    if n < p:
        for k in range(n+1, p+1):
            # determin clientul care urmeaza sa coboare
            pozmin = 1
            for i in range(2, n+1):
                if c[i] < c[pozmin]:
                    pozmin = i

            # afisez ordinea la coborare
            g.write(str(o[pozmin]) + " ")

            # resetez toate valorile lui c[i] pentru ca sunt prea mari
            if c[pozmin] > 10000000:
                for i in range(1, n+1):
                    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 in range(2, n+1):
        if c[i] >= c[pozmax]:
            pozmax = i

    for k in range(1, n+1):
        # determin clientul care urmeaza sa coboare
        pozmin = 1
        for i in range(2, n+1):
            if c[i] < c[pozmin]:
                pozmin = i

        # afisez ordinea la coborare
        g.write(str(o[pozmin]) + " ")

        c[pozmin] += 100001

    # afisez numarul cabinei din care va cobora ultimul client
    g.write("\n" + str(pozmax) + "\n")

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

if __name__ == "__main__":
    sys.exit(main())
</syntaxhighlight>