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

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


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

O misiune a echipei SG1 constă în activarea unui dispozitiv extraterestru acţionat cu ajutorul unei tastaturi ciudate formate din n comutatoare aflate iniţial toate în aceeaşi poziţie (să o notăm cu 0). Se ştie că trebuie setate (trecute în poziţia 1) exact k comutatoare şi că nu contează ordinea în care trebuie acţionate comutatoarele. În plus, cu ajutorul unor documente antice, au aflat că între oricare două comutatoare succesive setate se pot afla cel puţin d1 şi cel mult d2 comutatoare nesetate. De exemplu, pentru n=7, k=3, d1=1 şi d2=2, o configuraţie care corespunde cerinţei este: 0100101, în timp ce configuraţiile 1010001, 1100100, 1010101 nu corespund datelor problemei.
Dacă o combinaţie de comutatoare setate nu activează dispozitivul, nu se întâmplă nimic deosebit (ce plictisitor episod!), ci comutatoarele se resetează automat, permiţând încercarea altei combinaţii.
Se cere să se determine numărul maxim de configuraţii distincte de comutatoare setate pe care trebuie să le încerce echipa SG1 pentru a activa dispozitivul.

Cerinţă

Scrieţi un program care, pentru valorile n, k, d1, d2 date, determină numărul total de configuraţii posibile de comutatoare ce respectă condiţiile din enunţ.

Date de intrare

În fişierul text sg1.in se dau, pe aceeaşi linie, despărţite prin spaţii, valorile n, k, d1, d2.

Date de ieşire

În fişierul sg1.out se scrie numărul de configuraţii ce corespund cerinţei.

Restricţii

0 < n < 101
0 < k ≤ n
0 ≤ d1 ≤ d2 < n

Exemple

sg1.insg1.outExplicaţii
7 3 1 2 8 Cele 8 configuraţii sunt:
1010100, 1010010,
1001010, 1001001,
0101010, 0101001,
0100101, 0010101
5 2 0 0 4 11000, 01100,
00110, 00011
14 8 1 5 0

autor: Prof. Rodica Pintea
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2006: borg, diamant, matrice1, petrom, ratina, vitale, acolor, cifru1, evo, part, trasee, bombo, cub2, prieteni2, fact, limbaj, panouri, pereti, sant1, zumzi, adun, sport1, baschet1, mere3, roboti, tzigla, morse, powerpuff
De acelaşi autor: fisc, cartonase2, cartoane, joc8, tramvai1, suma2, volei1, team, elfi, cezar1, piramida1, mosia, vanatoare, spirala1, poligon3, panglica, cerc, tablou1, radioactiv, solitar
Despre combinatorică: manevre, carti, bonuri, test, cub, nspecial, circuit, numere, cs, pluricex, parent, gray, siruri, anagrame, party, net, scaune, sir, monede, aztec, nrcuv2, perm, race, hanoig, red, grup, hperm, depou, grazing, pm, reteta2, playlist, young, pizza1, albine, caramele, teatru1, tub, robot1, sir23, soldati1, concurs1, comb, expresii, arbnr, cod1, munte, shgraf, desc, lex, munte1, maxperm, role, avere, vizibil, prime1, hexa, patrat, carti2, puncte2, pact, aranjari, numere5, borg, acolor, perfect, cifru2, bile4, pviz, culmi1, piramida1, trapez, frunze, sir7, logic, coduri, jetoane, kperms, tablite, secvpar, lego, permutari, binperm, multiplu1, operatii, fotbal, kbiti, jucarii, bradut, expozitie, parbit, kmax, petrecere, tango, rege, cd1, cifru3, kcons, bubblesort, hawaii, randomizare, kdist, reuniune, echipa, ghinion, cavaleri, camera616, covor, subm, grupuri, pavari, asfalt, adunscad, rotund, sport2, arbore1, lant1, module, nrperm, oneton, nrpomi, cover1, nrpal, probleme, optim, poly, vot1, sudoku1, flori2, xnumere, showroom, cntgcd, subsets, nkd, nrgraf, spion1, puteri, stiva1, permtr, relatii, 2sah, matcnt, magic7, nmult, roua
Despre numere mari: fib, 2sir, test, sort, gray, siruri, vecini, div, sir2, nrcuv2, scor, hanoig, red, matrice3, pavaj, depou, pm, sqr, set, albine, teatru1, descfib, tub, m01, soldati1, euclid, mutare, munte1, bifo, banda10, cutii, zumzi, numere7, trapez, patrate6, muguri, impozit, kbiti, m4, numar3, parbit, petrecere, randomizare, radical, ghinion, aliniere, sumb, cavaleri, camera616, numar4, pavari, asfalt, rotund, cos, risipa, xpn, dale, codpatrat, culori1, plus, minm, pomi, cifrab, subsets, doitrei, conjectura, ech, inventie
Despre recurenţă: nrbun2, nrbun, grupe, palind, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, expresii, agitatie, aparitii, apel, randuri, zidar, log, maxq, cover, dist, munte1, sir1, vizibil, csir, puncte2, aranjari, numere5, anticip, bsir, evantai, zumzi, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, sir9, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, 2ndesc, flori2, cntgcd, 2sah, matcnt, nmult
surse trimise | ajutor