|
ONI'97 Timisoara
ZIUA 1
PROBLEMA 2
DICTIONAR
Fisiere de intrare: DICTIO.TXT si INPUT.TXT
Fisier de iesire: OUTPUT.TXT
Un traducator (de exemplu, din engleza in romana) trebuie sa traduca o carte
de informatica cu foarte multi termeni de specialitate. In scopul realizarii
traducerii, el cumpara un dictionar de termeni tehnici.
Dictionarul contine doua coloane. Pe prima coloana sunt scrise cuvinte in
limba engleza, iar pe a doua traducerile acestora in limba romana.
Textul in limba engleza, dintr-o eroare, este scris fara spatii intre cuvinte,
doar cu litere mici, pe mai multe linii. Traducatorul citeste textul linie cu
linie si, pentru fiecare cuvant in limba engleza, scrie in textul tradus
cuvantul in limba romana.
Deoarece in informatica exista foarte multe cuvinte compuse care se traduc
altfel decat daca se traduc separat, traducatorul incearca (corespunzator
fiecarei linii), sa desparta caracterele in numar minim de cuvinte existente in
dictionar.
In cazul in care o asemenea separare de cuvinte, toate existente in dictionar,
nu este posibila, traducatorul va scrie in traducerea sa un singur caracter
corespunzator liniei respective: a?a. stiind ca o separare conform cerintei
este unica, traducatorul va scrie in textul tradus cuvintele in limba romana
in ordinea in care au fost cuvintele corespunzatoare in textul original.
DATE DE INTRARE:
Se dau doua fisiere de intrare:
1. Fisierul text DICTIO.TXT contine dictionarul. Pe fiecare linie a fisierului
este scris un cuvant in limba engleza, un spatiu, apoi cuvantul in limba romana.
In fisier pot fi cel mult 3.000 de linii. Lungimea maxima a cuvintelor din
dictionar este de 30 de litere.
2. Fisierul text INPUT.TXT contine textul care urmeaza sa fie tradus. Fisierul
are cel mult 100 de linii, iar pe fiecare linie pot exista maxim 100 de litere.
DATE DE IESIRE:
Fisierul text OUTPUT.TXT va contine o secventa de linii corespunzatoare linii
lor din fisierul de intrare. Fiecare linie poate sa contina fie caracterul a?a
(singur pe linie), fie unul sau mai multe cuvinte in limba romana, reprezentand
traducerea cuvintelor din limba engleza, dupa ce textul de pe linia respectiva
a fost separat in numar minim de cuvinte.
Exemplu:
DICTIO.TXT INPUT.TXT OUTPUT.TXT
alfa alfar delta deltar
be ber beta betar
beta betar sigmaalfakingdelta sigmar alfar kingr deltar
delta deltar tetaalfa ?
kilo kilor alfaalfa alfar alfar
king kingr
sigma sigmar
ta tar
Timp maxim de executare pentru un test: 1 minut.
ONI'97 Timisoara
ZIUA 1
Problema 1
POLITITI PE TEREN
Fisier de intrare: INPUT.TXT
Fisier de iesire: OUTPUT.TXT
Intr-un municipiu, noul sef al Politiei Circulatie incearca sa micsoreze
numarul de subalterni care stau fara sarcini concrete in birouri. In acest scop
doreste sa trimita pe teren cat mai multi politisti, pentru a supraveghea
anumite strazi ale orasului. El considera ca ii va controla mai usor daca va
repartiza fiecaruia acelasi tip de traseu. Prin traseu el intelege o secventa
de strazi, fiecare strada fiind identificata prin cele doua intersectii care o
delimiteaza.
La stabilirea traseului pentru fiecare politist in parte, se tine cont de
urmatoarele cerinte:
* din orice punct de intersectie al traseului politistul poate sa strabata
toate strazile acestuia, o singura data, intorcandu-se intotdeauna in punctul
de plecare;
* in final orice traseu repartizat unui politist trebuie sa aiba cel putin o
strada nesupravegheata de restul politistilor aflati in patrulare.
Determinati numarul maxim de politisti care pot fi trimisi pe teren si
traseele repartizate fiecaruia.
DATE DE INTRARE
Fisierul de intrare INPUT.TXT are urmatoarea structura:
* pe prima linie sunt scrise doua numere: n (n<=1500), reprezentand numarul
de intersectii din oras si m (m<=5000), reprezentand numarul strazilor;
* urmatoarele m linii contin perechi de doua numere, reprezentand
identificatorii intersectiilor la care este conectata fiecare strada.
DATE DE IESIRE
Fisierul de iesire OUTPUT.TXT are urmatoarea structura:
* pe prima linie se scrie numarul p care reprezinta numarul maxim de politisti
care pot fi trimisi pe teren;
* pe urmatoarele p linii se vor scrie traseele atribuite politistilor, pentru
fiecare traseu precizandu-se intersectiile aflate pe acestea; datele de pe
fiecare linie se vor desparti prin cate-un spatiu.
Observatie:
In cazul in care exista mai multe solutii, se va furniza una singura.
Exemplu:
INPUT.TXT OUTPUT.TXT
7 10 4
1 2 1 2 6 1
1 6 2 3 6 2
2 6 3 6 5 4 3
2 3 3 5 4 3
3 4
3 5
3 6
4 5
5 6
5 7
Timp maxim de executare pentru un test: 30 secunde
|
