|
CLASA a-X-a
ZIUA I
Problema 1
Avenul SPEOTIM-97
Institutul de cercetari speologice din Romania a anuntat descoperirea
recenta in zona Muntilor Bihorului a unui sistem subteran de coridoare
(culoare orizontale) situate pe nivele diferite ce comunica intre ele prin
puturi (verticale). Fiecare culoar vertical se termina intr-un coridor
(culoar orizontal) care are doua capete (diferite de punctul unde ajunge
putul). La fiecare capat de coridor se poate intalni fie un alt put, fie o
fundatura.
Intre cele doua capete nu exista alte ramificatii.
Tinerii de la "SpeoTim" au pornit intr-o expeditie de cercetare si
cartare a pesterii. Pentru aceasta, ei realizeaza intai o schema a legaturilor
dintre culoare si apoi fac masuratorile necesare intocmirii hartii.
Cei doi speologi plecati sa puna in evidenta legaturile dintre culoare
procedeaza in felul urmator:
* Coboara prin culoarul vertical de la intrare pe care-l marcheaza (pe
perete) cu numarul 1.
* Ajunsi in primul culoar orizontal, ei isi marcheaza cu X un perete fata de
care se orienteaza si pornesc spre stanga. La capatul acestui culoar pot
intalni:
* un nou put, pe care-l marcheaza cu 2, il coboara si continua in acelasi
mod (spre stanga) investigarea sistemului de culoare accesibil prin
putul 2;
* o fundatura, unde se opresc si isi noteaza pe o hartie numarul ultimului
put pe care l-au coborat, se reintorc si continua investigarea culoarului
pe ramura din dreapta marcajului cu X.
* Cand au terminat de explorat ambele ramuri ale unui culoar, ei escaladeaza
putul de acces recuperand si coarda cu care echipasera putul la coborare si
continua explorarea culoarului superior pe ramura din dreapta marcajului X.
In concluzie ei exploreaza pestera coborand ori de cate ori se poate cobora
si virand tot timpul la stanga astfel incat sa nu treaca de doua ori prin
acelasi loc mergand in acelasi sens.
Observatii: Fiecare nou put coborat se marcheaza cu urmatorul numar
disponibil (nefolosit). Notatiile corespunzatoare fundaturilor respecta
ordinea cronologica a descoperirii lor.
La intoarcere ei fac unele observatii: ca nu se poate ajunge in nici un
coridor prin doua puturi diferite, ca doua coridoare diferite nu pot comunica
decat printr-un culoar vertical si ca nu exista put care leaga mai mult de
doua culoare.
Vi se cere sa reconstituiti schema legaturilor subterane cu ajutorul
insemnarilor celor doi.
Fisierul "pestera.in" contine :
* pe prima linie o valoare n reprezentand numarul de fundaturi intalnite de
cei doi (n<=200);
* pe linia urmatoare cele n numere notate de speologi pe hartie despartite
intre ele prin cate un spatiu.
Schema legaturilor pe care o veti reconstitui contine numerele de ordine ale
puturilor, pentru fiecare put precizandu-se intai numarul putului din stanga
coridorului unde ajunge acesta sau caracterul '*' daca in stanga este o
fundatura si apoi numarul putului din dreapta coridorului unde ajunge acesta
sau caracterul '*' daca in dreapta este o fundatura. Schema legaturilor
(realizata ca in exemplu, folosind caracterele cu codurile 195,192,179) va fi
scrisa in fisierul text "pestera.out". Daca fisierul contine niste
numere ce nu pot fi rezultatul cercetarii pesterii, fisierul de iesire va
contine mesajul "IMPOSIBIL".
Exemple: pentru datele de intrare:
6
2 4 4 5 5 5
fisierul de iesire va contine o schema de forma (numai desenul din
stanga!):
pentru datele de intrare
5
1 2 1 3 4
fisierul de iesire va contine mesajul:
IMPOSIBIL
O.N.I. Timsoara
Clasa a X-a
Ziua 1
Problema 2 Punctaj: 50p
"ALIANTE POLITICE"
Spunem ca un partid x simpatizeaza un alt partid y daca in programul politic
al partidului y se regasesc idei ale programului partidului x.
Numim coalitie de partide politice o grupare de doua sau mai multe partide
in care orice doua partide se simpatizeaza reciproc.
Fiind date n partide (n<=20) sa se determine coalitia cu cel mai mare
numar de partide politice. Daca sunt mai multe cu acest numar maxim, atunci
se afiseaza toate .
Datele de intrare se introduc printr-un fisier cu numele FIS.INT. El are
urmatoarea structura :
* prima linie contine numarul n de partide
* urmatoarele n linii dau informatii despre simpatiile fiecarui partid prin
valorile 0 si 1 care au urmatoarea semnificatie
* linia i contine 1 pe pozitiile j corespunzatoare partidelor pe care
partidul i le simpatizeaza si contine 0 pe pozitiile corespunzatoare
partidelor pe care partidul i nu le simpatizeaza
Rezultatul prelucrarii se va afisa intr-un fisier text cu numele FIS.OUT si
cu urmatoarea structura :
* fiecare coalitie se trece pe o linie in care elementele sunt separate prin
cate un spatiu
* coalitiile sunt separate intre ele prin cate o linie libera
Exemplu
La intrarea :
6
0 1 0 1 0 1
1 0 1 1 0 1
0 1 0 1 0 0
1 1 0 0 1 1
0 1 0 1 0 0
1 1 0 1 1 0
corespunde iesirea :
1 2 4 6
Timp de rulare : 1 minut/ test.
Timp de lucru pentru ambele probleme 3 ore
Punctaj: 100 (50+50)
|
