首页 > 试题广场 >

青草游戏

[编程题]青草游戏

热度指数：5695 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛和羊羊都很喜欢青草。今天他们决定玩青草游戏。
最初有一个装有n份青草的箱子,牛牛和羊羊依次进行,牛牛先开始。在每个回合中,每个玩家必须吃一些箱子中的青草,所吃的青草份数必须是4的x次幂,比如1,4,16,64等等。不能在箱子中吃到有效份数青草的玩家落败。假定牛牛和羊羊都是按照最佳方法进行游戏,请输出胜利者的名字。

输入描述:

输入包括t+1行。
第一行包括一个整数t(1 ≤ t ≤ 100),表示情况数.
接下来t行每行一个n(1 ≤ n ≤ 10^9),表示青草份数

输出描述:

对于每一个n,如果牛牛胜利输出"niu",如果羊羊胜利输出"yang"。

示例1

输入

输出

niu
yang
niu

算法知识视频讲解

元气の悟空

#include<stdio.h>
int dp[10],n,x,i,j;
int main(){
    for(i=1;i<10;i++){
        int flag=0;
        for(j=1;j<=i;j*=4)
            if(dp[i-j]==0) flag=1;
        dp[i]=flag;
    }
    for(scanf("%d",&n),i=0;i<n;i++)
        scanf("%d",&x),printf("%s\n",dp[x%10]?"niu":"yang");
}

发表于 2017-11-29 13:04:48 回复(1)

Alejandro1

#include<iostream>

using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        int f = n%5;
        if (f == 0 || f == 2) cout << "yang" << endl;
        else cout << "niu" << endl;
    }
    return 0;
}

发表于 2019-01-26 23:32:06 回复(0)

泣血残阳

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while(t-- > 0) {
        int n;
        scanf("%d", &n);
        if(n % 5 == 0 || n % 5 == 2)
            cout << "yang" << endl;
        else
            cout << "niu" << endl;
    }
    return 0;
}

本题可以先使用暴力算法求解n较小时的基础情况，然后观察规律，可以发现序列以0,1,0,1,1,0,1,0,1,1...的规律延续，其中0表示先手必败，1表示先手必胜。因此该问题转化为由n对5取模，余0或2时必败，其他情况必胜。

发表于 2018-02-24 13:32:34 回复(0)

猎户座1

有和我一样题目都没读懂的吗

发表于 2019-02-04 12:49:34 回复(3)

茶月猫

我只是来分析一下题目的，仅给那些跟我一样没看懂题目，想不通的人。

题目里面说牛和羊都是按照最优方法进行游戏，什么是最优方法？

就是谁都不想输，因为牛是先手，如果牛不想输，那么一定会想尽一切办法让自己赢，比如说草堆里面有8根草，那么它先拿1根，无论后面牛和羊怎么吃，都是牛赢，所以当8的时候，是牛赢。一开始我想错了，以为牛吃4，羊也吃4，那不就羊赢了么，但是按照最优解，牛不可能第一口就吃4的。

那是不是说明，牛通过先手控制都能赢了呢？并不是，比如说7，无论牛先吃几口，都必输无疑。

所以本道题，讨论的是必输必赢的情况。

【来自没有看懂题目，乱敲代码然后一直以为是自己错了，调了一下午的小菜鸡】

发表于 2019-04-24 12:21:37 回复(3)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, x;
    scanf("%d", &n);
    while(n--){
        scanf("%d", &x);
        if(x%5==0 || x%5==2)
            puts("yang");
        else
            puts("niu");
    }
    return 0;
}

发表于 2020-10-12 00:43:59 回复(0)

Python

李镇强

数学博弈论问题

没有思路，只好参考解释。

归结：

n的幂次方捡石子

变成取一还是取n 的博弈论问题

for i in range(int(input())):
    print("niu" if int(input())%5 in [1,3,4] else 'yang')

发表于 2019-04-13 10:46:10 回复(0)

木然猫猫

数学题，找规律

arr = ['yang', 'niu', 'yang', 'niu', 'niu']
t = int(input())
for _ in range(t):
    n = int(input())
    print(arr[n % 5])

发表于 2019-03-18 20:44:30 回复(0)

