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

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


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

Miruna are un seif care este împărţit în mai multe compartimente, dispuse sub forma unei matrice cu N linii şi M coloane. Astfel, fiecărui compartiment îi pot fi asociate două coordonate x şi y reprezentand linia, respectiv coloana din care face parte.
Pentru a deschide un compartiment, este nevoie de o anumită cheie unică asociată. O echipă de hoţi a reuşit să facă rost de o parte dintre cele N*M chei, însă nu de toate. Se ştie faptul că hoţilor le lipsesc exact K chei.
Un compartiment de coordonate (x, y) este considerat a fi în siguranţă dacă sunt îndeplinite următoarele condiţii:
1. Hoţii nu au cheia asociată compartimentului.
2. Hoţii nu au cheia unui alt compartiment de coordonate (z, y), unde z<x şi diferenţa x-z ≤ L (unde L este indicele de siguranţă al seifului).

Cerinţă

Miruna nu ştie care sunt cheile care le lipsesc hoţilor. Fiecare set posibil de câte K chei determină o mulţime de compartimente care sunt în siguranţă. Ea ar dori să ştie câte seturi de K chei determină exact S compartimente care sunt în siguranţă.

Date de intrare

Fişierul de intrare seif.in conţine pe prima linie sunt scrise 5 numere întregi N M K L S, separate prin câte un singur spaţiu, având semnificaţia din enunţ.

Date de ieşire

Fişierul de ieşire seif.out va conţine o singură linie pe care va fi scris numărul de seturi de K chei lipsă pentru care exact S compartimente sunt în siguranţă, modulo 30011.

Restricţii

1 ≤ N, M ≤ 30
1 ≤ S ≤ K ≤ 30
1 ≤ L ≤ N

Exemple

seif.inseif.out
5 5 15 2 7 4825

autor: Stud. Andrei Grigorean
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la Finala .campion 2008: sir2, livada, drept, monede, ocean14, aztec, pendul, plopi
De acelaşi autor: fbr, 2sir, platforma, barfa, sumdif, cartonase, desen, kinder, shgraf, pikachu, dist1, subgeom, submatrix1, teroristi, parpal, bubblesort
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, 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, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor