2249 - panouri

Enunt

Pe autostrada Soarele Estului sunt aşezate de-a lungul şoselei, la distanţe egale, panouri publicitare ale unor firme. Aceeaşi firmă, poate să aibă mai multe panouri publicitare şi fiecare panou poate să apară în mai multe locuri. Panourile se identifică prin numere naturale, numărul total de panouri fiind N. Firma X Corporation are panouri de T tipuri diferite. Firma a primit aprobarea construirii unui mare complex turistic în apropierea autostrăzii; de aceea, pentru alegerea locului, este interesată şi de următorul aspect: care este lungimea minimă de şosea, în care se pot întâlni, toate cele T tipuri de panouri publicitare ale firmei, indiferent de ordinea acestora, şi indiferent dacă între ele se mai interpun sau nu panouri ale altor firme.

Cerința

Cunoscând N – numărul total de panouri de la marginea autostrăzii şi ordinea amplasării lor, ca şi cele T tipuri de panouri amplasate de firmă, determinaţi numărul minim de intervale dintre două panouri între care firma X Corporation îşi regăsește toate panourile sale.

Date de intrare

Fișierul de intrare panouriIN.txt are pe prima linie numerele N şi T. Pe următoarele N linii, sunt N numere naturale, nu neapărat diferite, câte unul pe linie, reprezentând panourile, iar începând cu linia N + 2, câte unul pe linie, cele T tipuri de panouri diferite al firmei.

Date de ieșire

Fișierul de ieșire panouriOUT.txt va conţine pe prima linie un singur număr întreg pozitiv L, reprezentând numărul cerut, sau -1 în caz că nu există soluţie. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 1 ≤ N ≤ 15000
• 1 ≤ T ≤ 1000
• Toate numerele reprezentând panouri sunt numere naturale din intervalul [1..1000].

Exemplul 1:

panouriIN.txt

6 2
1
2
3
5
3
1
5
1

panouriOUT.txt

2

Exemplul 2:

panouriIN.txt

6 2
1
2
3
5
3
1
5
1

panouriOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def read_input():

   with open("panouriIN.txt", "r") as file:
       n, t = map(int, file.readline().split())
       v = []
       for _ in range(n):
           panou = file.readline().strip()
           if panou:
               v.append(int(panou))
       panou_firma = set()
       for _ in range(t):
           panou = file.readline().strip()
           if panou:
               panou_firma.add(int(panou))
   return n, t, v, panou_firma

def write_output(result):

   with open("panouriOUT.txt", "w") as file:
       file.write(str(result))

def validate_constraints(n, t, v, panou_firma):

   if not (1 <= n <= 15000 and 1 <= t <= 1000):
       write_output("Datele nu corespund restrictiilor impuse")
       return False
   for panou in v:
       if not 1 <= panou <= 1000:
           write_output("Datele nu corespund restrictiilor impuse")
           return False
   return True

def solve_problem(n, t, v, panou_firma):

   fr = [0] * 1001
   firma = []
   lmin = 100000
   k = 0

   for i in range(n):
       if v[i] in panou_firma:
           firma.append((v[i], i))
           if fr[v[i]] == 0:
               k += 1
           fr[v[i]] += 1

       if k == t:
           while firma and fr[firma[0][0]] > 1:
               fr[firma[0][0]] -= 1
               firma.pop(0)
           lmin = min(lmin, i - firma[0][1])
           fr[firma[0][0]] = 0
           firma.pop(0)
           k -= 1

   return lmin

def main():

   n, t, v, panou_firma = read_input()
   if validate_constraints(n, t, v, panou_firma):
       result = solve_problem(n, t, v, panou_firma)
       write_output(result)

if __name__ == "__main__":

   main()

</syntaxhighlight>