増やす減らす二倍する〜横へな 2013.9.6 参考問題

問題

装置がある。
装置には数を表示する場所と、3つのボタン +1 、 -1 、 ×2 がある。
表示されている数は、最初 0 になっている。
なにか決まった数(例えば 59 )があり、あなたはこの数を装置に表示したいと思っている。目的の数値に到達するために、最低何回ボタンを押さなければならないのかを計算せよ。

たとえば 59 に到達するためには、 +1, +1, ×2, ×2, ×2, -1, ×2, ×2, -1 のように、 9 回の操作が必要となる。

入力と出力

入力文字列は 59 のように単なる整数 ( 10進数 ) であり、目的の数を示している。

出力も単なる整数を文字列にしたもので、 9 のような文字列を出力すればよい。

補足

装置は負の数を表示できない。 0が表示されている時に -1 を押すと、装置が故障するものとする。くれぐれも 0 が表示されている時に -1 を押さないこと。
不正な入力に対処する必要はない。
実装ができた方は Qiitaの記事のコメント欄からリンクを張っていただくと見つけやすくて助かります。

サンプルデータ

#	入力	期待	例
0	`59`	`9`	+1 ×2 ×2 ×2 ×2 -1 ×2 ×2 -1
1	`10`	`5`	+1 +1 ×2 +1 ×2
2	`11`	`6`	+1 ×2 ×2 +1 ×2 +1
3	`12`	`5`	+1 +1 +1 ×2 ×2
4	`13`	`6`	+1 ×2 +1 ×2 ×2 +1
5	`14`	`6`	+1 +1 ×2 ×2 -1 ×2
6	`15`	`6`	+1 ×2 ×2 ×2 ×2 -1
7	`16`	`5`	+1 +1 ×2 ×2 ×2
8	`17`	`6`	+1 +1 ×2 ×2 ×2 +1
9	`18`	`6`	+1 +1 ×2 ×2 +1 ×2
10	`27`	`8`	+1 +1 ×2 ×2 -1 ×2 ×2 -1
11	`28`	`7`	+1 ×2 +1 ×2 +1 ×2 ×2
12	`29`	`8`	+1 ×2 ×2 ×2 ×2 -1 ×2 -1
13	`30`	`7`	+1 +1 ×2 ×2 ×2 -1 ×2
14	`31`	`7`	+1 ×2 ×2 ×2 ×2 ×2 -1
15	`32`	`6`	+1 +1 ×2 ×2 ×2 ×2
16	`33`	`7`	+1 ×2 ×2 ×2 ×2 ×2 +1
17	`34`	`7`	+1 ×2 ×2 ×2 ×2 +1 ×2
18	`35`	`8`	+1 +1 ×2 ×2 ×2 +1 ×2 +1
19	`41`	`8`	+1 +1 ×2 +1 ×2 ×2 ×2 +1
20	`71`	`9`	+1 +1 ×2 ×2 +1 ×2 ×2 ×2 -1
21	`1023`	`12`	+1 +1 ×2 ×2 ×2 ×2 ×2 ×2 ×2 ×2 ×2 -1
22	`1024`	`11`	+1 +1 ×2 ×2 ×2 ×2 ×2 ×2 ×2 ×2 ×2
23	`1025`	`12`	+1 +1 ×2 ×2 ×2 ×2 ×2 ×2 ×2 ×2 ×2 +1
24	`1707`	`17`	+1 +1 +1 ×2 +1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1
25	`683`	`15`	+1 ×2 ×2 +1 ×2 +1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1
26	`123`	`10`	+1 ×2 ×2 ×2 ×2 ×2 -1 ×2 ×2 -1
27	`187`	`11`	+1 +1 +1 ×2 ×2 ×2 ×2 -1 ×2 ×2 -1
28	`237`	`12`	+1 ×2 ×2 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 +1
29	`5267`	`18`	+1 +1 ×2 +1 ×2 ×2 ×2 +1 ×2 ×2 ×2 +1 ×2 ×2 +1 ×2 ×2 -1
30	`6737`	`18`	+1 +1 +1 ×2 ×2 +1 ×2 ×2 ×2 +1 ×2 ×2 +1 ×2 ×2 ×2 ×2 +1
31	`14796`	`20`	+1 +1 +1 ×2 +1 ×2 ×2 +1 ×2 ×2 ×2 -1 ×2 ×2 ×2 +1 ×2 +1 ×2 ×2
32	`18998`	`20`	+1 +1 ×2 ×2 +1 ×2 ×2 +1 ×2 ×2 ×2 +1 ×2 ×2 ×2 -1 ×2 ×2 -1 ×2
33	`23820`	`20`	+1 ×2 +1 ×2 ×2 ×2 ×2 -1 ×2 -1 ×2 ×2 ×2 ×2 +1 ×2 ×2 -1 ×2 ×2
34	`30380`	`21`	+1 ×2 ×2 ×2 ×2 -1 ×2 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2
35	`31119`	`21`	+1 ×2 ×2 ×2 ×2 ×2 -1 ×2 -1 ×2 ×2 -1 ×2 ×2 ×2 +1 ×2 ×2 ×2 ×2 -1
36	`33301`	`20`	+1 ×2 ×2 ×2 ×2 ×2 ×2 +1 ×2 ×2 ×2 ×2 ×2 +1 ×2 ×2 +1 ×2 ×2 +1
37	`33967`	`21`	+1 +1 ×2 ×2 ×2 ×2 +1 ×2 ×2 ×2 +1 ×2 +1 ×2 ×2 -1 ×2 ×2 ×2 ×2 -1
38	`35443`	`22`	+1 ×2 ×2 ×2 ×2 +1 ×2 ×2 +1 ×2 ×2 +1 ×2 ×2 ×2 -1 ×2 ×2 ×2 +1 ×2 +1
39	`35641`	`22`	+1 +1 ×2 ×2 ×2 +1 ×2 +1 ×2 ×2 -1 ×2 ×2 +1 ×2 ×2 ×2 -1 ×2 ×2 ×2 +1
40	`43695`	`23`	+1 ×2 +1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 ×2 ×2 -1
41	`44395`	`23`	+1 ×2 +1 ×2 ×2 -1 ×2 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1
42	`44666`	`22`	+1 +1 ×2 +1 ×2 +1 ×2 ×2 ×2 ×2 -1 ×2 -1 ×2 ×2 ×2 ×2 ×2 -1 ×2 -1 ×2
43	`987`	`14`	+1 ×2 ×2 ×2 ×2 ×2 -1 ×2 ×2 ×2 -1 ×2 ×2 -1
44	`1021`	`13`	+1 +1 ×2 ×2 ×2 ×2 ×2 ×2 ×2 -1 ×2 ×2 +1
45	`1019`	`13`	+1 +1 ×2 ×2 ×2 ×2 ×2 ×2 ×2 -1 ×2 ×2 -1
46	`1015`	`13`	+1 ×2 ×2 ×2 ×2 ×2 ×2 ×2 -1 ×2 ×2 ×2 -1
47	`1007`	`13`	+1 ×2 ×2 ×2 ×2 ×2 ×2 -1 ×2 ×2 ×2 ×2 -1
48	`1011`	`14`	+1 +1 ×2 ×2 ×2 ×2 ×2 -1 ×2 ×2 +1 ×2 ×2 -1
49	`1003`	`14`	+1 ×2 ×2 ×2 ×2 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1
50	`983`	`14`	+1 +1 ×2 ×2 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 ×2 -1
51	`999`	`14`	+1 ×2 ×2 ×2 ×2 ×2 ×2 -1 ×2 -1 ×2 ×2 ×2 -1
52	`2731`	`18`	+1 ×2 ×2 +1 ×2 +1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1
53	`6827`	`20`	+1 +1 +1 ×2 +1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1
54	`10923`	`21`	+1 +1 ×2 +1 ×2 +1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1
55	`27307`	`23`	+1 ×2 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1
56	`43691`	`24`	+1 ×2 +1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1
57	`109227`	`26`	+1 ×2 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1
58	`174763`	`27`	+1 ×2 +1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1 ×2 ×2 -1

