|
ONI'97 Timisoara
Clasa a X-a
Ziua I
Problema 1
Beculete
Fie o retea ortogonala, ale carei linii sunt la distanta unitara, iar
nodurile ei in puncte de coordonate intregi; patratele retelei sunt colorate
initial in alb (culoarea de indice 0). In n noduri ale retelei (1<=n<=255)
se afla cate un beculet. Unind in linie dreapta printr-un fir doua beculete,
toate patratele traversate efectiv de fir (firul trece prin interiorul
patratului) isi schimba culoarea din i in i + 1 (nici Comisia nu stie de ce!).
Instalatia functioneaza daca si numai daca intre oricare doua becuri, exista
(direct sau indirect) legaturi.
Determinati o modalitate de conectare a celor n becuri, astfel incat
instalatia sa functioneze, iar coloratura retelei sa fie de indice minim. Prin
indicele unei coloraturi intelegem suma indicilor de culoare a tuturor
patratelor din retea.
Restrictii de intrare / iesire
Fisierul de intrare se numeste "input.txt" si contine pe prima linie
n, numarul de beculete, iar pe urmatoarele n linii cate doua numere intregi din
intervalul [-16000, 16000], care reprezinta coordonatele nodurilor retelei in
care sunt plasate cele n beculete.
Solutia va fi afisata in fisierul de iesire "output.txt" astfel:
* prima linie contine indicele coloraturii obtinute;
* a doua linie contine numarul k, de legaturi directe realizate;
* urmatoarele k linii contin fiecare coordonatele a doua beculete unite prin
fir direct, separate prin cate un spatiu.
Exemple
1. Pentru fisierul de intrare:
3
0 0
20 5
18 40
fisierul de iesire va fi:
56
2
0 0 20 5
20 5 18 40
2. Pentru fisierul de intrare:
5
0 0
2 10
1 5
5 7
10 0
fisierul de iesire va fi:
12
4
2 10 5 7
1 5 0 0
5 7 1 5
10 0 0 0
Timp de executie: maxim 5 secunde.
Punctaj: 50 puncte.
ONI'97 Timisoara
Clasa a X-a
Ziua I
Problema 2
Un om sarman are un seif1 pe care il poate deschide numai daca cele N
(1<=N<=100) ceasuri (fiecare cu un singur ac) conectate la sistemul de
securizare al seifului, indica ora 0.
Ceasurile sunt speciale, pe ecranele lor fiind marcate p pozitii (p numar
prim, 2<=p<=200). Pe seif exista M butoane (1<=M<=100); prin actionarea
oricarui buton sunt miscate simultan acele tuturor celor N ceasuri.
Initial acele celor N ceasuri sunt pe pozitiile P1, P2, ...., PN.
Prin apasarea butonului Bi (i = 1, 2, ..., M) acul ceasului Cj
(j = 1, 2, ..., N) avanseaza cu Dij pozitii in sens orar.
Sa se determine o modalitate de folosire a butoanelor astfel incat seiful sa
poata fi deschis; nu este obligatoriu sa fie folosite toate butoanele.
Restrictii de intrare / iesire:
Numele fisierului de intrare (care contine un singur set de date) este
'input.txt ' si are urmatorul format:
M N P
P1 P2 ..... PN
D11 D12 .... D1N
D21 D22 .... D2N
.....
DM1 DM2 ... DMN
Numele fisierului de iesire este output.txt si contine:
- daca seiful poate fi deschis:
- pe prima linie, M numere: A1,A2,... AN, unde
Ai indica de cate ori a fost apasat butonul Bi;
- pe urmatoarea linie, numarul total de apasari;
- in caz contrar, mesajul NU.
Exemple:
1.daca fisierul de intrare contine: fisierul de iesire va contine:
3 3 3 1 1 0
0 2 1 2
1 1 2
2 0 0
1 1 1
2.daca fisierul de intrare contine: fisierul de iesire va contine:
2 3 3 NU
0 2 1
1 1 2
1 1 1
Timp de executie: maxim 30 secunde
Punctaj 50 puncte.
1 gol, nud, adica nu are nimic in el
|
