11312: 【原1312】划方格

题目

题目描述

author: Juda 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1312

Description

德州扑克玩得非常无聊，Juda来到了拉斯维加斯“玩游戏”。这次，他面对的是赌王。

他们玩的游戏是这样的。桌子上放着一个圆盘，圆盘上写着0到n-1的数字，按顺序排成一圈。

他们一开始扔骰子选择了一个数字K，每次一个人可以划连续若干数字，数量在1-k之间。但是已经被划过的数字不能再划。

比如说n=5，k=3那么一开始0 1 2 3 4排成一圈。假如第一个人把2划掉，第二个人可以划4 0 1，0 1 ，3 4 0等，但不能划1 2 3，因为2已经被划过了。

你可以认为赌王和Juda都绝顶聪明。强龙压不过地头蛇，所以每次赌王都先手，第一个没法划格子的人就输了。Juda想知道他是否一定能赢。

Input Format

多组数据。第一行为数据组数T

每组数据一行2个数字，表示n和k

Output Format

每行输出一组数据的答案。若Juda能赢输出"Yeah!"，否则输出"5555"

Sample Input

2
3 1
3 2

Sample Output

5555
Yeah!

Hint

20%数据保证k<=2 n<=1000

另外20%数据保证 n<=20

100%数据保证1<=n<=10^6 1<=k<=10 1<=T<=10

q4x3's solution

/**
 * 数学题
 * 赌王划什么，Juda划对称的
 **/
#include <iostream>

using namespace std;

int T, n, k;

int main() {
    cin >> T;
    for(int i = 0;i < T;++ i) {
        cin >> n >> k;
        if(k == 1) {
            if(n % 2 == 0) cout << "Yeah!" << endl;
            else cout << "5555" << endl;
        } else {
            if(n <= k) cout << "5555" << endl;
            else cout << "Yeah!" << endl;
        }
    }
}

victrid's solution

#include <iostream>
using namespace std;
int main() {
    // a math problem?
    int m, n, k;
    cin >> m;
    bool* ans = new bool[m];
    for (int i = 0; i < m; i++) {
        cin >> n >> k;
        //赌王把一个环剪开成了绳子。
        //Juda把绳子剪成长度相等的两条绳子。
        //赌王怎么剪Juda就怎么剪。就获胜了。

        //一次一个的划，能不能剪出来要看奇偶。
        if (k == 1) {
            ans[i] = n % 2;
            continue;
        }
        //一把就直接把所有数都划掉
        ans[i] = k >= n;
    }
    for (int i = 0; i < m; i++) {
        if (i)
            cout << endl;
        cout << (ans[i] ? "5555" : "Yeah!");
    }
    return 0;
}

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu1312.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, k, f[10005];
bool vis[10005];
void init(){
    n = read(), k = read();
}
void solve(){
    if (n <= k){
        printf("5555\n");
        return ;
    } 
    if (k == 1){
        printf("%s\n", (n % 2 == 0 ? "Yeah!": "5555"));
    }else printf("Yeah!\n");
    /*
    f[0] = 0;
    for (int i = 1; i <= n; ++i){
        memset(vis, 0, sizeof(vis));
        for (int j = 1; j <= k; ++j){
            for (int t = 0; t <= i - j; ++t)
                vis[f[t] ^ f[i - t - j]] = true;
        }
        for (int t = 0; t <= n; ++t)
            if (!vis[t]){
                f[i] = t;
                break;
            }
    }
    for (int i = 1; i <= n; ++i)
        cout << f[i] << endl;
    int ans = INT_MAX;
    for (int i = n - k; i < n; ++i)
        ans = min(ans, f[i]);
    printf("%s\n", (ans > 0 ? "Yeah!": "5555")); */
}
int main(){
    int T = read();
    while (T--){
        init();
        solve();
    }
    return 0;
}