Editing 2051 - PP


==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> reprezentând tipul cerinței, 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> și <code>T</code> perechi de numere naturale <code>(p[k],q[k])</code> cu <code>1≤p[k]<q[k]≤N</code> și <code>1≤k≤T</code> și apoi:

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

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

==Date de intrare==
Fișierul de intrare <code>pp.in</code> conține pe prima linie numărul natural <code>C</code>. Pe al doilea rând se află numărul <code>N</code>. Pe al treilea rând sunt scrise <code>N</code> numere naturale ordonate crescător și separate prin câte un spațiu. Pe al patrulea rând este scris numărul natural <code>T</code>, iar pe fiecare dintre următoarele <code>T</code> rânduri câte două numere naturale separate prin câte un spațiu.
==Date de ieșire==
Dacă <code>C=1</code>, atunci fișierul de ieșire <code>pp.out</code> va conține pe fiecare dintre primele <code>T</code> linii câte un număr natural. Al <code>k</code>-lea număr va reprezenta suma elementelor cuprinse între pozițiile <code>p[k]</code> și <code>q[k]</code> inclusiv.

Dacă <code>C=2</code>, atunci fișierul de ieșire <code>pp.out</code> va conține pe fiecare dintre primele <code>T</code> linii câte un număr natural. Al <code>k</code>-lea număr va reprezenta numărul cerut de perechi de indici cuprinși între poziţiile <code>p[k]</code> şi <code>q[k]</code> inclusiv.

==Restricții și precizări==

*<code>1 ≤ p[i] < q[i] ≤ N ≤ 100 000</code>
*<code>1 ≤ a[1] ≤ a[2] ≤ ... ≤ a[N] ≤ 100 000</code>
*<code>1 ≤ T ≤ 1000</code>

==Exemplu 1==
;Intrare
:1
:5
:1 2 3 3 3
:2
:1 4
:2 5
;Ieșire
:9
:11

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

==Exemplu 2==
;Intrare
:2
:5
:1 2 3 3 3
:2
:1 4
:2 5
;Ieșire
:5
:3

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

A doua pereche <code>(p,q)</code> este <code>(2,5)</code>. Perechile de poziții care conțin numere diferite sunt <code>(2,3)</code>, <code>(2,4)</code>, <code>(2,5)</code>. Deci sunt <code>3</code> 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">
#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>