Count

count

==Include(page="template/taskheader" task_id="count")==

== include(page="template/taskheader" task_id="count") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| count.in | count.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="count") ==

==Include(page="template/raw")==
 
Link: [1]File-List
 
count
 
Fiind dat un graf planar cu N noduri si M muchii aflati numarul maxim de noduri pe care il poate avea un subgraf complet al sau (un graf neorientat se numeste complet daca exista muchie intre oricare doua noduri ale sale). De asemenea se cere si numarul de subgrafuri complete cu numar maxim de noduri care se gasesc in graful planar dat.
 
h2. Cerinta
 
Fiind dat un graf planar aflati cele doua numere cautate.
 
h2. Date de Intrare
 
Linia 1 a fisierului de intrare contine doua numere naturale separate prin spatii N si M (numarul de noduri, respectiv numarul de muchii ale grafului planar).
 
Liniile 2 .. M + 1 contin cate doua numere A si B cu semnificatia: exista o muchie bidirectionala intre nodurile A si B (nodurile grafului sunt numerotate de la 1 la N).
 
h2. Date de Iesire
 
Fisierul de iesire va contine pe prima linie doua numere X si Y reprezentand numarul maxim de noduri pe care il poate avea un subgraf complet si, respectiv, numarul de subgrafuri complete cu X noduri din graful planar dat.
 
h2. Restrictii si precizari
 
o 2 <= N <= 30 000
o 1 <= M <= 60 000
o Y <= 2^30
o Pentru 70% din teste N <= 2000
 
h2. Exemplu
 
 
|count.in |count.out |Explicatii |
 
|5 8 |3 4 |Se pot forma 4 subgrafuri complete cu 3 noduri. Acestea sunt:|
|1 2 | | |
| | |(1 2 5), (2 4 5), (3 4 5), (1 3 5) |
|1 3 | | |
| | | |
|1 5 | | |
|2 4 | | |
| | | |
|2 5 | | |
| | | |
|3 4 | | |
| | | |
|3 5 | | |
| | | |
|4 5 | | |
 
 
 
 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/count/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="count")==