Fișierul intrare/ieșire pavare.in, pavare.out Sursă OJI 2015 clasa a 8-a
Autor Daniel Popa Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.3 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in pavare.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii