| CLASA a XII-a |
| Problema
1: |
| LINII
Navale |
De o parte si de alta a
unui fluviu se afla cate N orase (1<=N<=10000),
fiecare oras de pe un mal fiind legat printr-o linie
navala de un singur oras de pe malul opus. Sa se
determine numarul maxim de linii navale pe pot fi
pastrate astfel incat oricare doua sa nu se intersecteze.
Orasele, atat de pe un mal si de pe celalalt, sunt
numerotate de la 1 la N, crescator in sensul de curgere a
apei. |
| Observatie: nu pot fi
stabilite alte linii navale decat cele existente |
| Fisierul de intrare: |
- prima linie contine numarul N de
orase |
| - fiecare din urmatoarele N linii
contine o pereche de numere (X,Y), 1<=X,Y<=N cu
urmatoarea semnificatie: orasul numarul X de pe malul
stang este legat printr-o linie navala de orasul Y de pe
malul opus. |
| Numele fisierului de intrare (cu
extensia .in) se citeste de la tastatura. |
| Exemplu: Pentru fisierul de
intrare NUME.in:
| 7 |
| 2 3 |
| 1 1 |
| 3 5 |
| 6 4 |
| 5 7 |
| 7 6 |
| 4 2 |
| |
| Rezultatul afisat pe ecran este: 4 |
| |
 |
|
| |
Observatie: la aceasta
problema se poate aplica |
Branch and Bound |
| Greedy |
| Problema
2: |
| Joc |
Un joc se compune din m
cilindri de aceeasi raza si inaltime, montati pe o axa
orizontala care trece prin axa de simetrie a fiecarui
cilindru. Pe fetele laterale ale fiecarui cilindru sunt
montate n bile de diverse culori, culorile fiind
codificate prin numere de la 1 la k. Scopul jocului este
de a roti cilindrii, astfel incat sa obtinem cel putin o
generatoare pe care se gasesc bile de aceeasi culoare. In
fisierul 'NUME.in' pe prima linie se dau m, n si k
separate prin spatii, iar pe urmatoarele m linii se
gasesc culorile bilelor din cate un cilindru. Dati o
configuratie finala a jocului, astfel incat numarul de
generatoare completate cu bile de aceeasi culoare sa fie
maxim (nu este nevoie ca toate generatoarele sa fie de
aceeasi culoare). In fisierul 'NUME.out' dati pe cate o
linie culorile din fiecare cilindru, pornind de la o
anumita generatoare. NUMEle fisierului se citeste de la
tastatura. |
| De exemplu: |
Fisireul de intrare 'bile.in'
contine
| 3 |
4 |
15 |
|
| 3 |
2 |
4 |
1 |
| 2 |
6 |
1 |
5 |
| 3 |
1 |
5 |
2 |
|
| Fisierul de iesire 'bile.out'
contine |
| |
Observatie: aceasta
problema este o problema tipica Backtracking |
| |