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

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


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

Într-un şir de biţi, o secvenţă este o succesiune maximală nevidă de biţi alăturaţi identici. De exemplu, şirul 0011101 conţine patru secvenţe: 00, 111, 0 şi 1. Pentru orice secvenţă, lungimea sa este dată de numărul de biţi ai secvenţei. În exemplul de mai sus, cele patru secvenţe au lungimile 2, 3, 1 şi respectiv 1.

Cerinţă

Scrieţi un program care citeşte trei numere naturale N, T şi K şi determină numărul de şiruri de N biţi care conţin exact T secvenţe, orice secvenţă având lungimea între 1 şi K. Pentru că acest număr poate fi foarte mare, trebuie să determinaţi acest număr modulo 2011.

Date de intrare

Fişierul de intrare secvbiti.in conţine pe prima linie trei numere naturale N, T şi K, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire secvbiti.out va conţine o singură linie pe care veţi scrie numărul şirurilor de N biţi care conţin exact T secvenţe, fiecare secvenţă având lungimea cel mult K, modulo 2011.

Restricţii

4 ≤ N ≤ 2000
2 ≤ T ≤ N / 2
1 ≤ K ≤ N

Exemple

secvbiti.insecvbiti.outExplicaţii
5 2 4 8 Şirurile de 5 biţi care conţin exact 2 secvenţe, fiecare secvenţă având lungimea maxim 4 sunt: 00001, 11110, 00011, 11100, 00111, 11000, 01111, 10000. Evident, 8 mod 2011 = 8.

autor: Prof. Dan Pracsiu
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la Finala .campion 2010: expo, mine, popic, arctir, guess, orientare, activ
De acelaşi autor: cai, rebus, harta, comun, axa, sir, ocean14, reduceri, div3, patrate6, vot, reziduu, accesibil, predecesor, permutari, scanduri, ordonare, xor1, paltrei, triunghi1, 123, traseu1, parbit, petrecere, 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, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, 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