Fişierul intrare/ieşire:perfect.in, perfect.outSursăLot 2006 Alba
AutorMarinel SerbanAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Perfect

Sa consideram secvente de grafuri neorientate de tipurile urmatoare:

  • Tipul A
    Secventa grafurilor de tip A se construieste in modul ce se poate deduce din exemplele urmatoare:
    A1A2A3A4A5

    Observati ca graful An are 2n varfuri.
  • Tipul B
    Secventa grafurilor de tip B se construieste dupa modelul urmator:
    B1B2B3B4
  • Tipul C
    Secventa grafurilor de tip C se construieste dupa modelul urmator:
    C1C2C3C4

Se numeste cuplaj perfect in graf o modalitate de a alege muchii ale grafului astfel incat oricare varf din graf sa fie incident cu exact o muchie aleasa. Doua cuplaje sunt distincte daca exista o muchie care apartine unui cuplaj, dar nu apartine celuilalt.

Cerinta

Dat fiind un graf de unul dintre tipurile din enunt, sa se determine numarul de cuplaje perfecte distincte ale grafului respectiv.

Date de intrare

Fisierul de intrare perfect.in contine o singura linie pe care se afla un caracter si un numar natural nenul n, separate printr-un spatiu. Caracterul poate fi A, B sau C si indica tipul grafului. Numarul natural n indica numarul de ordine al grafului in secventa de grafuri de tipul specificat de caracter.

Date de iesire

Fisierul de iesire perfect.out va contine o singura linie pe care va fi scris numarul de cuplaje perfecte ale grafului din fisierul de intrare.

Restrictii

  • 1 ≤ n ≤ 100

Exemplu

perfect.inperfect.out
A 4
5
B 2
4
C 2
8

Explicatie

Cele 5 cuplaje perfecte ale grafului A4 sunt:

Cele 4 cuplaje perfecte ale grafului B2 sunt:

Cele 8 cuplaje perfecte ale grafului C2 sunt:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content