竹園論壇

標題: [數學]1026 - 惡猿果實 [打印本頁]

作者: Shaymin 時間: 2014-9-25 20:29
標題: [數學]1026 - 惡猿果實
本帖最後由 Shaymin 於 2014-9-25 22:30 編輯

原題：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]
簡單就能夠解決這一題了！

歡迎光臨竹園論壇 (http://forum.tfcis.org/)