3692 - maxime

Cerinta

Se dă un șir V cu N valori naturale nenule, memorate pe poziții consecutive începând cu poziția 1. Notăm cu S următoarea secvență de cod aplicată asupra sa:

(C/C++) maxim = 0; rep = 0; for(i = 1; i <= N; i++) if(V[i] > maxim) maxim = V[i]; else if(V[i] == maxim) rep++; Considerăm operația de eliminare din V a elementului de pe o anumită poziție dată P. În urma operației de eliminare elementele de pe pozițiile P + 1, P + 2, ..., N ajung pe o poziție cu 1 mai mică iar N scade cu 1.

Dându-se mai multe operații de eliminare(independente una de alta, adică fiecare se aplică asupra șirului inițial, nu după operația anterioară), să se determine valoarea variabilei rep dacă am aplica secvența S asupra șirului obținut după fiecare operație de eliminare.

Date de intrare

Fisierul maxime.in conține pe prima linie un număr natural N. Pe linia a doua se află N numere naturale nenule, separate prin câte un spațiu. Pe linia următoare se află un număr M reprezentând numărul de operații de eliminare. Linia următoare conține M numere, cuprinse între 1 și N, ce reprezină poziția din șir a elementului la care se realizează eliminarea curentă. Numerele de pe această linie sunt separate prin câte un spațiu.

Date de iesire

Fișierul maxime.out conține pe primul rând M numere, separate prin câte un spațiu, reprezentând valoarea variabilei rep obținută aplicând secvența S după fiecare operație de eliminare.

Restrictii si precizari

• 2 ≤ N ≤ 100.000
• 1 ≤ Vi ≤ 100.000
• 1 ≤ M ≤ 100.000
• 1 ≤ poziție eliminare ≤ N

Exemplul 1

intrare

6

3 1 3 8 1 8

3

2 5 6

iesire

Datele introduse corespund restrictiilor impuse.

2 2 1

Exemplul 2

intrare

9

4 2 4 8 2 9

6

5 7 5

iesire

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"

def calculeaza_rep(V):

   maxim = 0
   rep = 0
   for val in V:
       if val > maxim:
           maxim = val
       elif val == maxim:
           rep += 1
   return rep

def eliminare_element(V, P):

   del V[P - 1]
   return V

for P in [2, 5, 8]:

   V = eliminare_element(V, P)
   rep = calculeaza_rep(V)
   print(f"După eliminarea elementului de pe poziția {P}, rep = {rep}")

</syntaxhighlight>