
Problema A (Decupari)
Concurs regional ACM, Europa Centrala, oct. 1996
Dificultate: C2-C3

Intr-o fabrica exista o masina care taie bucati din tabla. Ea are un cutit
extraordinar de ascutit capabil sa taie segmente drepte orizontale si verticale.
Fiecare proces de taiere consta dintr-o secventa de astfel de taieturi. Fiecare
segment taiat este dat rpin coordonatele capetelor sale care sunt totdeauna
in interiorul foliei de tabla. In timpul procesului de taiere unele parti din
tabla sunt decupate si apar astfel gauri.
De rearcat ca o taietura simpla in tabla nu este considerata gaura.
   Serviciul de proiectare-productie vrea sa stie numarul de gauri obtinute la
sfarsitul procesului de taiere. Scrieti un program care raspunde acestei
cerinte.
Iata cateva situatii care pot apare dupa taiere:

		-----    ----               -----
                |   |    |  |  ----     ----|---|----     ------
            ---------    | -|--|- |     |   |   |   |     |   --|--
            |   |        |  |  ----     ----|---|----     ----|--  |
            -----        ----               |   |             |    |
                                            -----             ------
           2 gauri       2 gauri           o gaura         o gaura

Intrare:
Fisierul de intrare (cutter.in) consta din blocuri de linii. Fiecare bloc 
(inafara de ultimul) descrie un proces de taiere. Pe prima linie a blocului 
exista un singur numar N<=100 care indica numarul de segmente taiate. Aceste 
taieturi sunt definite pe urmatoarele N linii. 
Linia care defineste o taietura are forma
x1 y1 x2 y2
unde (x1,y1),(x2,y2) cunt coordonatele capetelor segmentului taietura. Intre
cele patru nuemre se afla cel putin cate un spatiu. Coordonatel sunt numere
intregi si definesc un segment orizontal sau vertical (adica paralel cu una din
axele de coordonate). Ultimul bloc este format dintr-o singura linie care contine
un 0.
Iesire:
Fisierul de iesire (cutter.out) contine cate o linie corespunzatoare fiecarui
bloc din fisierul de intrare. O astfel de linie are un numar intreg care
reprezinta numarul de gauri care raman in tabla cupa executarea taieturilor
date la intrare. Nu exista raspuns la ultimul bloc din fisierul de intrare
(care contine numai numarul 0).
Exemplu:
Pentru intrarea
4
0 1 1 1
1 1 1 0
1 0 0 0
0 0 0 1
2
0 1 2 1
1 2 1 0
0
iesirea este:
1
0
====================

Problema B (Morse modificat)
Faza finala ACM, San Jose, California, 1 martie 1997
Dificultate: D1

       Samuel F.B. Morse este foarte cunoscut pentru schema de codificare care 
i poarta numele. Codul Morse este foarte simplu. Fiecare litera (mare sau mica) 
este translatata ntr-o secventa predefinita de linii si puncte (notate - 
respectiv .). Fiecare astfel de element este transmis printr-un semnal care are 
o anumita durata. Un punct este un semnal scurt, iar o linie - un semnal de trei 
ori mai lung ca durata. Intre elemente apare un scurt moment de pauza, ntre
litere pauza este ceva mai lunga, iar ntre cuvinte marimea este crescuta. 
Aceasta dependenta ntre spatiu si timp are drept efect faptul ca uneori 
operatorii Morse nu transmit n mod perfect codurile, ceea ce creaza dificultati 
la receptie; mesajul este nsa decodificat corect pe baza contextului.
     In aceasta problema vom considera receptia cuvintelor n semnale Morse, 
fara spatii ntre litere. In aceasta situatie, este posibil sa se codifice 
identic mesaje diferite. De exemplu, mesajul "..." poate fi interpretat "EEE',
"EI","IE","S" (folosind tabelul de codficare dat n exemplu). Selectia 
interpretarii corecte se face pe baza contextului si a supozitiei ca orice
cuvnt primit apare ntr-un dictionar.
    In aceasta problema programul va citi o tabela cu codificarea literelor si 
