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

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


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

Se consideră numerele naturale n, k şi p şi un şir de n numere din mulţimea {1, 2, 3}. Acest şir îl împărţim în mai multe secvenţe de lungime cel mult k astfel încât, dacă în fiecare secvenţă notăm cu a1 numărul de valori de 1, cu a2 numărul de valori de 2 şi cu a3 numărul de valori 3, atunci să fie îndeplinite condiţiile (unde prin |x| am notat modulul lui x):

  • |a1 – a2| <= p cu condiţia ca a1 şi a2 să fie strict pozitive (dacă a1 şi/sau a2 sunt 0, condiţia nu trebuie verificată)
  • |a2 – a3| <= p cu condiţia ca a2 şi a3 să fie strict pozitive (dacă a2 şi/sau a3 sunt 0, condiţia nu trebuie verificată)
  • |a1 – a3| <= p cu condiţia ca a1 şi a3 să fie strict pozitive (dacă a1 şi/sau a3 sunt 0, condiţia nu trebuie verificată)

De exemplu, pentru n=13, k=8, p=1, şirul 1,2,1,1,2,3,3,2,2,2,1,1,3 il putem împărţi în două secvenţe: 1,2,1,1,2 şi 3,3,2,2,2,1,1,3. În prima secvenţă a1=3, a2=2, a3=0 şi |a1 – a2| <= 1, iar celelalte două module nu se vor calcula, pentru că a3 este 0. În secvenţa a doua, a1=2, a2=3, a3=3 şi deci diferenţa în modul dintre oricare două este mai mică sau egală cu 1.

Împărţirea în secvenţe nu este unică. Şirul din exemplul de mai sus se poate împărţi şi în 3 secvenţe de lungime cel mult k. Prima: 1,2,1,1,2,3,3, a doua:  2,2,2,1,1 şi a treia: 3

Cerinţă

Scrieţi un program care împarte şirul într-un număr minim de secvenţe de lungime cel mult k astfel încât fiecare secvenţă să respecte condiţiile.

Date de intrare

Fişierul de intrare 123.in conţine pe prima linie numerele n k p separate printr-un spaţiu. Pe linia a doua se află şirul de n valori din mulţimea {1, 2, 3}, valori scrise fără spaţiu între ele.

Date de ieşire

Fişierul de ieşire 123.out va conţine o singură linie pe care va fi scris un singur număr natural, reprezentând numărul minim de secvenţe în care se poate împărţi şirul.

Restricţii

  • 2 <= n <= 10 000
  • 1 <= p <= 100
  • 1 <= k <= 100

Exemplu

123.in 123.out
13 8 1
1211233222113
2
prof. Dan Pracsiu
Grupul Şcolar „Ştefan Procopiu” Vaslui
dpracsiu@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la XOR 2010: ordonare, xor1, paltrei, triunghi1, traseu1
De acelaşi autor: cai, rebus, harta, comun, axa, sir, ocean14, reduceri, div3, patrate6, vot, reziduu, accesibil, predecesor, permutari, scanduri, ordonare, xor1, paltrei, triunghi1, traseu1, parbit, petrecere, secvbiti, subm, triunghi3, cmmdcsecv, drumuri1, fillmat, secvb, siruri3, acces, segmente, echilibru1, broscute, ksecv, paisprezece, proddiv, perechi2, expeval, maxtri, combcuv, dfs, qtri, blis, maxbin, probleme, divider, eliminare, minm, genab, grafxy, matd3, azeval, matrixdel, speed, maxp, split, binremove, sminus, subsets, tcif, sprime, sir2dif, ecp, arbsum, robotzi, permtr, unudoi, matcnt, ssdj, dominant
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor