1685 - Dif 2

Enunț

Sandu a studiat la ora de informatică mai multe aplicații cu vectori de numere naturale, iar acum are de rezolvat o problemă interesantă. Se dă un șir X=(X[1],X[2],…,X[n]) de numere naturale nenule și două numere naturale p1 și p2, unde p1<p2. Sandu trebuie să construiască un nou șir Y=(Y[1],Y[2],…,Y[n*n]) cu n*n elemente obținute din toate produsele de câte două elemente din șirul X (fiecare element din șirul Y este de forma X[i]*X[j], 1<=i, j<=n). Sandu are de calculat două valori naturale d1 și d2 obținute din șirul Y. Valoarea d1 este egală cu diferența maximă posibilă dintre două valori ale șirului Y. Pentru a obține valoarea d2, Sandu trebuie să considere că șirul Y are elementele ordonate descrescător iar d2 va fi diferența dintre valorile aflate pe pozițiile p1 și p2 în șirul ordonat descrescător. Sandu a găsit rapid valorile d1 și d2 și, pentru a le verifica, vă roagă să le determinați și voi.

Cerința

Dându-se șirul X cu n elemente și valorile p1 și p2, determinați valorile d1 și d2.

Date de intrare

Fișierul de intrare dif2in.txt conține pe prima linie un număr natural C care poate fi doar 1 sau 2. Dacă C=1, atunci pe linia a doua se va afla numărul natural n. Dacă C=2, atunci pe linia a doua se vor afla numerele naturale n p1 p2 separate prin câte un spațiu. În ambele cazuri, pe următoarele n linii se vor afla elementele șirului X, câte un număr natural pe fiecare linie a fișierului.

Date de ieșire

În cazul C=1, fișierul de ieșire dif2out.txt va conține pe prima linie valoarea d1 egală cu diferența maximă dintre oricare două valori din șirul Y. În cazul C=2 fișierul de ieșire va conține pe prima linie un număr natural d2 reprezentând diferența dintre valorile aflate pe pozițiile p1 și p2 din șirul Y, presupunând că ar fi ordonat descrescător.

Restricții și precizări

• 2 ⩽ n ⩽ 299.999
• 1 ⩽ p1 ⩽ p2-1 ⩽n^2
• 1 ⩽ x[i] ⩽ 299.999 i=1...n

Exemplul 1

Intrare

dif2in.txt

1

4

3

5

2

6

Ieșire

Datele de intrare corespund restricțiilor impuse

dif2out.txt

32

Explicație

Atenție, C=1, deci se rezolvă doar cerința 1! Valoarea maximă d1 va fi 32 și se obține efectuând diferența dintre 6*6 și 2*2.

Exemplul 2

Intrare

dif2in.txt

2

4 5 11

3

5

2

6

Ieșire

Datele de intrare corespund restricțiilor impuse

dif2out.txt

8

Explicație

Atenție, C=2, deci se rezolvă doar cerința 2! Se obțin în Y următoarele 16 valori: 3*3, 3*5, 3*2, 3*6, 5*3, 5*5, 5*2, 5*6, 2*3, 2*5, 2*2, 2*6, 6*3, 6*5, 6*2, 6*6. Valoarea d2 va fi 8, deoarece dacă vom considera șirul Y ordonat descrescător (36, 30, 30, 25, 18, 18, 15, 15, 12, 12, 10, 10, 9, 6, 6, 4), atunci Y[5]-Y[11]=18-10=8

Exemplul 3

Intrare

dif2in.txt

3

4

3

5

2

6

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#1685 - Dif2

def validare_input(c, n, p1, p2, x):
    if not (3 < n < 300000):
        raise ValueError("Valoarea lui n nu respectă restricțiile.")
    if c == 2 and not (1 <= p1 < p2 <= n * n):
        raise ValueError("Valorile lui p1 și p2 nu respectă restricțiile.")
    if not all(1 <= x < 300000 for x in x):
        raise ValueError("Elementele șirului x nu respectă restricțiile.")


def calcul_d1(x):
    y = [x * y for x in x for y in x]
    return max(y) - min(y)


def calcul_d2(x, p1, p2):
    y = sorted([x * y for x in x for y in x], reverse=True)
    return y[p1 - 1] - y[p2 - 1]


with open("dif2in.txt", "r") as file:
    c = int(file.readline().strip())
    if c == 1:
        n = int(file.readline().strip())
        p1 = None
        p2 = None
    else:
        n, p1, p2 = map(int, file.readline().strip().split())

    x = [int(file.readline().strip()) for _ in range(n)]

    if validare_input(c, n, p1, p2, x):
        print("Datele de intrare corespund restricțiilor impuse")

        if c == 1:
            d1 = calcul_d1(x)
            with open("dif2out.txt", "w") as out_file:
                out_file.write(str(d1))
        else:
            d2 = calcul_d2(x, p1, p2)
            with open("dif2out.txt", "w") as out_file:
                out_file.write(str(d2))
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)