Rezolvare completă PbInfo #1701 Birouri

Arhi şi-a propus să extindă clădirea de birouri pe care a proiectat-o iniţial pe un singur nivel numerotat cu 1, împărţit în n*n zone pătratice de latură 1, fiecare corespunzând unui birou, prin construirea mai multor niveluri. În colţurile tuturor birourilor se construiesc grinzi de rezistenţă. Pentru a asigura rezistenţa întregii clădiri, Arhi va proiecta niveluri noi, numerotate cu 2, 3,… atât timp cât conțin cel puțin un birou și sunt respectate următoarele patru reguli:

  • R1: fiecare nivel nou va fi proiectat sub forma unui dreptunghi sau pătrat de arie maximă pentru nivelele cu număr impar, respectiv, sub forma unui pătrat de arie maximă pentru nivelele cu număr par;
  • R2: fiecare dintre colţurile zidurilor unui nivel nou trebuie plasat pe câte o grindă de rezistenţă dintre două sau mai multe birouri de pe nivelul precedent;
  • R3: oricare două dintre colţurile zidurilor unui nivel nou vor fi plasate pe ziduri diferite (un zid nu se poate suprapune în totalitate pe alt zid) şi cel puţin două vârfuri opuse ale unui nivel nou se vor afla pe ziduri opuse ale nivelului precedent;
  • R4: orice porţiune de zid de pe nivelul k (k>1), construită deasupra unui birou de pe nivelul k-1, se va suprapune exact peste una dintre laturile biroului, sau îl va străbate în diagonală.

Birourile de pe nivelul k (k>1), vor fi construite exact deasupra celor de pe nivelul precedent, astfel, nivelurile 2, 4 etc. vor avea lângă ziduri spaţii triunghiulare care nu vor aparţine niciunui birou.

Numerele inscripţionate pe birouri în imaginea de mai sus, indică nivelul corespunzător birourilor vizibile de deasupra clădirii.

Cerința

Cunoscându-se lungimea n a laturii primului nivel al clădirii, să se determine:

  1. numărul maxim de niveluri pe care le poate avea clădirea;
  2. numărul total de birouri ale clădirii cu număr maxim de niveluri.

Date de intrare

Fișierul de intrare birouri.in conține pe prima linie una dintre valorile 1 sau 2, reprezentând cerinţa 1, dacă se cere determinarea numărului maxim de niveluri pe care le poate avea clădirea, respectiv cerinţa 2, dacă se cere determinarea numărului total de birouri al clădirii cu număr maxim de niveluri.

Linia a doua conţine un număr natural n (reprezentând lungimea fiecărui zid al primului nivel al clădirii).

Date de ieșire

Fișierul de ieșire birouri.out va conține pe prima linie pe prima linie un număr natural reprezentând numărul maxim de niveluri pe care le poate avea clădirea, dacă cerinţa a fost 1, respectiv un număr natural reprezentând numărul total de birouri ale clădirii cu număr maxim de niveluri, dacă cerinţa a fost 2.

Restricții și precizări

  • 3 ≤ n ≤ 32768
  • Pentru rezolvarea corectă a cerinţei 1 se acordă 30% din punctaj, iar pentru rezolvarea corectă a cerinţei 2 se acordă 70% din punctaj.

Exemplul 1

birouri.in

1
10

birouri.out

5

Explicație

Exemplul corespunde imaginii de mai sus. Clădirea cu nivelul de la bază de latură 10 va avea 5 niveluri.

Nivelul 6 nu se mai construieşte, deoarece nu ar conţine niciun birou.

Exemplul 2

birouri.in

2
10

birouri.out

172

Explicație

Clădirea cu 5 niveluri şi latura de la bază de lungime 10 are:

  • pe primul nivel 100 birouri;
  • pe nivelul doi 40 birouri;
  • pe nivelul trei 24 birouri;
  • pe nivelul patru 4 birouri;
  • pe nivelul cinci 4 birouri.

100 + 40 + 24 + 4 + 4 = 172

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Birouri:

program CS_birouri;
var
    n, m, k, c, niv, b, p : longint;
    fin, fout:text;
begin
    assign(fin, 'birouri.in');
    assign(fout,'birouri.out');
    reset(fin); rewrite(fout);
        readln(fin, c, n);
    m:=n;
        repeat

            inc(niv);
            if niv mod 2 = 1 then
                    b := b + n * m
            else begin
            if n > m then k := m
                 else k := n;
                    p := k * k div 2 - k;
            b := b + p;
                    if p = 0 then dec(niv);
                    if k mod 4 = 0 then begin
                k := k div 2;
                n := k; m := k
            end
                    else begin
                n := n div 2 - 1; m := n + 2
            end
            end;
        until not((n <> 0) and (n mod 2 = 0));
        if c=1 then
            writeln(fout, niv)
        else
            writeln(fout, b);
    close(fin); close(fout);
end.

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1701 Birouri

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1701 Birouri de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!