3736 - Sir 15

Sursă: [1]

Enunt

Se dă un șir format din N numere naturale nenule. Elementele șirului sunt numerotate de la stânga la dreapta începând cu poziția 1.

Cerință

Scrieți un program care să determine răspunsul pentru întrebări de următoarele tipuri: 1. Care este cea mai din stânga poziție care conține o valoare strict mai mare decât toate cele din dreapta sa? – întrebare de tipul 1 2. Care sunt pozițiile care conțin valori strict mai mari decât toate cele din stânga lor? – întrebare de tipul 2 3. Dacă fiecărui element aflat între prima și ultima apariție a maximului i-am mări valoarea pentru a ajunge egal cu maximul, care este suma totală a valorilor adăugate? – întrebare de tipul 3

Date de intrare

Fișierul de intrare sir.in conține pe prima linie un număr C (care poate fi 1, 2 sau 3), indicând tipul întrebării. Pe linia a doua se află un număr natural N, reprezentând numărul de elemente din șir. Pe a treia linie a fișierului de intrare se află N numere naturale, reprezentând elementele șirului, date de la stânga la dreapta (cel mai din stânga are poziția 1 și cel mai din dreapta are poziția N). Numerele de pe această linie sunt separate prin câte un spațiu.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.". Dacă C = 1, fișierul de ieșire sir.out trebuie să conțină un număr natural ce reprezintă răspunsul la o întrebare de tipul 1. Dacă C = 2, fișierul de ieșire trebuie să conțină, separați prin câte un spațiu și în ordine crescătoare, indicii determinați ca răspuns la o întrebare de tipul 2. Dacă C = 3, fișierul de ieșire trebuie să conțină un număr ce reprezintă răspunsul la o întrebare de tipul 3. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricții și precizări

• 1 ≤ C ≤ 3
• 1 ≤ N ≤ 100.000
• Numerele din șirul dat sunt cuprinse între 1 și 10.000, inclusiv.
• Pentru teste în valoare de 24 de puncte avem C = 1.
• Pentru teste în valoare de 32 de puncte avem C = 2.
• Pentru teste în valoare de 44 de puncte avem C = 3.

Exemple

Exemplu 1

sir.in

1

7

3 2 2 5 3 5 4

sir.out

6

Explicatie

Cea mai din stânga poziție a unei valori care este mai mare decât toate cele din dreapta sa este 6 (acolo unde se află valoarea 5)

Exemplu 2

sir.in

2

7

3 2 2 5 3 5 4

sir.out

1 4

Explicatie

1 și 4 sunt pozițiile unde se află valori mai mari decât toate cele din stânga lor.

Exemplu 3

sir.in

3

8

3 2 2 5 3 1 5 4

sir.out

6

Explicatie

Maximul fiind 5, conform explicației de la întrebarea de tipul 3, trebuie mărite două elemente pentru a ajunge egale cu 5. Acestea sunt cel aflat pe poziția 5 (de mărit cu 2) precum și cel de pe poziția 6 (de mărit cu4). Suma valorilor cu care avem de mărit este 2 + 4 = 6.

Exemplu 4

sir.in

3

5

3 2 7 5 3

sir.out

0

Explicatie

Maximul este 7 și apare o singură dată, deci nu se mai mărește nicio valoare.

Rezolvare

<syntaxhighlight lang="python" line="1"> def citeste_n():

   while True:
       try:
           with open("sir.in") as fin:
               c = int(fin.readline().strip())
               n = int(fin.readline().strip())
               if 1 <= c <= 3 and 1 <= n <= 100000:
                   print("Datele sunt corecte.")
                   return c, n
               else:
                   print("Datele nu sunt conform restrictiilor impuse.")
       except ValueError:
           print("Trebuie introduse doar numere intregi.")

def citeste_valori(n):

   valori = []
   with open("sir.in") as fin:
       fin.readline()
       fin.readline()
       for line in fin:
           for valoare in line.split():
               try:
                   valoare = int(valoare)
                   if valoare > 1 and valoare <= 10000:
                       print("Datele sunt corecte.")
                       valori.append(valoare)
                   else:
                       print("Datele nu sunt conform restricțiilor impuse.")
               except ValueError:
                   print("Trebuie introduse doar valori naturale cu mai putin de 9 cifre.")
   return valori

def sir(c, n, valori):

   # Cerinta 1
   if c == 1:
       max_val = valori[0]
       max_pos = 0
       ans = -1
       for i in range(1, n):
           if valori[i] > max_val:
               max_val = valori[i]
               max_pos = i
           elif valori[i] < max_val and i > max_pos:
               ans = max_pos + 1
               break
       with open("sir.out", "w") as fout:
           fout.write(str(ans))

   # Cerinta 2
   elif c == 2:
       max_val = valori[0]
       ans = []
       for i in range(1, n):
           if valori[i] > max_val:
               max_val = valori[i]
           elif valori[i] < max_val and i > 1:
               ans.append(str(i))
       with open("sir.out", "w") as fout:
           fout.write(" ".join(ans))

   # Cerinta 3
   elif c == 3:
       max_val = max(valori)
       max_pos = [i for i, j in enumerate(valori) if j == max_val]
       ans = 0
       for i in range(max_pos[0]+1, max_pos[-1]):
           ans += max_val - valori[i]
       with open("sir.out", "w") as fout:
           fout.write(str(ans))

if _name_ == "_main_":

   c, n = citeste_n()
   valori = citeste_valori(n)
   sir(c, n, valori)

</syntaxhighlight>

Explicatie

Acest cod este o implementare Python a unui algoritm pentru rezolvarea unei probleme matematice, descrisă în enunțul pe care l-ai furnizat anterior.

Funcția citeste_n este utilizată pentru a citi valorile necesare din fișierul de intrare, respectiv tipul întrebării c și lungimea șirului n. Această funcție verifică dacă valorile citite sunt valide în conformitate cu restricțiile impuse de cerințe și returnează valorile citite.

Funcția citeste_valori este utilizată pentru a citi valorile din fișierul de intrare și verifica dacă sunt valide. Aceasta construiește o listă de valori valori și o returnează.

Funcția sir primește lista de valori valori și implementează algoritmii necesari pentru a determina răspunsurile la întrebările specifice. În funcție de tipul întrebării c, se aplică o strategie diferită pentru a obține rezultatul corect. Rezultatele sunt scrise în fișierul de ieșire "sir.out".

În final, se citește tipul întrebării și lista de valori din fișierul de intrare și se apelează funcția sir pentru a obține rezultatul.