向宇回桌

首先是用二人博弈dp，发现TLE(10e9那不是当然的嘛ww)。

import java.util.*;
public class Main {
    private static final int MAX = (int)1e9;
    private static boolean[] dp = new boolean[MAX + 5];
    private static final int strategyN = (int) (Math.log(MAX) / Math.log(4)) + 1;
    private static final int[] strategies = new int[strategyN];;
    static {
        for (int i= 0; i<strategyN; i++) {
            strategies[i] = (int)Math.pow(4, i);
            Arrays.fill(dp, false);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 1; i <= MAX; i++) {
            for (int j = 0; j < strategyN; j++) {
                if (strategies[j] <= i) {
                    dp[i] |= !dp[i - strategies[j]];
                }
            }
        }
        int T = sc.nextInt();
        while (T-- != 0) {
            for (int i = 0; i != MAX; i++) {
                if (dp[sc.nextInt()]) {
                    System.out.println("niu");
                } else {
                    System.out.println("yang");
                }
            }
            return;
        }
    }
}

然后因为是4的幂，所以找规律，发现是5个一循环，羊牛羊牛牛。证明可用数学归纳法。

所以，直接利用这个规律AC。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- != 0) {
            int in = sc.nextInt();
            System.out.println( (in % 5 == 0|| in % 5 == 2) ? "yang" : "niu");
        }
        return;
    }
}

发表于 2019-01-23 04:48:17 回复(0)

乔碧萝殿下

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int i = 0;
        // 这是一道规律题
        // 0 -> yang
        // 1 -> niu
        // 2 -> yang
        // 3 -> niu
        // 4 -> niu
        // 5 -> yang
        // 6 -> niu
        // 7 -> yang
        // 8 -> niu
        // 9 -> niu
        while(i < t) {
            long n = sc.nextLong();
            if(n % 5 == 0 || n % 5 == 2)
                System.out.println("yang");
            else 
                System.out.println("niu");
            i++;
        }
        sc.close();
    }
}

算法还没想好，规律就找出来了，emmmmm，对比上面大佬的解法，自己还是菜

发表于 2019-03-19 16:36:24 回复(0)

Python

华科平凡

python两行

参考：

https://blog.csdn.net/huyahuioo/article/details/80081031

一通秀的飞起的分析之后，模5为1，3，4时牛牛赢，否则输。***神奇

for _ in range(int(input())):
    print("niu" if int(input())%5 in [1,3,4] else 'yang')

发表于 2019-03-15 22:19:45 回复(11)

pein531

这种题一般都是找规律最快，和leetcode292题Nim游戏类似

当N%5==1或N%5==4，牛牛都可以把草的数量变为0，而羊羊面对0的草堆必输，因此牛牛必赢。
当N%5==0，牛牛只能吃1或4，因此牛牛吃完后，剩余的草量只能为1或4，对于两种情况，羊羊都能在吃完之后使剩余数量为0。正好与第一种情况互补，因此羊羊必赢。
当N%5==2，牛牛只能把草的数量变为1或者3（2-4+5），此时他当然只能选择3，如此羊羊可以选择吃1个草来使得N==2，因此羊羊可以做到：使牛牛始终面临的草量都为2，其中特殊情况即2，因此羊羊必赢。
当N%5==3，牛牛可以吃1个草，使得羊羊面临N%5==2的情况，正好与第三种情况互补，因此牛牛必赢。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strN;
        while((strN = br.readLine()) != null){
            int n = Integer.parseInt(strN);
            for(int i = 0; i < n; i++)
                solve(Integer.parseInt(br.readLine()));
        }
    }
    
    private static void solve(int num) {
        if(num % 5 == 0 || num % 5 == 2)
            System.out.println("yang");
        else
            System.out.println("niu");
    }
}

发表于 2020-11-05 11:23:03 回复(0)

名柳字思牧

def F(n):
    k = n%5
    if k in [0,2]:
        return 'yang'
    else:
        return 'niu'

T = int(input())
for t in range(T):
    print(F(int(input())))

结果是以5为周期的。因为4的幂模5的余数只有1和4两种，通过数学归纳法可以证明，余数是0-4分别对应羊牛羊牛牛

