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

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


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

Alina este mare iubitoare de teatru. Directorul teatrului i-a oferit şansa să joace în mai multe spectacole, ca figurant, deocamdată. Costumiera de scenă a decis să-i dea C costume diferite dintre cele care sunt destinate acestei stagiuni. Alina va duce costumele acasă şi le va ajusta ca să-i vină bine. Stagiunea durează N zile consecutive şi în fiecare zi se joacă câte o piesă. Aceeaşi piesă se va juca, desigur în una sau mai mai multe zile ale stagiunii. Fiecărei piese i se asociază un unic costum de figurant, deci pentru fiecare piesă în care joacă, Alina trebuie să îmbrace un singur costum, acela asociat piesei respective. Costumele de figuranţi sunt identificate prin literele mari ale alfabetului englez: A, B, C, …, X, Y, Z. Alina are voie să-şi aleagă cele C costume diferite.

Cerinţă

Cunoscând costumul asociat fiecărei zile a stagiunii, ajutaţi-o pe Alina să-şi aleagă cele C costume diferite, în aşa fel încât să poată juca într-un număr cât mai mare de piese consecutive.

Date de intrare

Fişierul de intrare teatru.in conţine pe prima linie două numere naturale Z şi C despărţite printr-un spaţiu. Z este numărul de zile din stagiune, iar C este numărul de costume diferite pe care Alina le poate primi. Pe linia a doua, se găsesc Z caractere, litere mari ale alfabetului englez. Caracterul al i-lea identifică costumul de figurant care trebuie îmbrăcat în spectacolul din ziua i.

Date de ieşire

În fişierul de ieşire teatru.out se va scrie pe prima linie un număr natural N, reprezentând numărul maxim de spectacole consecutive în care Alina poate juca. Pe linia a doua se scriu N caractere, fără spaţii între ele, corespunzătoare costumelor care vor fi îmbrăcate în cele N piese de teatru alese, în ordinea spectacolelor în care va juca. Dacă există mai multe soluţii de lungime N, atunci se afişează cea căreia îi corespunde o zi de început mai aproape de începutul stagiunii.

Restricţii

1 <= Z <= 55000
1 <= C <= 26
C <= Z
Pentru 20% dintre teste, Z <= 350

Exemple

teatru.inteatru.out
5 KUFKF 10 3 XKUFKFEGXG
15 4 IAJRAMRCZJJCDNS 6 AJRAMR
25 5 LDSDGIFAURLPTZLDLPNLEGFRN 8 LPTZLDLP

autor: Prof. Constantin Gălăţan
propunător: Stud. Vlad Manea
Facultatea de Informatică
vlad.c.manea@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2008: ab2, iepuras, palind, auto, div, pm, submat, reteta2, rezervatie, creioane, melci, mere2, felinare, joc3, 2numere, fi, tablou, borcane, mexc, tcast, dep, dist1, stiva, banda, pavare, poarta, aranjare, bile4, subgeom, albinuta1, curent, pviz, atac2, virus
De acelaşi autor: ozn, pod, numere, vikingi, furtuna, livada, iepuras2, kimberley, novel, friends2, stalpi, tabara, sport, randuri, panouri, 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, 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, panouri, 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, repeat, ratb, 2sec, sport, pikachu, suma3, panouri, 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