|
Olimpiada Nationala de Informatica
Timisoara, 23-30 martie 1997
CLASA a IX-a
ZIUA 1
PROBLEMA 1
Baze ascunse
Se dau n numere naturale, x1, x2, ..., xn
(fiecare numar are cel mult 9 cifre de la 0 la 9). Fiecare numar xi este
reprezentat intr-o baza bi (2<=bi<= 10), care nu este cunoscuta.
Sa se determine pentru fiecare numar xi o baza bi astfel
incat intervalul de valori, [a,b], in care sunt cuprinse toate cele n numere
sa fie de lungime minima. Prin lungimea unui interval se intelege diferenta
dintre capetele intervalului in valoare absoluta.
INTRARE:
Datele de intrare se vor citi din fisierul INPUT.TXT cu structura:
n -numarul de numere
x1 x2 ... xn - numerele (separate printr-un spatiu)
IESIRE:
Rezultatele vor fi scrise in fisierul OUTPUT.TXT cu structura:
x1 b1
x2 b2
...
xn bn
a b
Exemplu
Pentru fisierul de intrare INPUT.TXT
5
35 27 100 13 19
Iesirea in fisierul OUTPUT.TXT
35 6
27 8
100 4
13 10
19 10
13 23
NOTA
Datele de intrare se presupun corecte.
Olimpiada Nationala de Informatica
Timisoara, 23-30 martie 1997
CLASA a IX-a
ZIUA 1
PROBLEMA 2
Hong-Kong-ul la ONI'97
Firma "HAWOS" din Hong-Kong pune la dispozitia Comisiei Centrale n aparate
individuale de teleportare. Fiecare aparat are o capacitate de transport ci,
i=1,n (n<=1000). Cei p membri ai Comisiei Centrale, numerotati de la 1 la p,
au masele gj, j=1,p (p<=1000), distincte.
Sa se gaseasca o repartizare a membrilor Comisiei Centrale pe aparate astfel
incat capacitatea totala neutilizata sa fie minima.
INTRARE:
Datele de intrare se vor citi din fisierul INPUT.TXT cu structura:
n - numarul de aparate
c1 c2 ... cn - capacitatile de transport ale
aparatelor (separate printr-un spatiu)
p - numarul membrilor
g1 g2 ... gp - masele membrilor (separate printr-un spatiu)
IESIRE:
Rezultatele vor fi scrise in fisierul OUTPUT.TXT cu structura:
K -capacitatea totala neutilizata
c1 m1 gm1 unde ci sunt capacitatile celor n aparate,
c2 m2 gm2 mi numarul membrului repartizat pe aparatul
de capacitate ci,
... iar gmi masa membrului mI , separate printr-un spatiu.
cn mn gmn (daca un aparat nu este repartizat, mi=gmi=0)
Exemplu
Pentru fisierul de intrare INPUT.TXT
4
90 50 30 70
7
75 89 76 70 64 48 71
Iesirea în fisierul OUTPUT.TXT
90 2 89
50 6 48
30 0 0
70 4 70
NOTA
Datele de intrare se presupun corecte.
|