imi cer scuze...postez acum si enunturile
Problema 1 (Urgenţa)
Autorităţile dintr-o zonă de munte intenţionează să stabilească un plan de urgenţă, pentru a reacţiona mai efici¬ent la frecventele calamităţi naturale din zonă. În acest scop au identificat N puncte de interes strategic şi le-au numerotat distinct de la 1 la N. Punctele de interes strategic sunt conectate prin M căi de acces având priorităţi în funcţie de importanţă. Între oricare două puncte de interes strategic există cel mult o cale de acces ce poate fi parcursă în ambele sensuri şi cel puţin un drum (format din una sau mai multe căi de acces) ce le conectează.
În cazul unei calamităţi unele căi de acces pot fi temporar întrerupte şi astfel între anumite puncte de interes nu mai există legătură. Ca urmare pot rezulta mai multe grupuri de puncte în aşa fel încât între oricare două puncte din acelaşi grup să existe măcar un drum şi între oricare două puncte din grupuri diferite să nu existe drum.
Autorităţile estimează gravitatea unei calamităţi ca fiind suma priorităţilor căilor de acces distruse de aceasta şi doresc să determine un scenariu de gravitate maximă, în care punctele de interes strategic să fie împărţite într-un număr de K grupuri.
Date de intrare
Fişierul de intrare URGENTA.IN are următorul format:
N M K
i1 j1 p1 – între punctele i1 şi j1 există o cale de acces de prioritate p1
i2 j2 p2 – între punctele i2 şi j2 există o cale de acces de prioritate p2
...
iM jM pM – între punctele iM şi jM există o cale de acces de prioritate pM
Date de ieÅŸire
Fişierul de ieşire URGENTA.OUT va avea următorul format:
gravmax – gravitatea maximă
C – numărul de căi de acces întrerupte de calamitate
k1 h1 – între punctele k1 şi h1 a fost întreruptă calea de acces
k2 h2 – între punctele k2 şi h2 a fost întreruptă calea de acces
...
kC hC – între punctele kC şi hC a fost întreruptă calea de acces
Restricţii şi precizări
0<N<256
N-2<M<32385
0<K<N+1
Priorităţile căilor de acces sunt întregi strict pozitivi mai mici decât 256.
Un grup de puncte poate conţine între 1 şi N puncte inclusiv.
Dacă există mai multe soluţii, programul va determina una singură.
Exemplu
URGENTA.IN URGENTA.OUT
7 11 4
1 2 1
1 3 2
1 7 3
2 4 3
3 4 2
3 5 1
3 6 1
3 7 5
4 5 5
5 6 4
6 7 3 27
8
1 3
1 7
2 4
3 4
3 7
4 5
5 6
6 7
Timp maxim de executare: 1 secundă / test
Problema 2 (Nunta)
În faţa palatului Prinţesei Mofturoase se află N peţitori aşezaţi la coadă, unul în spatele celuilalt. Fiecare poartă sub mantie un număr de pietre preţioase pe care doreşte să le ofere prinţesei ca dar de nuntă. Pentru a nu semăna vrajbă în rândurile lor, prinţesa a decis să-i determine ca N-1 dintre ei să renunţe în chip paşnic, peţitorul rămas devenind alesul prinţesei (indiferent de numărul de pietre preţioase deţinute de acesta).
Doi peţitori vecini la coadă se pot înţelege între ei astfel: cel care are mai puţine pietre preţioase pleacă de la coadă primind de la celălalt un număr de pietre astfel încât să plece acasă cu un număr dublu de pietre faţă de câte avea. Dacă doi peţitori au acelaşi număr de pietre, unul din ei (nu contează care) pleacă luând toate pietrele vecinului său.
Un peţitor se poate înţelege la un moment dat cu unul singur dintre cei doi vecini ai săi. După plecarea unui peţitor, toţi cei din spatele lui avansează.
De exemplu: pentru configuraţia alăturată de 5 peţitori, un şir posibil de negocieri care conduc la reducerea cozii la un singur peţitor este: se înţeleg vecinii 4 cu 5 şi pleacă 4, se înţeleg apoi 1 cu 2 şi pleacă 1, se înţeleg apoi 3 cu 2 şi pleacă 3, se înţeleg 2 cu 5 şi pleacă 5. Astfel peţitorul 2 câştigă mâna preafrumoasei prinţese, oferindu-i 0 pietre preţioase ca dar de nuntă.
Fie P numarul de pietre preţioase pe care le are peţitorul care va deveni alesul prinţesei. Se cer valorile distincte ale lui P la care se poate ajunge prin toate succesiunile de negocieri posibile.
Fişierul de intrare nunta.in conţine:
- pe prima linie numărul de peţitori: n (1  n  50).
- pe a doua linie, n numere naturale din intervalul [0, 20], reprezentând numărul de pietre preţioase pe care le deţin peţitorii, în ordinea în care stau la coadă.
Fişierul de ieşire nunta.out va conţine:
- pe prima linie numărul m de valori distincte ce pot fi obţinute
- pe a doua linie cele m valori ordonate crescător, reprezentând valorile care se pot obţine.
Exemplu:
nunta.in
4
1 4 2 6
nunta.out
3
1 3 5
Timp maxim de executare: 1 secundă / test
Imi cer scuze dar nu reusesc sa copiez si desenul de la problema nunta.
Afişează mesaje
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena
