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

Dacă C=1, atunci fișierul de ieșire pp.out va conține pe fiecare dintre primele T linii 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 fișierul de ieșire pp.out va conține pe fiecare dintre primele T linii 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.

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: 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: 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: Date de intrare gresite!

Rezolvare

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 suma(numere, perechi):

   for pereche in perechi:
       print(sum(numere[pereche[0]-1:pereche[1]]))

def nr_perechi(numere, perechi):

   for pereche in perechi:
       nr = 0
       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)

def 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):
       return print("Date de intrare gresite!")

   if c == 1:
       suma(numere, perechi)
   elif c == 2:
       nr_perechi(numere, perechi)

if __name__ == '__main__':

   main()

</syntaxhighlight>