Fişierul intrare/ieşire:panouri.in, panouri.outSursăONI 2006
AutorConstantin GalatanAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Panouri

Pe autostrada "Soarele Estului " sunt asezate de-a lungul soselei, la distante egale, panouri publicitare ale unor firme. Aceeasi firma, poate sa aiba mai multe panouri publicitare si fiecare panou poate sa apara in mai multe locuri. Tipurile de panouri se identifica prin numere naturale, numarul total de panouri fiind N.
Firma "X Corporation" are panouri de T tipuri diferite. Firma a primit aprobarea construirii unui mare complex turistic in apropierea autostrazii; de aceea, pentru alegerea locului, este interesata si de urmatorul aspect: care este lungimea minima de sosea, in care se pot intalni, toate cele T tipuri de panouri publicitare ale firmei, indiferent de ordinea acestora, si indiferent daca intre ele se mai interpun sau nu panouri ale altor firme.

Cerinta

Cunoscand N - numarul total de panouri de la marginea autostrazii si ordinea amplasarii lor, ca si cele T tipuri de panouri amplasate de firma, determinati numarul minim de intervale dintre doua panouri intre care firma "X Corporation" isi regaseste toate panourile sale.

Date de Intrare

Fisierul de intrare panouri.in are pe prima linie numerele N si T. Pe urmatoarele N linii, sunt N numere naturale, nu neaparat diferite, cate unul pe linie, fiecare numar reprezentind tipul panoului respectiv, iar incepand cu linia N + 2, cate unul pe linie, cele T tipuri de panouri diferite al firmei.

Date de Iesire

Fisierul de iesire panouri.out va contine pe prima linie un singur numar intreg pozitiv L, reprezentand numarul cerut, sau -1 in caz ca nu exista solutie.

Restrictii si precizari

  • 1 ≤ N ≤ 200.000
  • 1 ≤ T ≤ 20.000
  • Toate numerele reprezentand panouri sunt numere naturale din intervalul [1..20.000]

Exemple

panouri.inpanouri.out
6 2
1
2
3
5
3
1
5
1
2
8 3
5
1
3
3
5
4
2
1
3
1
4
4

Explicatii

  • Sunt N = 6 panouri : 1 2 3 5 3 1. Firma are T = 2 tipuri de panouri: 5 si 1. Cea mai scurta secventa care contine elementele 5 si 1, este intre panourile al 4 – lea si al 6 -lea , si contine 2 intervale.
  • Sunt N = 8 panouri de tipurile: 5 1 3 3 5 4 2 1. Firma are T = 3 tipuri de panouri: 3, 1 si 4. Cea mai scurta secventa care contine elementele 1, 3 si 4, este intre al 2 lea si al 6-lea panou, si contine 4 intervale.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content