PROBLEMA 3: Fractali (sau 'Cum a ajuns Cantor la sanatoriu')
DEADLINE: Luni, 15 februarie 1999
TIMP DE IMPLEMENTARE: 75, poate 90 minute
(Obs. Timpii de implementare sunt recomandati
chiar din momentul deschiderii acestui fisier)
PUNCTAJ: 50 dexteri
DOMENIU: Recurenta
Sa consideram patratul de latura 1 cu colturile in (0,0), (1,0), (1,1)
si (0,1). Impartim acest patrat in patru parti egale si numerotam
sferturile in ordinea indicata in figura 1:
(0,1) (1,1)
+-------+-------+
| | |
| 1 | 2 |
| | |
+-------+-------+ Figura 1.jpg (True Color)
| | |
| 3 | 4 |
| | |
+-------+-------+
(0,0) (1,0)
Acest procedeu se reia pentru fiecare din patratele obtinute; rezulta
16 patrate, fiecare avand atasat cate un cod format din doua cifre. De
exemplu, patratul cu codul 24 are colturile in (0.75, 0.5), (1, 0.5),
(1, 0.75) si (0.75, 0.75).
(0,1) (1,1)
+---+---+---+---+
|11 |12 |21 |22 |
+---+---+---+---+
|13 |14 |23 |24 |
+---+---+---+---+ Figura 2.jpg
|31 |32 |41 |42 |
+---+---+---+---+
|33 |34 |43 |44 |
+---+---+---+---+
(0,0) (1,0)
Conform aceluiasi procedeu fiecare patratel se reimparte, obtinand
patratele cu coduri formate din trei cifre s.a.m.d. Problema este ca,
indicandu-se doua patrate P1 si P2 prin codurile lor, sa spuneti daca
patratele sunt:
(a) Identice
(b) P1 inclus in P2, cu care nu are nici un punct de contact
(c) P2 inclus in P1, cu care nu are nici un punct de contact
(d) P1 inclus in P2, cu care are cel putin un punct comun
(e) P2 inclus in P1, cu care are cel putin un punct comun
(f) Exterioare unul altuia, cu cel putin doua puncte comune
(g) Exterioare unul altuia, cu un singur punct comun
(h) Complet disjuncte
OBSERVATIE: Codurile celor doua patrate pot avea lungimi diferite, cel
mult egale cu 10000.
OBSERVATIE LA OBSERVATIE: Un patratel cu lungimea codului de 10000 are
latura de 2^(-10000). Veti avea probleme mari cu underflow-ul pe
orice tip de date real, deci recomandarea este sa nu rezolvati
problema geometric.
EXEMPLE:
Perechi de tipul (a): 31 si 31
Perechi de tipul (b): 141 si 1
Perechi de tipul (c): 2 si 241
Perechi de tipul (d): 124 si 1
Perechi de tipul (e): 4 si 44
Perechi de tipul (f): 1 si 2
Perechi de tipul (g): 1 si 4
Perechi de tipul (h): 11 si 44
INTRAREA se face din fisierul PATRAT.IN, care contine doua linii,
fiecare terminata cu <Enter>. Pe fiecare linie se afla codul unui
patrat, format din cifre intre 1 si 4, NEdespartite prin nimic.
Codurile au intre 1 si 10000 cifre.
IESIREA: Pe ecran se va afisa o litera intre 'a' si 'h',
corespunzatoare situatiei in care se afla cele doua patrate. Comisia
s-a trezit binedispusa astazi si va permite sa afisati o litera mare
sau una mica, la alegere :)
EXEMPLU:
PATRAT.IN Raspuns:
1444444444 F
3222222
TIMP DE RULARE: Ca de obicei, o secunda.
COMPLEXITATE RECOMANDATA: O(L1+L2) unde L1 si L2 sunt lungimile
codurilor.
|
|
