2676 - Afise

Cerința

Fiind date lungimea zidului, câte unităţi sunt deteriorate, care este numărul maxim de panouri ce pot fi folosite şi care sunt unităţile de zid deteriorate, se cere să se determine lungimea minimă totală a panourilor care sunt folosite pentru a acoperi zona şi câte panouri se folosesc. Lungimea minimă o definim ca numărul total de unităţi de zid acoperite astfel încât să fie mascate zonele problemă. Pentru acoperirea unităţilor de zid deteriorate, nu este neapărat necesar să se folosească toate panourile. Numărul de panouri folosite fiind limitat există posibilitatea să fie acoperite şi zone din zid care sunt curate.

Date de intrare

Fișierul de intrare afise.in conţine pe prima linie trei valori separate prin câte un spaţiu L n k, cu semnificația: L lungimea totală a zidului, n numărul de unităţi ce urmează a fi acoperite şi k numărul maxim de panouri ce pot fi folosite. Pe a doua linie separate prin câte un spațiu sunt n valori x1, x2, … , xn, unde xi reprezintă unitatea din zid care este acoperită de un afiș vechi. Valorile x1, x2, … , xn apar într-o ordine aleatoare.

Date de ieșire

Fișierul de ieșire afise.out va conține o singură linie cu două valori val Nk, ce reprezintă lungimea minimă totală folosită și numărul de panouri folosite astfel încât toate zonele deteriorate să fie acoperite.

Restricții și precizări

~ 0 < L ≤ 1000
~ 0 < n ≤ L
~ 0 < k ≤ L / 2

Exemplu 1

Intrare

afise.in

25 8 3

3 11 6 4 19 15 20 12

Ieșire

afise.out

11 3

Exemplu 2

Intrare

afise.in

10 4 6

7 3 8 1

Ieșire

afise.out

4 3

Rezolvare

#2676 - Afise
def acoperire_zid(L, n, k, unitati_deteriorate):
    unitati_deteriorate.sort()
    lungime_minima = 0
    panouri_folosite = 0

    if k >= n:
        lungime_minima = L
        panouri_folosite = n
    else:
        for i in range(n - k + 1):
            lungime_sectiune = unitati_deteriorate[i + k - 1] - unitati_deteriorate[i] + 1
            if lungime_sectiune > lungime_minima:
                lungime_minima = lungime_sectiune

        panouri_folosite = min(n, k)

    return lungime_minima, panouri_folosite

def main():
    with open("afise.in", "r") as file_in:
        L, n, k = map(int, file_in.readline().split())
        unitati_deteriorate = list(map(int, file_in.readline().split()))

    lungime_minima, panouri_folosite = acoperire_zid(L, n, k, unitati_deteriorate)

    with open("afise.out", "w") as file_out:
        file_out.write(f"{lungime_minima} {panouri_folosite}\n")

if __name__ == "__main__":
    main()