[數學]1026 - 惡猿果實

Shaymin

原題：http://tioj.ck.tp.edu.tw/problems/1026
測試結果：http://tioj.ck.tp.edu.tw/submissions/2758

本人使用強大的觀察法找到了規律，解說如下：
參考表

N	D	距離dist	方法
1	X	1	1
2	0	3	+1+2
3	0	5	-1+2+4
4	1	7	+1+2+4
5	0	9	-1-2+4+8
6	1	11	+1-2+4+8
7	2	13	-1+2+4+8
8	3	15	+1+2+4+8
9	0	17	-1-2-4+8+16
10	1	19	+1-2-4+8+16
11	2	21	-1+2-4+8+16
12	3	23	+1+2-4+8+16
13	4	25	-1-2+4+8+16
14	5	27	+1-2+4+8+16

需特判的例外：
距離等於1時，答案為+1，而非-1+2。


推論：

• 末兩步為++
• 剩下其餘的步數，把-看成0，把+看成1，轉成二進位有規律，即為表中D值。
  

於是利用上兩推論可得公式：
1.求最高位H
[tex]H%3D%5Cleft%20%5Clfloor%20log_2dist%20%5Cright%20%5Crfloor[/tex]
2.求D值，即轉成N值相減
[tex]D%3D%5Cfrac%7Bdist+1%7D%7B2%7D-%5Cfrac%7B2%5EH+2%7D%7B2%7D[/tex]
簡單就能夠解決這一題了！

遊客，本帖隱藏的內容需要積分高於 300 才可瀏覽，您當前積分為 0