发表于 2020-04-21 14:37:56 回复(0)

Java

CR7M12

JAVA 牛牛和羊羊都很喜欢青草。今天他们决定玩青草游戏。
最初有一个装有n份青草的箱子,牛牛和羊羊依次进行,牛牛先开始。在每个回合中,每个玩家必须吃一些箱子中的青草,所吃的青草份数必须是4的x次幂,比如1,4,16,64等等。不能在箱子中吃到有效份数青草的玩家落败。假定牛牛和羊羊都是按照最佳方法进行游戏,请输出胜利者的名字。

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin = new Scanner(System.in);
		int n = cin.nextInt();// 总的情况
		String str[] = {"yang","niu","yang","niu","niu"};
		for (int i = 0; i < n; i++) {
			long a=cin.nextLong();
			System.out.println(str[(int) (a%5)]);
		}
	}

}

发表于 2019-11-07 09:02:00 回复(0)

AyaBrea

这种题目一看，感觉很复杂，然后就从头开始枚举：牛羊牛牛羊牛羊牛牛羊...我居然没有发现规律=。=我以为这是个很复杂的动态规划的题目，嗨呀好气

发表于 2019-09-07 19:49:07 回复(0)

莫欺少年穷201810091601235

😎

发表于 2019-04-25 19:48:45 回复(0)

不强化学习

#include<iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    while (n-->0){
        int m;
        cin >> m;
        if (m % 5 == 2 || m % 5 == 0)
            cout << "yang" << endl;
        else
            cout << "niu" << endl;
    }
    return 0;
}

发表于 2019-04-25 18:35:03 回复(0)

C/C++

韦禹

#include<stdio.h>
int main(){
    int t;int n;scanf("%d",&t);
    for(int i=0;i!=t;++i){
        scanf("%d",&n);
        switch(n%5){
            case 0:
                printf("%s\n","yang");break;
            case 1:
                printf("%s\n","niu");break;
            case 2:
                printf("%s\n","yang");break;
            case 3:
            case 4:
                printf("%s\n","niu");break;
        }
    }
}

发表于 2019-04-25 15:41:04 回复(0)

C/C++

小石子2409

#include <iostream>

using namespace std;

int main()
{
int t,n;
cin >> t;
while(t--){
cin >> n;
int f = n % 5;
if(f == 0){
cout << "yang" << endl;
}else if(f == 1){
cout << "niu" << endl;
}else if(f == 2){
cout << "yang" << endl;
}else if(f == 3){
cout << "niu" << endl;
}else if(f == 4){
cout << "niu" << endl;
}
}
return 0;
}

编辑于 2019-04-24 11:06:55 回复(0)

黄宗文

n = int(input())
for i in range(n):
    if int(input())%5 in [1, 3, 4]:
        print('niu')
    else:
        print('yang')
        
# 4的幂次结果%5只会是1或4
# r%5 == 2, x%5 == 1 or 4 , (r-x)%5 == 1 or 3
# r%5 == 2, x%5 == 4, (r-x)%5 == 3
"""
for i in range(int(input())):
    print('niu' if int(input())%5 in [1, 3, 4] else 'yang')
"""

发表于 2019-04-15 16:30:08 回复(0)

提交观点

问题信息

模拟算法工程师爱奇艺 2018 数学

来自：爱奇艺2018秋季校招...

上传者：小小

难度：

28条回答 83收藏 7460浏览

通过挑战的用户

查看代码

小蔡先生a

2023-03-02 22:30:03
One Peach

2023-02-14 20:47:53
samabc

2023-02-02 13:09:29
__Gray__

2022-12-27 21:46:37
牛客11510...

2022-11-25 20:25:41

青草游戏

输入描述:

输出描述:

输入

输出

数学博弈论问题

n的幂次方捡石子

变成取一还是取n 的博弈论问题

python两行

问题信息

热门推荐

通过挑战的用户

相关试题

青草游戏

输入描述:

输出描述:

输入

输出

数学博弈论问题

n的幂次方捡石子

变成 取一还是取n 的博弈论问题

python两行

问题信息

热门推荐

通过挑战的用户

相关试题

变成取一还是取n 的博弈论问题