2051 - PP

Cerința

Se consideră un șir de N numere naturale nenule ordonate crescător a[1]≤a[2]≤...≤a[N]. În legătură cu acest șir de numere ne interesează perechile de poziții (i,j) cu 1≤i<j≤N și a[i]≠a[j] sau ne interesează suma elementelor anumitor secvențe.

Se cere să se scrie un program care să citească un număr C reprezentând tipul cerinței, un șir de N numere naturale nenule ordonate crescător a[1]≤a[2]≤...≤a[N] și T perechi de numere naturale (p[k],q[k]) cu 1≤p[k]<q[k]≤N și 1≤k≤T și apoi:

(1) Dacă C=1, atunci trebuie să se determine pentru fiecare pereche dată de numere naturale (p,q) suma a[p]+a[p+1]+...+a[q].

(2) Dacă C=2, atunci trebuie să se determine pentru fiecare pereche dată de numere naturale (p,q) numărul de perechi (i,j) care respectă simultan condițiile p≤i<j≤q și a[i]≠a[j].

Date de intrare

Fișierul de intrare pp.in conține pe prima linie numărul natural C. Pe al doilea rând se află numărul N. Pe al treilea rând sunt scrise N numere naturale ordonate crescător și separate prin câte un spațiu. Pe al patrulea rând este scris numărul natural T, iar pe fiecare dintre următoarele T rânduri câte două numere naturale separate prin câte un spațiu.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

Dacă C=1, atunci pe fiecare din următoarele T rânduri va fi afișat câte un număr natural. Al k-lea număr va reprezenta suma elementelor cuprinse între pozițiile p[k] și q[k] inclusiv.

Dacă C=2, atunci pe fiecare din următoarele T rânduri va fi afișat câte un număr natural. Al k-lea număr va reprezenta numărul cerut de perechi de indici cuprinși între poziţiile p[k] şi q[k] inclusiv.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

• 1 ≤ p[i] < q[i] ≤ N ≤ 100 000
• 1 ≤ a[1] ≤ a[2] ≤ ... ≤ a[N] ≤ 100 000
• 1 ≤ T ≤ 1000

Exemplu 1

Intrare

1

5

1 2 3 3 3

2

1 4

2 5

Ieșire

Datele de intrare corespund restricțiilor impuse.

9

11

Explicație

Suntem în cazul C=1. Prima pereche (p,q) este (1,4). Suma valorilor din secvență este 1+2+3+3=9. A doua pereche (p,q) este (2,5). Suma valorilor din secvență este 2+3+3+3=11.

Exemplu 2

Intrare

2

5

1 2 3 3 3

2

1 4

2 5

Ieșire

Datele de intrare corespund restricțiilor impuse.

5

3

Explicație

Suntem în cazul C=2. Prima pereche (p,q) este (1,4). Perechile de poziții care conțin numere diferite între ele sunt (1,2), (1,3), (1,4), (2,3), (2,4). Deci sunt 5 perechi.

A doua pereche (p,q) este (2,5). Perechile de poziții care conțin numere diferite sunt (2,3), (2,4), (2,5). Deci sunt 3 perechi.

Exemplu 3

Intrare

1 5

1 2 3 3 3

2

1 4

5 2

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 2051 PP

def conditii_perechi(n, perechi):

   for pereche in perechi:
       if not 1 <= pereche[0] < pereche[1] <= n <= 100_000:
           return False

   return True

def conditii(n, numere, perechi):

   restrictii = (
       n == len(numere),
       1 <= len(perechi) <= 1000,
       sorted(numere) == numere,
       1 <= numere[0] <= numere[-1] <= 100_000,
       conditii_perechi(n, perechi)
   )

   return all(restrictii)

def pp(c, numere, perechi):

   if c == 1:
       # A și B fiind elementele din pereche, se îmsumează elementele din intervalul [A, B]
       for pereche in perechi:
           print(sum(numere[pereche[0] - 1:pereche[1]]))
           # Scădem 1 din A pentru că indexarea în Python începe de la 0
   elif c == 2:
       for pereche in perechi:
           nr = 0
           # Pentru elementele din intervalul [A, B], verificăm dacă există elemente egale
           for i in range(pereche[0] - 1, pereche[1]):
               for j in range(i + 1, pereche[1]):
                   if numere[i] != numere[j]:
                       nr += 1
           print(nr)

if __name__ == '__main__':

   c = int(input())
   n = int(input())
   numere = [int(x) for x in input().split()]
   t = int(input())
   perechi = []
   for i in range(t):
       perechi.append([int(x) for x in input().split(" ")])

   if not conditii(n, numere, perechi):
       print("Datele de intrare nu corespund restricțiilor impuse.")
   else:
       print("Datele de intrare corespund restricțiilor impuse.")
       pp(c, numere, perechi)

</syntaxhighlight>