C/C++/Java 用のテストデータ

/*0*/ test( "59", "9" );    
/*1*/ test( "10", "5" );    
/*2*/ test( "11", "6" );    
/*3*/ test( "12", "5" );    
/*4*/ test( "13", "6" );    
/*5*/ test( "14", "6" );    
/*6*/ test( "15", "6" );    
/*7*/ test( "16", "5" );    
/*8*/ test( "17", "6" );    
/*9*/ test( "18", "6" );    
/*10*/ test( "27", "8" );    
/*11*/ test( "28", "7" );    
/*12*/ test( "29", "8" );    
/*13*/ test( "30", "7" );    
/*14*/ test( "31", "7" );    
/*15*/ test( "32", "6" );    
/*16*/ test( "33", "7" );    
/*17*/ test( "34", "7" );    
/*18*/ test( "35", "8" );    
/*19*/ test( "41", "8" );    
/*20*/ test( "71", "9" );    
/*21*/ test( "1023", "12" );    
/*22*/ test( "1024", "11" );    
/*23*/ test( "1025", "12" );    
/*24*/ test( "1707", "17" );    
/*25*/ test( "683", "15" );    
/*26*/ test( "123", "10" );    
/*27*/ test( "187", "11" );    
/*28*/ test( "237", "12" );    
/*29*/ test( "5267", "18" );    
/*30*/ test( "6737", "18" );    
/*31*/ test( "14796", "20" );    
/*32*/ test( "18998", "20" );    
/*33*/ test( "23820", "20" );    
/*34*/ test( "30380", "21" );    
/*35*/ test( "31119", "21" );    
/*36*/ test( "33301", "20" );    
/*37*/ test( "33967", "21" );    
/*38*/ test( "35443", "22" );    
/*39*/ test( "35641", "22" );    
/*40*/ test( "43695", "23" );    
/*41*/ test( "44395", "23" );    
/*42*/ test( "44666", "22" );    
/*43*/ test( "987", "14" );    
/*44*/ test( "1021", "13" );    
/*45*/ test( "1019", "13" );    
/*46*/ test( "1015", "13" );    
/*47*/ test( "1007", "13" );    
/*48*/ test( "1011", "14" );    
/*49*/ test( "1003", "14" );    
/*50*/ test( "983", "14" );    
/*51*/ test( "999", "14" );    
/*52*/ test( "2731", "18" );    
/*53*/ test( "6827", "20" );    
/*54*/ test( "10923", "21" );    
/*55*/ test( "27307", "23" );    
/*56*/ test( "43691", "24" );    
/*57*/ test( "109227", "26" );    
/*58*/ test( "174763", "27" );

増やす減らす二倍する 〜 横へな 2013.9.6 参考問題

問題

入力と出力

補足

サンプルデータ

C/C++/Java 用のテストデータ

増やす減らす二倍する〜横へな 2013.9.6 参考問題