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

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


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

Să considerăm secvenţe de grafuri neorientate de tipurile următoare:
Tipul A
Secvenţa grafurilor de tip A se construieşte în modul ce se poate deduce din exemplele următoare:



Observaţi că graful An are 2n vârfuri.
Tipul B
Secvenţa grafurilor de tip B se construieşte după modelul următor:



Tipul C
Secvenţa grafurilor de tip C se construieşte după modelul următor:



Se numeşte cuplaj perfect în graf o modalitate de a alege muchii ale grafului astfel încât oricare vârf din graf să fie incident cu exact o muchie aleasă. Două cuplaje sunt distincte dacă există o muchie care aparţine unui cuplaj, dar nu aparţine celuilalt.

Cerinţă

Dat fiind un graf de unul dintre tipurile din enunţ, să se determine numărul de cuplaje perfecte distincte ale grafului respectiv.

Date de intrare

Fişierul de intrare perfect.in conţine o singură linie pe care se află un caracter şi un număr natural nenul n, separate printr-un spaţiu. Caracterul poate fi A, B sau C şi indică tipul grafului. Numărul natural n indică numărul de ordine al grafului în secvenţa de grafuri de tipul specificat de caracter.

Date de ieşire

Fişierul de ieşire perfect.out va conţine o singură linie pe care va fi scris numărul de cuplaje perfecte ale grafului din fişierul de intrare.

Restricţii

1 ≤ n ≤ 100

Exemple

perfect.inperfect.outExplicaţii
A 4 5 Cele 5 cuplaje perfecte ale grafului A4 sunt:


B 2 4 Cele 4 cuplaje perfecte ale grafului B2 sunt:


C 2 8 Cele 8 cuplaje perfecte ale grafului C2 sunt:



autor: Prof. Marinel Şerban
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot AB 2006: bcolor, peg, poze, import, oypara, ab3, camion1, soc
De acelaşi autor: premii, finala, fractii, trei, manevre, nrcuv, an, vopsea, opmat, tramvai, bipal, kpal, sarpe, replace, factori, barca, perechi, grupe, cod, reactii, factura, decript, trenuri, holo, cifre, firma, tribile, mesaj, tricouri, pajura, monede, programs, fry, repeat, red, pavaj, bacan, nrbinar, invest, cutie2, loc, depou, nr3, zid, felinare, sir3, sqr, carte, labirint, stea, count, evaluare, super, schimb, zaruri, vectori, spirala, desen1, rima, ceas1, romane, sms, bac, excursia, joc7, furnici, munte1, cezar, marcare, excursie1, culmi, sume1, schi, nr4, fractie, cod3, medii, tren3, top, sant1, imagine, ocr, pluton, reforma, alee, ceas2, paritate, borcane, aranjare, comoara1, culmi1, reactivi, submult, sablon1, sir8, sume2, dansatori, smith, tom, matriosca, asociativ, control1, calorii, immortal, concat, mat, cubinvers, mine, divizori, cheie, stelar, joct, minmax, cladire, adunscad, razboi, ore, oras1, sumprod, prisme, operatii1, lgdrum, unupatru, chibrituri, extraprime, prieten, rebus1, grindina, opmult, betisoare, antitero, clase, pagini, ornament, ordine, spioni1
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, sg1, 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 Inducţie matematică: 2sir, h, gray, poligon, patrate1, set, descfib, suma1, mutare, sir1, prieteni1, excursie1, galax, prieteni2, peg, borcane, regine, comoara2, domino, arctir, partitie, acoperire1, xpn
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, sg1, zumzi, lant, 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