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

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