rugaminte

[•bacerandrei]

Ma poate ajuta cineva cu solutiile subiectelor de la 11-12 de la OJI 2002? Am downloadat ce era pe infoarena dar am constatat ca nu sunt si solutiile. Daca cineva stie unde le pot gasi sau daca le are, il rog sa mi le dea si mie. Multumesc anticipat!

[•sigrid]

Daca-mi amintesc bine la problema Urgenta am folosit un algoritm de impartire a arborelui in k componente conexe, eliminand pe rand primele k muchii cu prioritatile de acces cele mai mari.

Despre problema Nunta nu stiu ce sa-ti spun 

Solutiile oficiale nu le gasesc nicaieri.

[•Marius]

Dacă vorbim de aceeași problemă, atunci nuntă se rezolvă cu programare dinamică în O(N³).

dp[l][r][k] reține 1 dacă din secvența [l..r] s-a putut obține k și 0 altfel. Secvențele se calculează de la mici la mari: cele de lungime 1, de lungime doi 2, de lungime 3... etc

Dacă vb prostii îmi cer scuze.

[•Cosmin]

Cand pui o intrebare e bine o pui in asa fel incat efortul de a raspunde la ea sa fie minim. In cazul asta puteai sa pui si textele problemelor in intrebarea ta.

[•bacerandrei]

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.

[•Cosmin]

La problema Urgenta pare sa ai un arbore acolo. De fiecare data cand stergi o muchie din graf, spargi o componenta conexa in doua. Deci problema ta practic cere sa stergi k - 1 muchii de cost cat mai mare, pe care le poti gasi simplu sortand muchiile dupa prioritati. Asta a zis si Maria mai sus.

Solutia lui Marius pare buna pentru problema Nunta.

Sa intrebi daca ai neclaritati.

[•devilkind]

din cate am inteles eu nu e erbore :-"

[•wefgef]

Daca nu e arbore procedezi astfel:

In loc sa determeni muchiile ce vor fi distruse, le vei determina pe cele care raman. Graful determinat de ele va fi format din K componente conexe si va avea costul minim. De aici vine ideea adaptarii alogritmului lui Kruskal: Presupunem initial ca fiecare nod este intr-o componenta conexa separata si sortam muchiile crescator in functie de cost. Parcurgem lista sortata a muchiilor cat timp avem mai mult de K componente conexe. Daca intalnim o muchie care uneste noduri din componente diferite o inseram, altfel nu facem nimic. Muchiile ce vor fi distruse in avalansa sunt cele pe care nu le-ai inserat.

[•bacerandrei]

multumesc tuturor celor care mi-au dat sugestii...pana acum am reusit o implementare de 50 de puncte la problema urgenta cu ajutorul algoritmului lui prim...

[•nparfene2004]

Nu cred ca merge cu Prim, care adauga la o componenta conexa un nou nod.
Trebuie Kruskal.

[•FlowControl]

la aia cu nunta e o programare dinamica 3D