Din cauza dezvoltării alerte a tehnicii, calculatoarele
„second-hand” s-au devalorizat brusc în aşa măsură, încât Mircea a hotărât
să deschidă un magazin unde computerele se vor vinde la kilogram. Pentru
o idee aşa de originală, Mircea a hotărât că va cântări marfa la fel
de original.
El va folosi o balanţă şi un set de greutăţi cu valori 1
gram, p grame,
p2
grame, p3
grame, ... (p
număr impar), greutăţi pe care le va închiria de la o firmă.
Un set de greutăţi "de tip p"
conţine din fiecare tip de greutate (p-1)/2
bucăţi, fiindcă aşa se spune, că orice gramaj întreg se poate cântări
cu ajutorul acestor greutăţi (cel puţin până acuma nu s-a găsit nici
un contraexemplu).
Setul de greutăţi se poate închiria cu condiţia că dacă e nevoie de
greutatea pn,
va trebui să se închirieze întregul set 1,p,p2,...,pn
(din fiecare tip de greutate (p-1)/2
bucăţi).
Având în vedere că fiecare greutate are acelaşi preţ unic de închiriere
şi cunoscând greutatea maximă a unui calculator ce urmează să fie cântărit
pe balanţă, Mircea vrea să calculeze numărul minim de greutăţi ce trebuie
să fie închiriate.
De exemplu, un calculator cu greutatea de 1 kg se poate cântări optim
cu greutăţile de tip 3
astfel: 1000g=1g+27g+243g+729g.
Deci, se vor închiria greutăţi până la 729g
inclusiv (în total 7 bucăţi: 1,3,9,27,81,243,729).
Pentru a cântări optim un calculator de 2 kg cu greutăţi de tip 5,
vom proceda astfel: 2000g+625g+625g=125g+3125g,
deci, se vor închiria greutăţi până la 3125g inclusiv (în total 12
bucăţi: 1,1,5,5,25,25,125,125,625,625,3125,3125).
Din cele două exemple putem observa, că nu e necesară folosirea tuturor
greutăţilor închiriate la măsurare.
Dacă sunt mai multe soluţii, se va alege
soluţia care are număr minim de greutăţi pe cântar.
Cerinţă
Cunoscând greutatea maximă M
a unui calculator, măsurată în grame, să se calculeze numărul minim de
greutăţi ce trebuie să fie închiriate pentru a cântări un calculator cu
greutatea M,
precum şi o modalitate de cântărire cu număr minim de greutăţi.
Date de intrare
Fişierul de intrare balanta.in
conţine pe prima linie numărul natural p.
Pe cea de a doua linie se află numărul natural M.
Date de ieşire
Dacă există soluţie, fişierul de ieşire balanta.out
va conţine trei linii. Pe prima linie va fi scris numărul minim de greutăţi
ce trebuie închiriate. Pe cea de a doua linie va fi scris conţinutul talerului
stâng al balanţei (primul număr va fi M,
urmat de celelalte greutăţi necesare, ordonate crescător). Pe cea de a
treia linie va fi scris conţinutul talerului drept (greutăţile ordonate
crescător). Valorile scrise pe aceeaşi linie vor fi separate prin câte
un spaţiu.
Dacă nu există soluţie, atunci fişierul balanta.out
va conţine o singură linie pe care va fi scrisă valoarea -1.
Restricţii
p are valori
din multimea {3,5,7,9}
1≤M≤100 000 000
Exemple
balanta.in
balanta.out
Explicaţii
3
1000
7
1000
1 27 243 729
se vor închiria 7 greutăţi cu valorile: 1,3,9,27,81,243,729
pe talerul stâng avem doar calculatorul de 1000g
pe talerul drept avem greutăţile de 1g, 27g, 243g, 729g
balanta.in
balanta.out
Explicaţii
5
2000
12
2000 625 625
125 3125
se vor închiria 12 greutăţi cu valorile: 1,1,5,5,25,25,125,125,625,625,3125,3125
pe talerul stâng avem calculatorul de 2000g si două greutăţi de
625 g
pe talerul drept avem greutăţile de 125g, 3125g