|
Inchisori Punctaj 50
In urma grevelor ce au avut loc in inchisori s-a hotarat 'de sus' sa se ia
masuri de intarire a pazei celulelor.
Datorita austeritatii bugetului inchisorii, si necesitatii reducerilor de
personal este posibil ca un gardian sa supravegheze mai multe celule cu
conditia ca acestea sa fie in raza lui vizuala. Cerinta conducerii este sa se
foloseasca un numar minim de gardieni, plasati in posturile din fata celulelor.
In proiectul elaborat de un detinut informatician care sparsese o banca prin
Internet, inchisorii i se asociaza un graf cu n noduri (celule) in care muchia
(i,j) reprezinta faptul ca intre celulele i,j exista vizibilitate. Datele de
intrare aflate in fisierul in.txt sunt reprezentate sub forma: pe prima linie,
numarul de celule n (n<=50).
Pe urmatoarele n linii sunt componenetele matricei de adiacenta separate
printr-un spatiu, fiecare linie terminandu-se cu <enter>.
Datele de iesire se vor gasi in fisierul out.txt si vor reprezenta solutiile
sub forma unor linii dispuse astfel: pe prima se afla numarul gardienilor,
iar pe urmatoarele, pe cate o linie numerele de ordine ale celulelor unde
sunt plasati, despartite prin spatiu (o linie pentru fiecare solutie gasita)
Exemplu:
Date de intrare :
9
1 1 1 1 1 1 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 1 1 1
1 0 0 1 1 1 0 0 0
1 0 0 1 1 1 0 0 0
1 0 0 1 1 1 0 0 0
0 0 1 0 0 0 1 1 1
0 0 1 0 0 0 1 1 1
0 0 1 0 0 0 1 1 1
Solutiile sunt:
2
1 7
1 8
1 9
3 6
3 4
3 5
1 3
Observatii:
Datele de intrare sunt corecte.
Vinuri Punctaj 50
La un depozit specializat din Recas sosesc, pe rand, n clienti care solicita
fiecare o cantitate data de Cabernet. In butoiul din magazinul de deservire
(considerat de capacitate nelimitata) nu se gaseste initial nici o picatura de
vin. Dan Septica, administratorul depozitului, are un algoritm propriu de
deservire a clientilor: in functie de ceea ce are in butoi, dar si de
inspiratia de moment, el poate sa raspunda:
- Va ofer intreaga cantitate cu cea mai mare placere !
sau
- Nu va pot oferi acum ceea ce doriti, mai reveniti cu solicitarea altadata!
Pe clientul servit il elibereaza de grija banilor corespunzatori costului
licorii cumparate, iar pe cel refuzat il saluta politicos si are grija ca,
imediat ce a plecat clientul, sa coboare si sa aduca in butoiul din magazin
exact cantitatea solicitata de clientul respectiv (cel ce nu a fost servit).
Clientii sunt restaurante de lux si nu cumpara mai mult de 1 hectolitru.
Cunoscind cele n cantitati cerute de clienti, sa se determine un mod de a
raspunde solicitarilor astfel incat, in final, cantitatea de vin vanduta sa
fie maxima.
Din fisierul de intrare CERERI.IN se citesc:
- de pe prima linie, n - numarul de clienti (n<=600);
- de pe a doua linie n numere naturale, separate prin spatiu, reprezentand
cantitatile (in litri) cerute de clienti, in ordinea sosirii lor.
Programul trebuie sa scrie in fisierul de iesire VANZARI.OUT cantitatea
vanduta (tot in litri).
Exemplu:
CERERI.IN:
4
5 3 4 2
VANZARI.OUT
6
Interpretare:
Actiunile lui Septica sunt: refuza primul client si pune 5 litri in butoi,
il refuza pe al doilea si mai pune inca 3 litri in butoi, iar pe urmatorii
doi clienti ii serveste, realizand o vanzare de 6 litri.
NOTA:
Timp de executie maxim 1 minut/test. (pentru fiecare problema)
Timp de lucru la ambele probleme 3 ore .
|
