
   Participantii la Olimpiada Internationala de Informatica pot trimite
rezolvarile celor 3 probleme pana in data de 13 decembrie.

---------------------------------------------------------------------------=
--

Motto:
 =09
Copilul rade:
"Intelepciunea si iubirea mea e jocul!"
Tanarul canta:
"Jocul si-ntelepciunea mea-i iubirea!"
Batranul tace:
"Iubirea si jocul meu e-ntelepciunea!"

=09=09=09Lucian Blaga.

Problema 1: Canalizari impotriva inundatiilor (30 puncte)

=09Comisia de Lupta Impotriva Calamitatilor Naturale a construit in judetul
Bihor o retea de canale ce leaga principalele rauri din acest judet. Numim
confluenta legatura in acelasi punct a cel putin doua ape (cel mult un rau =
si
cel putin un canal). Fiecare canal face o legatura unidirectionala intre do=
ua
confluente. Pentru fiecare rau exista o singura confluenta situata la punct=
ul
de intrare al raului in judet. Fiecare rau trece o singura data prin judetu=
l
Bihor. Sarcina dumneavoastra este de a dirija surplusul de apa de pe rauri =
cu
ajutorul canalelor si a asigura pe fiecare rau si pe fiecare canal un debit=
 cel
mult egal cu debitul de curgere maxim. Initial debitul de curgere pe canale=
 este
nul iar debitul maxim de curgere pe fiecare canal, debitul de curgere actua=
l pe
fiecare rau precum si debitul maxim de curgere pe fiecare rau sunt date.

Fisierul de intrare INPUT.TXT are urmatoarea structura :
n   m   c               - numarul de rauri, numarul de canale, numarul de  =
                               confluente
DMAX1   DA1             - debitul de curgere maxim si debitul actual la int=
rare
                          pentru raul numarul 1
=2E..
DMAXn   DAn             - debitul de curgere maxim si debitul actual la int=
rare
                          pentru raul numarul n
D1   CIN1  COUT1        - canalul numarul 1 intre confluenta CIN1 si conflu=
enta=20
                          COUT1 cu debitul maxim=20
=2E..
Dm   CINm  COUTm        - canalul numarul m intre confluenta CINm si conflu=
enta
                          COUTm cu debitul maxim Dm

Fisierul de iesire OUTPUT.TXT are urmatoarea structura :
DR1                     - debitul pe raul numarul 1
=2E..
DRn                     - debitul pe raul numarul n
DC1                     - debitul pe canalul 1
=2E..
DCm                     - debitul pe canalul m=09
Primele n confluente sunt confuentele situate la punctele de intrare in jud=
et
ale raurilor cu acelasi numar.  CINx si COUTx iau valori intre 1 si n pentr=
u=20
confluentele situate la punctele de intrare ale respectivelor rauri in jude=
t si=20
n+1 si c pentru celelalte confluente. Toate numerele sunt intregi. c poate =
fi maxim 100. In cazul in care nu exista solutie se va afisa infisierul de =
iesire pe o singura linie mesajul NO=20
Exemplu:
Pentru urmatorul fisier INPUT.TXT :
3  3  4
1000 100
1000 1100
500 1000
600  3  4
800  4  1
200  2  4
Un raspuns corect poate fi fisierul OUTPUT.TXT :
800
900
500
500
700
200
  Timp maxim de executie : 1 sec/test pe un calculator 486 DX2 / 66

=09=09=09=09=09=09=09Vlad Marius


Problema 2: Alegerea pietrelor (25 puncte)

"Alegerea pietrelor" este un joc in care doi jucatori extrag alternativ
pietre din doua gramezi. La fiecare miscare un jucator poate extrage
acelasi numar de pietre din ambele gramezi sau un numar oarecare de
pietre din una din gramezi. Castiga jucatorul care ia si ultima piatra.
Se cere sa testati daca, pentru o configuratie initiala data, primul
jucator are sau nu strategie de castig si daca da, sa afisati o mutare=20
a primului jucator astfel incat, dupa aceasta mutare, al doilea jucator
sa fie in situatie clara de pierdere (orice strategie ar adopta, al=20
doilea jucator nu poate castiga, in ipoteza ca primul jucator nu face=20
greseli).

Restrictii de intrare:
Numele fisierului de intrare se citeste de la tastatura.
Fisierul de intrare contine o singura linie de forma:
n m
unde n =3D numarul de pietre din prima gramada
     m =3D numarul de pietre din a doua gramada.

n, m sunt numere naturale mai mici decat 1.0E+18.
Pentru simplitate, presupunem n <=3D m.

Restrictii de iesire:
Numele fisierului de iesire se citeste de la tastatura.
Fisierul de iesire poate contine mesajul:
Jucatorul 1 este in situatie de pierdere.
sau
- pe prima linie mesajul:
Jucatorul 1 are strategie de castig.
- pe a doua linie:
x y
unde x reprezinta numarul de pietre extrase din prima gramada, iar y=20
numarul de pietre extrase din a doua gramada de primul jucator la o mutare=
=20
prin care al doilea jucator va fi plasat intr-o situatie de pierdere.
- pe a treia linie:
n1 m1
numarul de pietre ramase in prima gramada, respectiv numarul de pietre=20
ramase in cea de a doua gramada dupa mutarea primului jucator.

Timp de executie: 1 secunda per test (586/133MHz)

Exemplul 1:
Pentru fisierul de intrare:
1 2
Fisierul de iesire va fi:
Jucatorul 1 este in situatie de pierdere.

Exemplul 2:
Pentru fisierul de intrare:
5 6
Fisierul de iesire va fi:
Jucatorul 1 are strategie de castig.
0 3
5 3

=09=09=09=09=09=09prof. Emanuela Mateescu


Problema 3: Numere (20 puncte)

=09Fiind dat un numar natural n, n<=3D2.000.000.000, sa se
determine toate reprezentarile lui sub forma:
n =3D ((x+y)^2+3x+y)/2, unde x si y sunt numere naturale.
Intrare: fisierul "NR.IN" con=FEine numarul n pe o singura linie.
Iesire: fisierul "NR.OUT" are structura:
x1 y1
x2 y2
=2E..
xn yn
unde xn si yn sunt numere care satisfac conditia de mai sus.
Exemplu:
NR.IN
7
NR.OUT
1 2
Timp maxim de executie: 1 secunda/test pe un calculator 586/133 MHz.

=09=09=09=09=09=09prof. Maria & Adrian Nita



