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 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 ci, 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, 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.

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 ci, 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 ≤ ci ≤ 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.

Î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")

1. 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>