|
CLASA A XI-A
ZIUA 2,
PROBLEMA 1
TREPTE Punctaj: 50 puncte
In Estul Indepartat, pe varful unui munte, se va construi un templu.
Treptele care vor urca pana la acesta trebuie proiectate astfel incat
dimensiunile lor sa fie diferite, obligand pe cei care se vor urca pe ele sa
se apropie de zei cu capul plecat.
Proiectantul trebuie sa determine toate variantele in care aceste trepte
se pot construi astfel incat numarul lor sa fie cel mai mare posibil.
Fiecare treapta are o inaltime si o latime, iar proiectantului i se cere
ca oricare doua inaltimi si oricare doua latimi sa fie diferite, de asemenea
oricare inaltime trebuie sa difere de oricare latime. Nici o inaltime nu
poate fi mai mare decat o anumita valoare data.
Doua variante ale proiectului se considera "identice" daca in acestea
se regasesc aceleasi inaltimi (eventual in alta ordine) si aceleasi latimi
(eventual in alta ordine).
DATE DE INTRARE
In fisierul de intrare INPUT.TXT, pe primele doua linii este scris cate un
numar intreg I si L (2<I<50,2<L<50), reprezentand inaltimea totala,
respectiv latimea totala pe care se vor intinde treptele care trebuie
proiectate. Pe a treia linie a fisierului este scris un numar intreg
M (1<M<12), care este inaltimea cea mai mare posibila a unei trepte.
DATE DE IESIRE:
Rezultatul se va scrie in fisierul OUTPUT.TXT care va avea urmatoarea
structura:
- pe prima linie se va scrie numarul de trepte determinat N (cel mai mare
posibil, dar cel putin 2);
- pe urmatoarele linii se vor scrie variante care nu sunt "identice"
separate printr-o linie vida.
Pentru fiecare varianta se vor scrie doua linii:
- pe prima se vor scrie toate inaltimile (numere naturale) separate prin cate
un blanc;
- a doua linie va contine toate latimile (numere naturale) separate prin cate
un blanc;
Observatii:
- variantele proiectate pot fi scrise in orice ordine;
- in cadrul liniei care contine inaltimi, respectiv latimi, acestea pot fi
scrise in orice ordine;
- daca nu se poate determina nici un proiect care sa respecte cerintele puse,
in fisierul de iesire se va scrie mesajul: 'NU'
Exemplu:
INPUT.TXT OUTPUT.TXT
8 2
5 1 7
7 2 3
2 6
1 4
3 5
1 4
NOTA:
Timp de executare maxim pentru un test: 15 secunde.
CLASA a XI-A
ZIUA 2
PROBLEMA 2
PANZA DE PAIANJEN Punctaj: 50 puncte
Un paianjen isi tese panza ca in figura de mai jos:
(poza)
Nodurile acestei panze de paianjen vor fi plasate in directiile 0,1,2,...,n.
De asemenea, o astfel de panza are m niveluri concentrice de fire.
Odata cu trecerea timpului, unele fire se destrama, iar paianjenul nu mai
poate sa treaca pe acestea. Paianjenul "locuieste" in centrul panzei.
Cunoscand care sunt firele destramate, precum si pozitia unei muste prinse
in plasa, sa se determine cea mai scurta cale pe care trebuie sa o strabata
paianjenul (masurata in numar de fire) pentru a ajunge la musca.
DATE DE INTRARE
Fisierul de intrare de tip text INPUT.TXT va avea urmatoarea structura:
- pe prima linie sunt scrise doua numere: n, (n<100) si m, (m<100) avand
semnificatiile de mai sus;
- pe a doua linie sunt scrise doua numere separate printr-un spatiu,
reprezentand pozitia mustei (precizata prin numarul directiei si numarul
nivelului pe care se afla);
- urmatoarele linii descriu starea panzei: pe fiecare linie sunt descrise
doua noduri intre care panza este destramata; fiecare nod este precizat
printr-o pereche de numere: numarul de ordine al directiei si numarul de
ordine al nivelului.
DATE DE IESIRE
Fisierul text OUTPUT.TXT va contine:
- pe prima linie se va scrie un numar intreg, reprezentand lungimea drumului
parcurs de paianjen;
- pe urmatoarele linii se va afla descrierea nodurilor prin care trece
paianjenul pentru a ajunge la musca (un nod pe o linie). Fiecare nod se
precizeaza prin doua numere separate printr-un spatiu. Primul reprezinta
directia, al doilea reprezinta nivelul pe care se afla nodul.
Observatii:
- se considera ca paianjenul ramane agatat in panza, chiar si in cazul
limita in care aceasta se destrama in totalitate;
- daca nu exista solutie, in fisierul de iesire se va scrie: 'NU';
- daca exista mai multe solutii, atunci in fisierul de iesire se va scrie
doar una.
Exemplu:
INPUT.TXT OUTPUT.TXT
4 5 4
0 4 0 0
2 1 0 0 0 1
2 1 2 2 0 2
1 1 2 1 0 3
3 1 2 1 0 4
NOTA:
Timp maxim de executare pentru un test: 5 secunde
CLASA a XI-A
ZIUA 2,
PROBLEMA 3
PE LITORAL Punctaj: 50 puncte
Pe litoralul unei tari exista 2 plaje particulare numite A si B, intre
care se poate circula numai cu salupa. Exista un orar de functionare al
salupelor care contine ora de plecare si ora de sosire de pe o plaja pe
cealalta. Evident, orice turist care foloseste acest mijloc de transport
trebuie sa achite un bilet de calatorie care poate diferi de la voiaj la
voiaj.
Din pacate, proprietarii plajelor, au pretentia la o taxa de sedere pe
plaja lor, taxa care va fi incasata la anumite ore de la persoanele existente
la acea ora pe plaja respectiva. In cazul in care o persoana soseste pe o
plaja dupa momentul de incasare, nu plateste pana la momentul de incasare
imediat urmator. Aceste taxe pot fi de valori diferite in functie de ora
perceperii ei.
In cazul in care o salupa pleaca sau ajunge la un anumit moment pe o plaja
si exact in acel moment se percepe taxa de sedere pe acea plaja, atunci se
va plati si taxa de sedere.
Un tanar se afla pe plaja A la ora x, cunoscuta. El are intalnire cu
prietena lui pe plaja B, la o anumita ora y. El va incerca sa-si planifice
'stationarile' pe plaje si 'plimbarile' cu salupa astfel incat la ora y sa
fie la destinatie, platind efectiv taxe de sedere pe plaje si taxe de
transport cu salupa care insumate sa fie de valoare minima.
Determinati planul pe care el trebuie sa-l realizeze specificand si
costul acestuia.
DATE DE INTRARE
Fisierul text INPUT.TXT are urmatoarea structura:
- pe prima linie sunt scrise doua numere: oA (0<=oA<=23) si mA (0<=mA<=59)
reprezentand ora initiala si minutul la care tanarul se afla pe plaja A;
- pe a doua linie sunt scrise doua numere: oB (0<=oB<=23) si mB (0<=mB<=59)
reprezentand ora si minutul la care se vor intalni cei doi tineri pe plaja B;
- pe a treia linie sunt scrise doua numere ntA si ntB reprezentand numarul
de taxe percepute pe plaja A (0<=ntA<=100), respectiv numarul de taxe
percepute pe plaja B (0<=ntB<=100) intre momentul initial si momentul
intalnirii;
- pe urmatoarele ntA linii sunt scrise cate trei numere sub forma: h m c
unde h si m reprezinta ora si minutele perceperii taxei pe plaja A,
iar c reprezinta valoarea taxei (c<150);
- pe urmatoarele ntB linii sunt scrise cate trei numere sub forma: h m c
unde h si m reprezinta ora si minutele perceperii taxei pe plaja B,
iar c reprezinta valoarea taxei (c<150);
- urmatorea linie contine numarul natural ns<=80 reprezentand numarul total
de salupe care se deplaseaza intre cele doua plaje;
- pe urmatoarele ns linii este descris orarul salupelor folosind cate sase
numere scrise sub forma: d hA mA hB mB c unde:
- d poate lua doar valorile 0 si 1;
- daca d este 0, atunci :
- hA si mA reprezinta ora si minutele plecarii salupei din A
- hB si mB reprezinta ora si minutele sosirii in B;
- daca d este 1, atunci :
- hA si mA reprezinta ora si minutele sosirii salupei in A
- hB si mB reprezinta ora si minutele plecarii din B;
- c reprezinta costul biletului de calatorie (c<150).
Datele sunt despartite pe linii prin cate un spatiu.
Datele de intrare se considera corecte si admit intotdeauna solutie.
DATE DE IESIRE
Fisierul text OUTPUT.TXT va avea urmatoarea structura:
- pe prima linie se va scrie numarul ctm, reprezintand costul minim al
deplasarii (compus din toate taxele platite de tanar).
- pe linia urmatoare se vor scrie numerele de ordine ale salupelor cu care
a calatorit tanarul, in ordinea folosirii lor.
Datele vor fi despartite pe linii prin cate un spatiu.
Exemplu:
INPUT.TXT : OUTPUT.TXT
1 0 20
9 0 1 5 3
3 3
2 0 10
4 0 2
6 0 10
3 0 10
5 0 10
7 0 2
7
0 1 0 2 0 3
0 3 0 4 0 6
0 5 0 6 0 8
0 7 0 8 0 9
1 3 0 2 0 5
1 5 0 4 0 7
1 7 0 6 0 9
Interpretarea testului:
| Ora | Salupa | Plaja initiala | Plaja finala |
Taxa de sedere | Cost transport |
| 1h 0m-2h 0m | 1 | A | B | - | 3 |
| 2h 0m-3h 0m | 5 | B | A | - | 5 |
| 3h 0m-5h 0m | - | A | - | 2 | - |
| 5h 0m-6h 0m | 3 | A | B | - | 8 |
| 6h 0m-9h 0m | - | B | - | 2 | - |
| | | | | Total: 4 | Total: 16 |
NOTA
Timp de executare pentru fiecare test: 10 secunde
|
