Jums duotos svarstykles:
Ir svoriai : 1g, 3g, 9g, 27g, 81g, .... (ir t.t. i-tasis svoris yra 3^i)
Naudojant tokias svarstykles visai nesunku atsverti tam tikrą svorį. Pvz. jeigu reikia atsverti 55g galima į kairiąją svarstyklių pusę įdėti 27g svorį bei sveriamą medžiagą, o į dešinę 81g ir 1g svorį. Tada kai svarstyklės susibalansuos turėsime 27g + medžiaga = 81g + 1g, išsireiškę medžiagą turime: medžiaga = 81g + 1g - 27g = 55g.
Užduotis labai paprasta. Jums reiks atsverti 0 < T < 100, objektų. Kiekvienas iš jų sveria 0 <= X < 2000000000 gramų. Jūs turite nustatyti kiek mažiausiai svorių reikės norint subalansuoti svarstykles. kiekvienos rūšies svorių jūs turite tik po 1.
standard input | standard output |
---|---|
17 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 |
3 2 3 4 3 2 3 4 3 4 3 4 5 4 3 2 3 |