Morris' Blog

2011-09-04 14:11:41Morris

d370. 2. 盤中飧

留言 0 收藏 0 推薦 0

內容：

大寶跟小寶兩兄弟都不喜歡吃白飯，可是他們的媽媽說，古人有寫詩說：
「鋤禾日當午，汗滴禾下土；誰知盤中飧，粒粒皆辛苦。」
浪費糧食是不應該的，所以一定要他們兩個人把飯吃完。
小寶覺得兄弟倆個人都受苦不如一個人受苦來的好，於是對大寶提出一個賭賽的方式
每餐都來比，誰輸了，誰就得負責把兩兄弟那餐的白飯吃光光。
賭賽的方式是這樣的，首先，由小寶拿出X 粒白飯，而大寶拿出Y 粒白飯。
接下來兩兄弟由小寶開始輪流吃這些X+Y 粒白飯，每次可以吃1 粒或是k 粒白飯
當剩下的白飯不足k 粒時，兩兄弟只能一人一粒的輪流吃，而規定吃到最後一粒的人，就得把剩下的白飯通通吃光。
小寶還說每次賭賽他會先決定X 跟k 兩個數字，之後在由哥哥大寶決定Y。
開始這種賭賽的前幾天，由於大寶想的太少，已經連吃了好幾天白飯
你能不能幫他寫一個程式，幫他算算該拿出多少粒白飯，才有機會贏？
 

輸入說明：

輸入的第一個整數n，即有多少筆測試資料。
接下來的n 行，每行都有兩個正整數X 跟k，由空白隔開，其中X 不超過10000，k 不超過1000。

輸出說明：

一筆測試資料輸出一行。
當存在一個大於0 且不超過10000 的Y 值能讓大寶不用吃白飯的時候，輸出最小的Y 值。反之，輸出0。

範例輸入：

範例輸出：

提示：

出處：

 
  
  
  97全國能力縣賽
  
    (管理：pcshic)


作法 : DP


/**********************************************************************************/
/*  Problem: d370 "2. 盤中飧" from 97全國能力縣賽                        */
/*  Language: C                                                                   */
/*  Result: AC (1ms, 293KB) on ZeroJudge                                          */
/*  Author: morris1028 at 2011-09-04 00:17:11                                     */
/**********************************************************************************/


#include<stdio.h>
#include<math.h>
main() {
    int t, x, k;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &x, &k);
        int i, j, DP[20001] = {1, 0}, Ans;
        for(i = 2; i < k; i++)
            DP[i] = !(DP[i-1]);
        for(i = 1; i <= 20000; i++) {
            for(j = 1; j <= k; j += k-1)
                if(i+j >= k && i+j <= 20000)
                    DP[i+j] |= !(DP[i]);
        }
        for(i = x+1; i <= 20000; i++)
            if(DP[i] == 0)
                break;
        if(i-x >= 10001)
            puts("0");
        else
            printf("%d\n", i-x);
    }
    return 0;
}