Fişierul intrare/ieşire:shgraf.in, shgraf.outSursăLot Iasi 2008, Baraj 4
AutorAndrei GrigoreanAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Shgraf

Miruna a devenit de curând fascinată de grafuri. Mirunei i-au plăcut grafurile atât de tare, încât s-a decis să inventeze o nouă proprietate a lor. Astfel, ea consideră că un graf neorientat simplu are proprietatea de „SHGRAF” dacă şi numai dacă se respectă una dintre următoarele două cerinţe:

  • Este un graf conex în care numărul de noduri este egal cu numărul de muchii.
  • Nu este un graf conex, dar fiecare componentă conexă a sa are proprietatea de „SHGRAF”.

Prietena cea mai bună a Mirunei, A. Irina, este o fire foarte curioasă. Ea s-a gândit la două numere naturale N şi K, iar acum o întreabă pe Miruna câte grafuri etichetate cu N noduri şi cu proprietatea de „SHGRAF” există, astfel încât orice ciclu din graf are lungimea mai mare sau egală decât K.

Cerinţa

Ajutaţi-o pe Miruna să răspundă provocării A. Irinei, scriind un program care sa afişeze numărul căutat modulo 30011.

Date de intrare

Fişierul de intrare shgraf.in conţine pe prima linie două numere naturale N şi K, având semnificaţia din enunţ.

Date de ieşire

Fişierul de ieşire shgraf.out va conţine o singură linie pe care va fi afişat un număr întreg, reprezentând numărul total de grafuri etichetate cu N noduri, fără cicluri de lungime mai mică decât K şi care au proprietatea de „SHGRAF”, modulo 30011.

Restricţii

  • 3 ≤ N ≤ 250
  • 3 ≤ K ≤ N
  • Pentru 40% din teste 3 ≤ N ≤ 50

Exemplu

shgraf.inshgraf.out
3 3
1
50 10
20726

Explicaţie

  1. Singurul graf care respectă condiţiile impuse este ciclul elementar format din 3 noduri.
  2. Numărul de grafuri este prea mare pentru mai multe explicaţii, va trebui să ne credeţi pe cuvânt ;)
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content