cifrelor in semnale Morse, o lista a cuvintelor posibile (context) si o secventa 
de cuvinte codifcate n Morse (morse). Aceste cuvinte pot fi gresite. Pentru 
fiecare cuvnt morse, programul trebuie sa determine - daca exista - cuvntul 
corespunzator din context. Daca n context sunt mai multe cuvinte care se 
potrivesc cu morse, au daca nici un cuvnt nu se potriveste perfect, programul 
va scrie cuvntul care se potriveste cel mai bine si un indicator de modificare.
    Daca un cuvnt unic din context se potriveste perfect cu morse, el va fi 
scris pe o singura linie. Daca mai multe cuvinte din context se potrivesc 
perfect cu morse se selecteaza cuvntul cu cele mai putine caractere; daca 
ambiguitatea persista, oricare din cuvinte poate fi scris ca cel corect. Daca 
sunt posibile mai multe solutii, cuvntul ales ca rezultat este scris cu un semn 
de exclamare dupa el.
    Se considera un singur caz de eroare n transmisie, cnd elementele pot fi 
sau trunchiate sau adaugate la sfrsitul unui cuvnt morse. Cnd nu se gaseste o 
potrivire perfecta pentru morse, se scrie cuvntul din context care se potriveste 
cu cel mai lung prefix al lui morse sau are cele mai putine extra-elemente dupa 
acelea din morse. Daca n aceasta situatie sunt mai multe cuvinte din context, 
oricare din ele poate fi scris ca solutie. Cuvintele care nu coicid perfect sunt 
scrise cu semnul ntrebarii dupa ele.
Datele de intrare vor trata numai cazuri de aceste tipuri.
Intrare:
     Tabela codurilor Morse apare prima si consta din linii; fiecare linie 
contine o litera mare sau o cifra C, zero sau mai multe spatii, si o secventa de 
maxim sase linii si puncte care dau codul Morse pentru C. O linie care contine 
un asterisc, posibil precedat sau urmat de spatii, ncheie tabela codurilor 
Morse. Se presupune ca tabela contine codul Morse pentru orice caracter care 
apare n sectiunea context.
     Urmatoarea sectiune este context, cu cte un cuvnt per linie, posibil 
precedat sau urmat de blancuri. Fiecare cuvnt din context are maxim zece 
caractere; singurele caractere permise sunt literele mari si cifrele. Sunt maxim 
100 cuvinte n context. Sfrsitul tabelei este marcat de o linie cu un asterisc, 
posibil precedat sau urmat de blancuri.
     Restul fisierului de intrare contine cuvintele morse separate prin spatii 
sau caractere end-of-line. Sfrsitul fisierului este marcat de o linie cu un 
asterisc, posibil precedat sau urmat de blancuri. Nici un cuvnt morse nu are 
mai mult de 80 caractere.
Iesire:
     Pentru fiecare cuvnt de intrare morse se scrie cel mai potrivit cuvnt din 
context, urmat eventual de ! sau ?. Fiecare cuvnt se scrie pe o linie, de pe 
prima coloana.
Exemplu:
Intrare                            Iesire
A         .-                       WHAT
B         -...                     HATH
C         -.-.                     GOD
D         -..                      WROTH?
E         .                        WHAT
F         ..-.                     AN
G         --.                      EARTHQUAKE
H         ....                     IM!
I         ..                       READY
J         .---                     TO
K         -.-                      IM!
L         .-..
M         --
N         -.
O         ---
P         .--.
Q         --.-
R         .-.
S         ...
T         -
U         ..-
V         ...-
W         .--
X         -..-
Y         -.--
Z         --..
0         ------
1         .-----
2         ..---
3         ...--
4         ....-
5         .....
6         -....
7         --...
8         ---..
9         ----.
*
AN
EARTHQUAKE
EAT
GOD
HATH
IM
READY
TO
WHAT
WROTH
*
.--.....--   .....--....
--.----..  .--.-.----..
.--.....--   .--.
.-.-.-....--.-..-.--.-.
.--    .-...--..-.--
----           ..--
*
