#1497
Nunta
La o nuntă sunt invitate n
persoane, numerotate de la 1
la n
. Se știe că o parte din ele se cunosc două câte două, fie că sunt rude, fie de la serviciu, fie sunt prieteni sau vecini. Astfel se vor forma un număr K
minim de grupuri astfel încât în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut. Pentru fiecare grup de cel puțin două persoane se stabileşte un lider – persoana cu numărul de ordine minim. Aceste grupuri vor fi numerotate de la 1
la K
în ordinea crescătoare a numerelor de ordine ale liderilor. Ca sa se ivească cât mai puține situații stânjenitoare, organizatorul nunții ar dori să aranjeze o masă principală cu cel puţin n/2+1
invitaţi, la care să fie aşezate unul sau mai multe astfel de grupuri întregi numerotate cu valori consecutive.
Fiind date n
, numărul de persoane, m
, numărul de perechi de invitaţi care se cunosc între ei și cele m
perechi, să se determine numărul minim de grupuri formate din cel puțin doi invitați astfel încât, în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut, precum şi numărul variantelor distincte în care se poate organiza masa cu cel puţin n/2+1
invitaţi din grupurile formate.
Olimpiada locală de Informatică, Prahova, 2016
Problema | Nunta | Operații I/O |
nunta.in /nunta.out
|
---|---|---|---|
Limita timp | 0.1 secunde | Limita memorie |
Total: 2 MB
/
Stivă 1 MB
|
Id soluție | #39228808 | Utilizator | |
Fișier | nunta.cpp | Dimensiune | 1.01 KB |
Data încărcării | 02 Noiembrie 2022, 20:43 | Scor / rezultat | 60 puncte |
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
0 | 0 secunde | OK. | 10 | 10 | ||
1 | 0 secunde | OK. | 10 | 10 | ||
2 | 0 secunde | OK. | 10 | 10 | ||
3 | 0 secunde | Raspuns gresit. | 10 | 0 | ||
4 | 0 secunde | OK. | 10 | 10 | ||
5 | 0.008 secunde | Raspuns gresit. | 10 | 0 | ||
6 | 0.008 secunde | OK. | 10 | 10 | ||
7 | 0.004 secunde | Raspuns gresit. | 10 | 0 | ||
8 | 0.008 secunde | Raspuns gresit. | 10 | 0 | ||
9 | 0.008 secunde | OK. | 10 | 10 | ||
Punctaj total | 60 |
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Nunta face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.