TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

88.4% (38/43)

Submission's AC Ratio

51.0% (80/157)

Description

拈(nim)是一種兩個人玩的遊戲,此遊戲的一種版本是,只有一堆棋子(n>0 顆),兩人輪流從這堆棋子中取走一些棋子。其規則是每次最少要取走1 顆棋子,但是取出的棋子數不可以超過$max{[n/k], 1}$顆,其中k 是在玩此遊戲之前所設定的值,k 的範圍是1≤k≤n。而$[n/k]$ 表示小於或等於n/k 的最大整數。即,當$0<n/k<1 $時,必須取走一顆。先將棋子拿光的人贏得此遊戲。

此遊戲的輸贏可以由nim 函數值決定,我們用$f_{k,n} $來表示n 顆棋子的nim 函數值。如果$f_{k,n} =0$,則表示輪到的人會輸,否則$(f_{k,n} ≠0)$輪到的人會贏。計算$f_{k,n} $的方法如下:若n=0,則其nim 函數值為0。當n≠0 時,令$m= \max\{n/k, 1\}$,則$f_{k,n} = mex(\{f_{k,n-1} , …, f_{k,n-m}\})$。上述式子中$mex(\{s_1, …, s_m\})$的意思是,未在$\{ s_1, …, s_m \}$集合中出現的最小非負整數,其中$s_i, i=1, …, m$,為大於等於0 的整數。例如:$mex(\{0, 1, 2, 6, 7\})=3$,$mex(\{1, 3\})=0$,$mex(\{0, 4, 5\})=1$。

根據上述定義,可知
$f_{2,0} = 0$,
$f_{2,1} = mex(\{ f_{2,0}\}) = mex(\{0\}) = 1$,
$f_{2,2} = mex(\{ f_{2,1}\}) = mex(\{1\}) = 0$,
$f_{2,3} = mex(\{ f_{2,2}\}) = mex(\{0\}) = 1$,
$f_{2,4} = mex( \{ f_{2,3}, f_{2,2} \} ) = mex(\{1, 0\}) = 2$。

以下列出$f_{2,0}$到$f_{2,7}$ 的值:0, 1, 0, 1, 2, 0, 3, 1。

Input Format

輸入只有一行,為兩個整數,即k 和n 的值。注意,k 的值只可能是1 或2。

Output Format

輸出一行包含一個正整數,代表測試資料的nim 值。

Sample Input

輸入範例一
1 26

輸入範例二
2 3

Sample Output

輸出範例一
26

輸出範例二
1

Hints

本題共有四個子題,每一子題可有多筆測試資料:
第一子題的測試資料 $k = 1$ 且$n ≤ 10^ 9$,全部解出可獲13 分;
第二子題的測試資料 $k = 2$ 且$n ≤ 30$,全部解出可獲23 分;
第三子題的測試資料 $k = 2$ 且$n ≤ 10^ 4$,全部解出可獲23 分;
第四子題的測試資料 $k = 2$ 且$n ≤ 10^ 9$,全部解出可獲41 分。

Problem Source

105學年度高級中學資訊學科能力競賽決賽 程式設計試題第三題

Subtasks

No. Testdata Range Score
1 0~4 13
2 5~9 23
3 5~14 23
4 5~19 41

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 524288 262144 1
1 1000 524288 262144 1
2 1000 524288 262144 1
3 1000 524288 262144 1
4 1000 524288 262144 1
5 1000 524288 262144 2 3 4
6 1000 524288 262144 2 3 4
7 1000 524288 262144 2 3 4
8 1000 524288 262144 2 3 4
9 1000 524288 262144 2 3 4
10 1000 524288 262144 3 4
11 1000 524288 262144 3 4
12 1000 524288 262144 3 4
13 1000 524288 262144 3 4
14 1000 524288 262144 3 4
15 1000 524288 262144 4
16 1000 524288 262144 4
17 1000 524288 262144 4
18 1000 524288 262144 4
19 1000 524288 262144 4