洛谷P2252 取石子游戏(威佐夫博弈)

题目背景

题目描述

有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。

输入输出格式

输入格式:

输入共一行。

第一行共两个数a, b,表示石子的初始情况。

输出格式:

输出共一行。

第一行为一个数字1、0或-1,如果最后你是胜利者则为1;若失败则为0;若结果无法确定则为-1。

输入输出样例

输入样例#1: 

8 4

输出样例#1: 

1

说明

[数据范围]

50%的数据,a, b <= 1000

100%的数据,a, b <= 1 000 000 000

威佐夫博弈的裸题

不过不是那么好AC,数据太刁钻了

威佐夫博弈的必败条件

abs(a,b)*(1+\sqrt{5})/2 = min(a,b)

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#define int long long 
using namespace std;
const int MAXN=1e6+10,INF=1e9+10;
main()
{
    int a,b;
    scanf("%lld%lld",&a,&b);
    if(a>b) swap(a,b);
    int temp=abs(a-b);
    int ans=temp*(1.0+sqrt(5.0))/2.0;
    if(ans==a) printf("0");
    else        printf("1");
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏WOLFRAM

交互式查询化学键信息

2323
来自专栏有趣的Python和你

微信好友全头像直接上图代码代码分析

1433
来自专栏人工智能LeadAI

tensorflow读取数据-tfrecord格式

概述关于tensorflow读取数据,官网给出了三种方法: 1、供给数据:在tensorflow程序运行的每一步,让python代码来供给数据 2、从文件读取数...

9976
来自专栏数据星河

建模常用的pandas语句

  pandas对象是Python常用的数据分析模块,它主要包括series对象,dataframe对象和index对象。每种对象都有自己所特有的方法和属性。今...

420
来自专栏数据结构与算法

LOJ #115. 无源汇有上下界可行流

#115. 无源汇有上下界可行流 描述 这是一道模板题。 n n n 个点,m m m 条边,每条边 e e e 有一个流量下界 lower(e) \text{...

3367
来自专栏吉浦迅科技

DAY17:阅读纹理内存之纹理引用API

1442
来自专栏龙首琴剑庐

Java基准测试利器OpenJDK-JMH

5249
来自专栏mathor

搜索(5)

1633
来自专栏marsggbo

Udacity并行计算课程笔记-The GPU Hardware and Parallel Communication Patterns

本小节笔记大纲: 1.Communication patterns gather,scatter,stencil,transpose 2.GPU hardwa...

2276
来自专栏C语言及其他语言

【每日一题】1442[蓝桥杯][历届试题]打印十字图

继续给大家来一个蓝桥杯的真题,想练就能成大神! 请看题: 问题描述 小明为某机构设计了一个十字型的徽标(并非红十字会啊),如下所示: ..$$$$$...

2869

扫码关注云+社区

领取腾讯云代金券