TopCoder

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

User's AC Ratio

93.9% (31/33)

Submission's AC Ratio

57.0% (69/121)

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

For Testdata: 0 ~ 4, Score: 13
For Testdata: 5 ~ 9, Score: 23
For Testdata: 5 ~ 14, Score: 23
For Testdata: 5 ~ 19, Score: 41
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 524288 262144
1 1000 524288 262144
2 1000 524288 262144
3 1000 524288 262144
4 1000 524288 262144
5 1000 524288 262144
6 1000 524288 262144
7 1000 524288 262144
8 1000 524288 262144
9 1000 524288 262144
10 1000 524288 262144
11 1000 524288 262144
12 1000 524288 262144
13 1000 524288 262144
14 1000 524288 262144
15 1000 524288 262144
16 1000 524288 262144
17 1000 524288 262144
18 1000 524288 262144
19 1000 524288 262144