Fişierul intrare/ieşire:pavare.in, pavare.outSursăOJI 2015 clasa a 8-a
AutorDaniel PopaAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.3 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Pavare (clasa a 8-a)

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

Prima linie a fişierului pavare.in conţine 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 pavare.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 pavare.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

  • V ∈ {1,2}
  • 1 ≤ N ≤ 1000 000 000
  • Pentru 30% din punctaj V = 1.

Exemplu

pavare.inpavare.outExplicaţii
1
7
5
Pentru drumul de lungime 7 sunt necesare 5 dale.
2
7
1 1 2 2 1
Soluţiile cu număr minim de dale sunt: 1 1 2 2 1, 1 2 1 2 1, 1 2 2 1 1.
Trebuie sa te autentifici pentru a trimite solutii. Click aici