OLIMPIADA DE INFORMATICĂ Clasele XI-XII
Etapa municipală – IAŞI, 22 ianuarie 2006
Problema 2 – Proiect 100 puncte
Călin are de realizat un proiect pentru ora de desen. El utilizează o planşă dreptunghiulară având dimensi-
unile laturilor notate L1 şi L2 şi defineşte cele 4 vârfuri ale planşei astfel: colţul stânga-jos (A), colţul dreapta-
jos (B), colţul dreapta-sus (C), colţul stânga-sus (D) , L1=|AB|, L2=|BC|. Pe planşă trebuie să deseneze un
număr maxim de dreptunghiuri cu laturi paralele cu laturile planşei de dimensiuni notate: lungime Lg şi lăţime
L (Lg<L1, L<L2; Lg, L sunt numere naturale nenule) cu proprietăţile următoare:
– dimensiunea lungimii unui dreptunghi este mai mică sau egală cu o valoare dată D;
– pentru primul dreptunghi, colţul stânga-jos coincide cu vârful A al planşei;
– pentru fiecare dreptunghi, exceptând primul, colţul stânga-jos coincide cu colţul dreapta-sus al dreptunghi-
ului desenat înaintea sa şi dimensiunile lungimii şi lăţimii sunt mai mari decât ale dreptunghiului desenat
înaintea sa;
– pentru ultimul dreptunghi, colţul dreapta-sus coincide cu vârful C al planşei;
– fiecare dreptunghi are laturi de dimensiuni distincte şi oricare două dreptunghiuri desenate au dimensiunile
tuturor laturilor distincte două câte două;
– desenul realizat trebuie să conţină cel puţin două dreptunghiuri, care să fie aşezate conform cerinţelor
anterioare.
Călin doreşte să obţină toate schiţele posibile de desenare a dreptunghiurilor pe planşă.
Cerinţă
Scrieţi un program care să determine numărul maxim de dreptunghiuri posibile, precum şi toate variantele
distincte de împărţire a planşei în număr maxim de dreptunghiuri.
Date de intrare
Fişierul de intrare [Link] va conţine pe prima linie trei numere naturale nenule separate prin câte un
spaţiu L1 L2 D, cu semnificaţia: L1, L2 sunt dimensiunile planşei de desenare, D este valoarea maximă a
lungimii unui dreptunghi.
Date de ieşire
Fişierul de ieşire [Link] va conţine pe prima linie două numere naturale max n, separate prin spaţiu,
unde max reprezintă numărul maxim de dreptunghiuri care se pot desena pe planşă, iar n numărul de schiţe
obţinute. Pe următoarele 2*n linii se vor scrie schiţele, câte 2 linii pentru o schiţă conform formatului următor:
[Link] Semnificaţia datelor din fişier
max n max reprezintă numărul maxim de dreptunghiuri, n reprezintă numărul de
Lg11 Lg12 … Lg1max schiţe obţinute
L11 L12 … L1max
… Lgi1 Lgi2 … Lgimax reprezintă dimensiuni pentru lungimile
Lgi1 Lgi2 … Lgimax dreptunghiurilor din schiţa cu numărul de ordine i
Li1 Li2 … Limax Li1 Li2 … Limax reprezintă dimensiuni pentru lăţimile dreptunghiurilor
… din schiţa cu numărul de ordine i (1 i n).
Lgn1 Lgn2 … Lgnmax
Ln1 Ln2 … Lnmax
Restricţii şi precizări
▪ 3 L1 45; 3 L2 45; 1 D 12
▪ Variantele de schiţe se afişează în fişierul de ieşire în ordinea lexicografică a lungimilor dreptunghiurilor
obţinute. Vectorul x =(x1, x2,…,xk) precedă în ordine lexicografică vectorul y=(y1 ,y2 ,…yk) x=y sau dacă
există i 1, astfel încât xp = yp, pentru orice p < i şi xi < yi .
▪ Pentru schiţe distincte, dimensiunile lungimilor dreptunghiurilor pot fi şi egale între ele şi se vor afişa, în
acest caz, în ordinea lexicografică a dimensiunilor lăţimilor dreptunghiurilor.
▪ Pentru orice date de test, exista întotdeauna soluţie.
▪ Se acorda 10 puncte/test (4 puncte – deteminare maxim, 2 puncte – determinare număr de schiţe, 4 puncte –
determinarea variantelor de schiţe).
OLIMPIADA DE INFORMATICĂ Clasele XI-XII
Etapa municipală – IAŞI, 22 ianuarie 2006
Exemple
[Link] [Link] Explicaţie
8 7 7 2 4 Dimensiunile pentru lungimile dreptunghiurilor
1 7 obţinute în variante distincte pot fi egale sau sunt în
2 5 ordine lexicografică:
1 7 1,7
3 4 1,7
2 6 2,6
3 4 3,5
3 5
1 6
[Link] [Link] Explicaţie
9 12 7 3 3 D C
1 2 6 D 5 L1=|AB|=9
3 4 5 L2=|BC|=12
1 3 5 2 6
2 4 6 4 Schiţa conţine trei
2 3 4 dreptunghiuri :(1,3),
1 5 6 1 (2,4), (6,5).
3
A B
Timp maxim de execuţie /test: 1 secundă