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

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


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

Se consideră un şir de N numere naturale, precum şi 3 numere naturale M, A, B.

Cerinţă

Să se determine numărul de subşiruri crescătoare ale şirului dat care au suma elementelor modulo M cuprinsă între A şi B.
Mai exact, dat fiind şirul a=(a1, a2, ..., aN), trebuie să determinăm numărul de subşiruri ale lui a (ai1<= ai2<= ...<= aik) (i1<i2<...<ik) cu proprietatea că A≤S%M≤B, unde S= ai1 + ai2 + ... + aik.

Date de intrare

Fişierul de intrare subsiruri.in va conţine pe prima linie numerele naturale N M A B. Pe a doua linie se află N numere naturale reprezentând elementele şirului dat. Valorile scrise pe aceeaşi linie sunt separate prin spaţii.

Date de ieşire

Fişierul de ieşire subsiruri.out va conţine o singură linie pe care va fi scris rezultatul modulo 666013.

Restricţii

  • 1 ≤ N, M, A, B ≤ 1000
  • Elementele şirului sunt numere naturale din intervalul [1, 1000]
  • Pentru 40% din teste N ≤ 250 (Atenţie!!! M, A, B ≤ 1000).
  • Un subşir are cel puţin un element.

Exemple

subsiruri.in subsiruri.out Explicaţii
3 13 5 10
34 29 23




2

Cele 2 subşiruri sunt :
34 ( 5 ≤ 34 % 13 ≤ 10)
23 (5 ≤ 23 % 13 ≤ 10)


Mircea Dima
Vrije Universiteit Amsterdam
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2011: ore, pegals, valet, xpn, efect, nrperm, b2k, sumdivprod, nr0, maxviz, oneton, oras1, ksecv, ripstick, antic, oak, nor, nrpomi, sumprod, paisprezece, cover1, prisme, gxor, progresii, anagramabil, zuma, nrpal, sdmin, lista, operatii1, codarb, codpatrat, adprod, puncte4, qtri, reconst, gsm, mijloc, trifoi, cubulete, romb, maxbin, albine2, probleme, triburi1, megascoala, 2ndesc
De acelaşi autor: votare, nkbiti, kperms, site, kbiti, kdist, oldest, mess, subs
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, 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, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre arbori indexaţi binar: echilibru1
surse trimise | ajutor