Fişierul intrare/ieşire:fractal.in, fractal.outSursăONI 2018 baraj gimnaziu
AutorCerasela-Daniela CardasAdăugată defrancuCristian Francu francu
Timp execuţie pe test1.5 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Fractal (baraj gimnaziu)

Andra este o fetiţă pasionată de desen. Pentru a-şi îmbunătăţi performanţele şcolare la geometrie, Andra îmbină pasiunea pentru desen cu rezolvarea problemelor de geometrie. Astfel, pe o foaie de matematică împărţită în pătrăţele dispuse pe 2N linii şi 2N coloane, Andra desenează în centru o figură de forma unui pătrat de latură 2N-1 (figura 1) . Pentru fiecare colţ al figurii, Andra desenează alte 4 noi figuri cu latura egală cu jumătate din latura figurii iniţiale (Figura 2). Repetă procedeul de desenare pentru fiecare nouă figură obţinută, până când ajunge la marginea foii de hârtie, fără a depăşi marginile acesteia. Fiecare pătrăţel care face parte dintr-o figură desenată este colorat, pentru a se distinge pe foaia de hârtie. Fiecare figură desenată este un pătrat cu laturile paralele cu marginile foii de hârtie.

Figura 1Figura 2Figura 3Figura 4

Cerinţă

Scrieţi un program care citeşte numărul N, corespunzător dimensiunii de 2N x 2N a foii de desen şi determină:

  1. Numărul de figuri de latură minimă desenate;
  2. Numărul total de pătrăţele colorate cel puţin o dată de pe foaia de hârtie.

Date de intrare

Fişierul de intrare fractal.in conţine pe prima linie numărul natural C reprezentând cerinţa din problemă care trebuie rezolvată (1 sau 2) şi pe a doua linie, un număr natural N cu semnificaţia de mai sus.

Date de ieşire

Dacă valoarea lui C este 1, fişierul de ieşire fractal.out va conţine un număr natural care reprezintă numărul de figuri de latură minimă. Dacă valoarea lui C este 2, fişierul de ieşire fractal.out va conţine un număr natural care reprezintă numărul total de pătrăţele colorate cel puţin o dată de pe foaia de hârtie.

Restricţii şi precizări

  • 1 < N ≤ 10000
  • Pentru 30% dintre teste N ≤ 30
  • Pentru rezolvarea corectă a cerinţei 1 se obţin 30 de puncte, iar pentru rezolvarea corectă a cerinţei 2 se obţin 70 de puncte.

Exemple

fractal.infractal.outExplicaţie
1
4
16
Suprafaţa de desen are 16 linii şi 16 coloane (figura 3). Pornind de la
figura iniţială se vor desena mai întâi 4 figuri, apoi 16 figuri.
1
5
64
Suprafaţa de desen are 32 linii şi 32 coloane (figura 4). Pornind de la
figura iniţială se vor desena mai întâi 4 figuri, apoi 16 figuri, respectiv 64
figuri de latură minimă.
2
4
148
Suprafaţa desenată este cea din figura 3. Numărul de pătrăţele colorate cel
puţin o dată este de 148 din totalul de 256 de pătrăţele.
2
5
700
Suprafaţa desenată este cea din figura 4. Numărul de pătrăţele colorate cel
puţin o dată este de 700 din totalul de 1024 de pătrăţele.
Trebuie sa te autentifici pentru a trimite solutii. Click aici