Fişierul intrare/ieşire:gbc.in, gbc.outSursăSummer Challenge 2007, runda 2
AutorCosmin Silvestru NegruseriAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Gbc

Fie G = (V, E) un graf neorientat cu V multimea varfurilor, iar E multimea muchiilor. Vrem sa alegem doua multimi A,B ⊆ V astfel incat

  • |A| = n (A are n elemente)
  • |B| = m (B are m elemente)
  • A ⋂ B = Φ (A si B sunt disjuncte)
  • ∀ i ∈ A, j ∈ B, muchia (i j) ∈ E (exista muchie intre orice nod al lui A si orice nod al lui B)

Cerinta

Dandu-se G, un graf neorient conex, se cere sa se numere in cate moduri se pot alege cele doua multimi.

Date de intrare

Pe prima linie a fisierului de intrare gbc.in se afla trei numere intregi k - numarul de noduri ale grafului G, n si m - cu semnificatia din enunt. Urmatoarele k linii contin cate k numere 0 sau 1 cu semnficatia ca daca pe linia i+1, pe coloana j se afla 1 atunci avem muchie intre nodurile i si j.

Date de iesire

In fisierul de iesire gbc.out se va scrie pe prima linie numarul de moduri in care se pot alege cele doua multimi.

Restrictii

  • 1 ≤ n,m ≤ 8
  • 1 ≤ k ≤ 30
  • nu exista muchie de la un nod la el insusi

Exemplu

gbc.ingbc.out
4 2 2
0101
1010
0101
1010
2

Explicatie

  1. Multimea A={1,3}, B={2,4}
  2. Multimea A={2,4}, B={1,3}
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content