Lista de probleme 2

#2125 Piscina

Vasile este un tânăr programator angajat recent la o firma oarecare din domenul IT. Deoarece câştigă foarte bine el şi-a achiziţionat un teren de formă dreptunghiulară. Colţurile dreptunghiului care definesc acest teren au coordonatele (0,0), (N,M), unde N şi M sunt numere naturale.

Pe acest teren Vasile doreşte să construiască în primul rând o piscină de arie maximă, de formă dreptunghiulară, cu laturile respectiv paralele cu cele ale terenului.

Deşi credea că şi-a îndeplinit visul, Vasile şi-a dat seama că în viaţă nimic nu este atât de uşor deoarece au apărut două restricţii pe care el trebuie să le respecte:

  • Deoarece alimentarea cu apă se poate face doar în colţurile dreptunghiului care reprezintă terenul, piscina trebuie să aibă un punct comun cu unul dintre punctele (0,0),(0,M),(N,0) sau (N,M).
  • Pe teren se află P pomi la coordonate întregi cunoscute. Aceştia nu pot face parte din dreptunghiul ce defineşte piscina. Iar Vasile nici nu se gândeşte să taie vreun copac pentru că îi place aerul curat. Copacii se pot afla însă pe marginea piscinei.

Scrieţi un program care determină aria maximă pe care o poate avea piscina respectând restricţiile din enunţ.

Olimpiada Municipala Informatica Iasi 2015

Gigel vrea să confecţioneze un ornament pentru pomul de iarnă format din pătrăţele frumos colorate. Pătrăţelele pot arăta ca în desenul alăturat. Se observă faptul că ele pot avea 4 culori diferite pe cele 4 laturi, 3, 2 sau chiar o singură culoare pe toate cele 4 laturi ale pătrăţelului.

Gigel are la dispoziţie n (n pătrat perfect) pătrăţele egale de acest tip cu laturile colorate doar în patru culori (alb, roşu, galben, albastru). Le vom numerota simplu de la 1 la 4.

Să se scrie un program care primeşte o listă de n pătrăţele colorate şi determină o aranjare a lor sub forma de pătrat de forma k•k (k•k = n) astfel încât două laturi adiacente să aibă aceeaşi culoare, precum şi numărul de astfel de aranjări.

Olimpiada Municipala Informatica Iasi 2015