c - SYNC13C SPOJ 错误答案

Question

Link to challenge

Ramesh and Suresh get a box full of five stars on lottery each. Since both the boxes need not have the same number of chocolates, they decide to play a game. The winner gets to have both the boxes of chocolates. They play alternatively and Suresh starts the game. Given the number of chocolates in both the boxes, let them be c1 and c2, the player takes either c1 or c2 number of chocolates and divide the remaining box of chocolates to two boxes (these two boxes need not have the same number of chocolates). The player who cannot make such a move loses. Input

First line of input contains a number T(1<=T<=1000), the number of test cases. Then follows T lines each containing two space separated integers c1 and c2

(1<=c1<=c2<=10000).

Output For each test case print "Ramesh" or "Suresh" depending on who is the winner.

Input: 2 3 1 4 5

Output: Ramesh Suresh

这是我的尝试，它给了我错误的答案。也给我一些更多的测试用例。

#include<stdio.h>
int main()
{
    int t,c1,c2,max,count,min;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&c1,&c2);
        min=c1<c2?c1:c2;  
        max=c1>c2?c1:c2;
        if(max%2!=0 && min%2!=0) 
            printf("Ramesh\n");
        else if(min%2==0 && max%2!=0)
            printf("Suresh\n");
        else if(max%2==0 && min%2!=0)
            printf("Ramesh\n");  
        else printf("Suresh\n");
    }
    return 0; 
}

Answer 1

代码比那要简单得多。首先，让我解释一下算法。

设 W 是一个数组，其中，

W[i] = 1 如果用户通过选择拆分 i 盒巧克力获胜，如果他输了则为 0。

让我们构建这个数组，我们将得到一个模式。

W[1] = 0，因为不能拆开一盒巧克力。

对于所有i>1，我们有:

W[i] = 1 if there exists integers a and b such that a+b=i and W[a]=W[b]=0 , 0 otherwise.

上面的陈述意味着，对于通过选择 i 巧克力盒获胜的用户，他需要确保，无论他进一步选择哪个盒子，他的对手都会输。他的对手输了意味着 W[a]=W[b]=0 和 a+b=i。

如果我们尝试填充这个数组，我们会得到，

W : 1 2 3 4 5 6 7...

val: 0 1 0 1 0 1 0...

这意味着如果给定的整数之一是偶数，那么 suresh 将获胜。如果它们都是奇数，则意味着 ramesh 将获胜。

希望我清楚。