Vizualizare sursă pentru „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 ==
<syntaxhighlight lang="python" line="1">
# 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")

</syntaxhighlight>