0714 - Birocratie1

Enunt

Nici nu ştiţi cât de greu este să fii funcţionar. Zeci de rapoarte de întocmit, sute de cereri ce trebuiesc redactate, mii de semnături, sute de mii de hârtii de înregistrat. Circuitul nesfârşit al hârtiilor este cunoscut sub numele de birocraţie. În instituţia noastră sunt angajaţi N funcţionari, numerotaţi de la 1 la N.

Fiecare dintre ei trebuie să înregistreze un număr considerabil de documente. Acesta este motivul pentru care în fiecare zi, încă de la prima oră, funcţionarii se aşază la coadă la secretariat, în ordine de la 1 la N. Modalitatea de înregistrare a documentelor este următoarea: funcţionarul se aşează la coadă, aşteaptă până îi vine rândul, înregistrează un singur document, apoi, dacă mai are alte documente se reaşează la coadă, ş.a.m.d. Din păcate, serviciul de secretariat înregistrează într-o zi cel mult M documente.

Cerința

Dacă se cunoaşte, pentru fiecare din cei N de funcţionari, numărul de documente pe care trebuie să le înregistreze la secretariat, determinaţi numărul de ordine al funcţionarilor care nu au reuşit semnarea tuturor documentelor până la încheierea zilei de muncă.

Date de intrare

Fișierul de intrare birocratie1in.txt conține pe prima linie două valori întregi N şi M cu semnificaţia din enunţ (N – numărul de funcţionari, M – numărul maxim de documente înregistrate de secretariat într-o zi), iar pe cea de-a doua linie N numere naturale a[i], 1⩽i⩽N, separate prin câte un spaţiu, reprezentând numărul de documente pe care trebuie să le înregistreze fiecare funcţionar, în ordine de la 1 la N.

Date de ieșire

Fișierul de ieșire birocratie1out.txt va conţine pe o singură linie numerele de ordine ale tuturor funcţionarilor care au rămas nesoluţionaţi aşa cum se găsesc la coadă la sfârşitul zilei de lucru, de la primul rămas neservit, până la ultimul.

Dacă la finalul zilei toţi funcţionarii şi-au semnat toate documentele, fişierul de ieşire va conţine valoarea 0.

Restricții și precizări

• 1 ⩽ N ⩽ 100 000
• 0 < M < 1014
• 1 %les; a[i] ⩽ 109
• Numărul total de documente al tuturor funcţionarilor este cel mult 1018

Exemplu 1

birocratie1in.txt

5 10

2 4 1 3 2

birocratie1out.txt

4 2

Explicație

Iniţial s-a format coadă cu următorii funcţionari {1,2,3,4,5}. După o prima trecere a tuturor funcţionarilor pe la secretariat, s-au înregistrat 5 documente şi la coada au mai rămas în ordine funcţionarii {1,2,4,5}. După a doua trecere, s-au mai semnat 4 documente şi la coadă s-au reaşezat funcţionarii {2,4}. Funcţionarul 2 întregistrează documentul şi se aşează la coadă, după care secretariatul se închide.

Exemplu 2

birocratie1in.txt

3 6

1 2 1

birocratie1out.txt

0

Exemplu 3

birocratie1in.txt

0 -1

birocratie1out.txt

Nu au fost respectate cerintele impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 0714 - Birocratie1

def read_input(file_name):

   try:
       with open(file_name, 'r') as file:
           N, M = map(int, file.readline().split())
           documents = list(map(int, file.readline().split()))

           return N, M, documents
   except Exception as e:
       print(f"Nu au fost respectate cerintele impuse: {str(e)}")
       return None

def write_output(file_name, result):

   with open(file_name, 'w') as file:
       if result is not None:
           file.write(" ".join(map(str, result)) + "\n")

def unsolved_functionaries(N, M, documents):

   remaining_documents = M
   unsolved = []

   for i in range(N):
       if documents[i] > remaining_documents:
           unsolved.append(i + 1)
       else:
           remaining_documents -= documents[i]

   return unsolved

def main(input_file, output_file):

   result = read_input(input_file)
   if result is not None:
       N, M, documents = result
       result = unsolved_functionaries(N, M, documents)
       write_output(output_file, result)

if __name__ == "__main__":

   main("birocratie1in.txt", "birocratie1out.txt")

</syntaxhighlight>