2466 - Proiectoare

Primăria a montat, pe faleza din Mamaia, N proiectoare așezate liniar, pentru fiecare cunoscându-se zona de faleză pe care o luminează, sub forma unui interval [s, d], unde s și d (s < d) sunt numere naturale reprezentând distanțele față de punctul unde începe faleza. Pentru a verifica eficiența iluminării falezei, tehnicienii primăriei vor să determine intervalul de faleză de lungime maximă, iluminat de cel mult K proiectoare, conținut într-un interval [X, Y] precizat. Pentru a fi siguri de corectitudinea rezultatelor obținute, tehnicienii realizează Q astfel de verificări.

Cerința

Dându-se Q intervale de forma [Xi, Yi] determinați, pentru fiecare dintre acestea, câte un interval de lungime maximă iluminat de cel mult K proiectoare. Dacă nici un proiector nu iluminează vreo porțiune din intervalul [Xi, Yi] se va afișa valoarea 0.

Date de intrare

Datele de intrare se citesc din fișierul text proiectoarein.txt, care are structura următoare:

• pe prima linie se află valorile naturale N, Q, K, separate prin câte un spațiu, cu semnificația din enunț;
• pe următoarele N linii se află câte o pereche de valori naturale Si, Di, separate printr-un spațiu, reprezentând intervalele iluminate de fiecare proiector;
• pe următoarele Q linii se află câte o pereche de valori naturale Xi, Yi, separate printr-un spațiu, reprezentând intervalele pentru care se realizează verificările.

Date de ieșire

În fișierul text proiectoareout.txt se vor scrie Q linii; pe linia i (1 ≤ i ≤ Q) se va scrie un număr natural reprezentând lungimea intervalului obținut ca răspuns la verificarea efectuată pentru intervalul [Xi, Yi].

Restricții și precizări

• 0 ≤ S < D ≤ 1 000 000 000
• 1 ≤ K ≤ N ≤ 100 000
• 1 ≤ Q ≤ 100 000
• Pentru teste în valoare de 11 puncte, K = 1 și n ≤ 2000 și Q ≤ 2000
• Pentru teste în valoare de alte 38 puncte, K = 1
• Pentru teste în valoare de alte 21 puncte, K = 2
• Pentru teste în valoare de alte 10 puncte, K ≤ 30

Exemplul 1

proiectoarein.txt

5 5 1

1 4

2 3

3 6

4 7

4 8

1 10

2 5

3 4

6 8

8 9

proiectoareout.txt

Datele introduse corespund restricțiilor impuse.

4

2

1

2

0

Explicație

Pentru verificarea [1,10] cel mai lung interval complet iluminat este [4,8] cu lungimea 4. Pentru verificarea [2,5] cele mai lungi intervale complet iluminate sunt [2,4] și [3,5], ambele au lungimea 2. Pentru verificarea [3,4] cel mai lung interval complet iluminat este [3,4] cu lungimea 1. Pentru verificarea [6,8] cel mai lung interval complet iluminat este [6,8] cu lungimea 2. Pentru verificarea [8,9] se afișează valoarea 0.

Exemplul 2

proiectoarein.txt

5 5 1

1 4 2

2 3 1

3 6 1

4 7 1

4 8 1

1 10

2 5

3 4

6 8

8 9

proiectoareout.txt

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

# 2466 - Proiectoare
def validare(lista_proiectoare1, lista_verificari1, k_max1):           # functia de validare a datelor de intrare
    n, q = len(lista_proiectoare1), len(lista_verificari1)
    if not (1 <= k_max1 <= n <= 100000 and 1 <= q <= 100000):
        raise ValueError

    for s, d, k_proiector in lista_proiectoare1:
        if not (0 <= s < d <= 1000000000 and 1 <= k_proiector <= n):
            raise ValueError

    if k_max1 == 1 and n > 2000 and q > 2000:
        raise ValueError

    if k_max1 > 30:
        raise ValueError

    fisier_iesire.write("Datele de intrare corespund restrictiilor impuse\n")

# functia de rezolvare va fi implementata aici


if __name__ == '__main__':
    fisier_intrare = open("proiectoarein.txt", "r")         # declararea fisierelor
    fisier_iesire = open("proiectoareout.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

    try:
        lista_proiectoare = []
        lista_verificari = []
        k_max = 0
        # citirea si prelucrarea datelor de intrare se face aici

        validare(lista_proiectoare, lista_verificari, k_max)                 # apelul functiei de validare
        # apelul functiei de rezolvare se face aici

    except ValueError:
        fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")