2051 - PP

From Bitnami MediaWiki
Revision as of 13:04, 20 March 2023 by Ardelean Alexandru (talk | contribs) (Pagină nouă: ==Cerința== Se consideră un șir de <code>N</code> numere naturale nenule ordonate crescător <code>a<sub>[1]</sub>≤a<sub>[2]</sub>≤...≤a<sub>[N]</sub></code>. În legătură cu acest șir de numere ne interesează perechile de poziții <code>(i,j)</code> cu <code>1≤i<j≤N</code> și <code>a<sub>[i]</sub>≠a<sub>[j]</sub></code> sau ne interesează suma elementelor anumitor secvențe. Se cere să se scrie un program care să citească un număr <code>C</code> re...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

<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 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>