.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » panouri

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
panouri


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
16MB / 1MB

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ţă

Cunoscând N - numărul total de panouri de la marginea autostrăzii şi ordinea amplasării lor, precum ş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 panouri.in are pe prima linie numerele N şi T. Pe următoarele N linii, sunt N numere naturale, nu neaparat 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 panouri.out 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.

Restricţii

1 ≤ N ≤ 15000
1 ≤ T ≤ 1000

Toate numerele reprezentând panouri sunt numere naturale din intervalul [1..1000].

Exemple

panouri.inpanouri.outExplicaţii
6 2 1 2 3 5 3 1 5 1 2 Sunt N = 6 panouri : 1 2 3 5 3 1. Firma are T = 2 tipuri de panouri: 5 şi 1.
Cel mai scurt interval care conţine elementele 5 şi 1, este între panourile al 4 – lea şi al 6 -lea , şi conţine 2 intervale.
8 3 5 1 3 3 5 4 2 1 3 1 4 4 Sunt N = 8 panouri de tipurile: 5 1 3 3 5 4 2 1. Firma are T = 3 tipuri de panouri: 3, 1 şi 4.
Cel mai scurt interval care conţine elementele 1, 3 şi 4, este între al 2 lea şi al 6-lea panou, şi conţine 4 intervale.

autor: Prof. Constantin Gălăţan
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2006: borg, diamant, matrice1, petrom, ratina, vitale, acolor, cifru1, evo, part, trasee, bombo, cub2, prieteni2, sg1, fact, limbaj, pereti, sant1, zumzi, adun, sport1, baschet1, mere3, roboti, tzigla, morse, powerpuff
De acelaşi autor: ozn, pod, numere, vikingi, furtuna, livada, teatru, iepuras2, kimberley, novel, friends2, stalpi, tabara, sport, randuri, powerpuff, cartele, joc15, stalpi1, autostrazi, telecab, pseudobil, harta2
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
Despre secvenţe: degrade, hora, simetric, egal, ruleta, ecran, sirag, pasi, firma, br, numere2, termen, div, teatru, repeat, ratb, 2sec, sport, pikachu, suma3, sir5, mare, hof, resturi, efort, xor1, livada1, diff, popic, guess, albine1, permutare, miere, atelier, obstacole, echilibru1, lcdr, 3max, ksecv, maxbin, meteo1, galbeni, maxp, secvp, split, secvente2, ausoara, sminus, munte3, cool, betisoare, unudoi, charlie, lasere, arc, dominant, restaurare, roua
surse trimise | ajutor