Rezolvare completă PbInfo #1144 Pavare1

Ca în mai toate poveștile, Făt-Frumos a căutat o Cosânzeană și a găsit-o, dar tatăl ei i-a cerut să-i paveze drumul de lungime N care leagă castelele sale. Dalele cu care va pava drumul au aceeași lățime (egală cu lățimea drumului) și lungimi numere naturale. Fiind un împărat cam sâcâit, acesta dorește ca pavarea să se facă folosind un număr minim de dale, diferența de lungime între două dale vecine să nu fie mai mare ca 1, iar prima și ultima dală să fie de lungime 1. Împăratul nu se mulțumește să primească de la Făt-Frumos doar un număr (numărul minim de dale necesare): el vrea și posibilitatea de pavare cea mai mică din punct de vedere lexicografic.

Compararea lexicografică a două șiruri de numere este o extensie la numere a comparării alfabetice a două cuvinte. Astfel, fiind date două șiruri numerice de aceeași lungime, A1, A2, … Am și B1, B2, … Bm, acestea sunt egale dacă și numai dacă Ai = Bi pentru orice i de la 1 la m. Șirul A este mai mic lexicografic decât șirul B dacă există o valoare k astfel încât Ak <Bk și Ai=Bi pentru orice i de la 1 la k-1. De exemplu, șirul 3, 5, 4, 1 este mai mare lexicografic decât șirul 3, 5, 2, 9 pentru că prima poziție pe care valorile diferă este poziția 3 (4>2), fără a mai conta valorile aflate după aceasta.

Cerință

Cunoscând lungimea drumului, determinați numărul minim de dale necesare pavării și posibilitatea de pavare cu număr minim de dale, care este cea mai mică din punct de vedere lexicografic.

Date de intrare

Fișierul de intrare pavare1.in conține pe prima linie un număr natural V. Linia a doua conține un număr natural N ce reprezintă lungimea drumului.

Date de ieșire

Dacă V va avea valoarea 1, în fișierul pavare1.out se va scrie, pe prima linie, doar numărul minim de dale necesare pavării.

Dacă V va avea valoarea 2, în fișierul pavare1.out se va scrie, pe prima linie, un șir de numere separate prin câte un spațiu, ce reprezintă soluția de pavare a drumului, folosind un număr minim de dale, care este cea mai mică din punct de vedere lexicografic.

Restricții și precizări

  • V poate fi 1 sau 2
  • 1 ≤ N ≤ 1000 000 000
  • Pentru 30% din punctaj V = 1.

Exemplul 1

pavare1.in

1
7

pavare1.out

5

Explicație

Pentru drumul de lungime 7 sunt necesare 5 dale.

Exemplul 2

pavare1.in

2
7

pavare1.out

1 1 2 2 1

Explicație

Soluțiile cu număr minim de dale sunt: (1 1 2 2 1), (1 2 1 2 1), (1 2 2 1 1).

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 Pavare1:

program pavare;
var i,n,k,c,t,p,z:longint;
f,g:text;
Begin
 assign(f,'pavare1.in');reset(f);
 assign(g,'pavare1.out');rewrite(g);
 read(f,c,n);
 k:=trunc(2*sqrt(n))-1;
 if sqrt(n)<>trunc(sqrt(n)) then k:=k+1;
 if c=1 then writeln(g,k)
  else
   begin
    z:=1;
    t:=1;
    p:=((k+k mod 2) div 2)*((k+k mod 2) div 2 + 1 - k mod 2);
    for i:=1 to k do
     begin
       if (i>=(k div 2 + n- p+1 + k mod 2))and(i<=k div 2 + k mod 2) then write(g,z-1,' ')
         else write(g,z,' ');
       if i>=(k div 2 + k mod 2) then t:=-1;
       if (i=k div 2)and(k mod 2 =0) then t:=0;
       z:=z+t;
     end;
   end;
  close(f);
  close(g);
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 #1144 Pavare1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1144 Pavare1 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!