《算法竞赛·快冲300题》每日一题:“取石子游戏”

news/2025/2/2 6:48:24/

算法竞赛·快冲300题》将于2024年出版,是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。

文章目录

  • 题目描述
  • 题解
  • C++代码
  • Java代码
  • Python代码

取石子游戏” ,链接: http://oj.ecustacm.cn/problem.php?id=1119

题目描述

【题目描述】 有两堆石子,两个人轮流去取。每次取的时候,只能从较多的那堆石子里取,并且取的数目必须是较少的那堆石子数目的整数倍,最后谁能够把一堆石子取空谁就算赢。给定初始时石子的数目,如果两个人都采取最优策略,请问先手能否获胜。
【输入格式】 输入包含多数数据。每组数据一行,包含两个正整数a和b,表示初始时石子的数目。a, b≤109。输入以两个0表示结束。
【输出格式】 如果先手胜,输出"win",否则输出"lose"。
【输入样例】

34 12
15 24
0 0

【输出样例】

win
lose

题解

   设a≥b。当前能取空石子的获胜,那么要求当前的局面是a=kb,即a是b的整数倍,取空a后获胜。
   第一个样例“34, 12”的取法是:
      甲:34-24, 12 -> 10, 12
      乙:10, 12-10 -> 10, 2, 乙只有这一种取法
      甲:10-10, 2 -> 0, 2, 甲胜
   读者可以自行模拟第二个样例。
   下面讨论不同情况下的游戏局面。设开始时a≥b。
   (1)局面1:a = b。先手胜,因为他能取空一堆。
   (2)局面2:b < a < 2b。此局面对先手不利,因为他没有选择,只能在a这一堆中取b,剩下a-b。新的两堆是a’ = b,b’ = a-b。注意有a’≠b’,游戏并没有结束,先手还有机会。如果下一步仍有b’ <a’ < 2b’,不利的局面就转到了对方。如果a’ ≥ 2b’,见局面(3)的讨论。
   (3)局面3:a≥2b。
   如果a刚好是b的整k倍,a = kb,那么先手直接取空a=kb,先手胜。
   如果a不是b的整倍,先手可以取b的某个倍数,转为局面2的情况,让对方不利,并且让后续局面轮到自己时仍保持优势。
   例如a=13,b=5,甲先手,这样取:
      甲:13-5, 5 -> 8, 5, 下一步的(8, 5)转为局面2,让乙处于不利局面
      乙:8-5, 5 -> 3, 5, 乙只有这一种选择
      甲:3, 5-3 -> 3, 2, 甲也只有这一种选择
      乙:3-2, 2 -> 1, 2, 乙只有这一种选择
      甲:1, 2-2 -> 1, 0, 甲胜
   如果甲的第一步没取对,会导致失败:
      甲:13-10, 5 -> 3, 5
      乙:3, 5-3 -> 3, 2, 乙只有这一种选择
      甲:3-2, 2 -> 1, 2, 甲也只有这一种选择
      乙:1, 2-2 -> 1, 0, 乙胜
   也就是说,甲有两种选择,一种失败,一种赢,他肯定选赢的那种。
   总结以上讨论,先手获胜的条件是当前处于局面1和局面3。
【重点】 局面分析 。

C++代码

   在dfs()中转换游戏局面并返回结果。dfs()的复杂度是多少?第6行当b < a < 2b时执行dfs(a-b, b),每次a-b至少减一半,所以复杂度是 O ( l o g a ) O(loga) O(loga)的,当 a = 1 0 9 a=10^9 a=109时, l o g a = 30 loga = 30 loga=30

#include<bits/stdc++.h>
using namespace std;
bool dfs(int a, int b){if(a < b)  swap(a, b);      //保证多的石子在前if(a >= 2*b || a==b) return true;  //当前处于局面1、局面3,获胜return !dfs(a-b, b);      //局面2,对方只能取a-b
}
int main(){int a, b;while(cin>>a>>b && (a+b)) {if(dfs(a, b)) cout<<"win" <<endl;else          cout<<"lose"<<endl;}return 0;
}

Java代码

import java.util.Scanner;
public class Main {public static boolean dfs(int a, int b) {if (a < b) {int temp = a;a = b;b = temp;}if (a >= 2 * b || a==b)  return true;return !dfs(a - b, b);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int a = sc.nextInt();int b = sc.nextInt();if (a == 0 && b == 0)  break;            if (dfs(a, b)) System.out.println("win");else           System.out.println("lose");            }sc.close();}
}

Python代码

def dfs(a, b):if a < b:  a, b = b, a           #交换if a >= 2 * b or a==b: return Truereturn not dfs(a - b, b) 
while True:a, b = map(int, input().split())if a == 0 and b == 0:  breakif dfs(a, b):  print("win")else:          print("lose")

http://www.ppmy.cn/news/1085206.html

相关文章

【Python】OpenCV4图像、视频读写操作

读取/写入图像文件 OpenCV提供了imread函数来从文件中加载图像,以及imwrite函数来将图像写入文件。这些函数支持各种静态图像的文件格式。通常支持BMP、PNG、JPEG和TIFF等格式。 让我们来探索在OpenCV和NumPy中表示图像的结构。图像是一个多维数组;它有列和行的像素,并且每…

Android OkHttp源码阅读详解一

博主前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住也分享一下给大家 &#x1f449;点击跳转到教程 前言&#xff1a;源码阅读基于okhttp:3.10.0 Android中OkHttp源码阅读二(责任链模式) implementation com.squareup.o…

安装启动Stable Diffusion教程

一、下载源码 GitHub - AUTOMATIC1111/stable-diffusion-webui: Stable Diffusion web UI 二、安装miniconda 参考&#xff1a;安装启动yolo5教程_苍穹之跃的博客-CSDN博客 三、安装CUDA 参考&#xff1a;安装启动yolo5教程_苍穹之跃的博客-CSDN博客 四、创建虚拟环境 co…

工服穿戴检测联动门禁开关算法

工服穿戴检测联动门禁开关算法通过yolov8深度学习框架模型&#xff0c;工服穿戴检测联动门禁开关算法能够准确识别和检测作业人员是否按照规定进行工服着装&#xff0c;只有当人员合规着装时&#xff0c;算法会发送开关量信号给门禁设备&#xff0c;使门禁自动打开。YOLO的结构…

MySQL 基本操作1

目录 Create insert 插入跟新 1 插入跟新 2 Retrive select where 子句查询 1.查找数学成绩小于 80 的同学。 2.查询数学成绩等于90分的同学。 3.查询总分大于240 的学生 4.查询空值或者非空值 5.查询语文成绩在70~80之间的同学 6.查询英语成绩是99 和 93 和 19 和…

SpringBoot自写项目记录

设置静态资源映射 Slf4j 用来打印日志 Configuration Slf4j //设置静态资源映射 public class WebMvcConfig extends WebMvcConfigurationSupport {Overrideprotected void addResourceHandlers(ResourceHandlerRegistry registry) {log.info("开始静态资源配置");r…

[华为云云服务器评测] 华为云耀云服务器 Java、node环境配置

系列文章目录 第一章 [linux实战] 华为云耀云服务器L实例 Java、node环境配置 文章目录 系列文章目录前言一、任务拆解二、修改密码三、配置安全规则四、远程登录并更新apt五、安装、配置JDK环境5.1、安装openjdk,选择8版本5.2、检查jdk配置 六、安装、配置git6.1、安装git6.2…

core dump管理在linux中的前世今生

目录 一、什么是core dump&#xff1f; 二、coredump是怎么来的&#xff1f; 三、怎么限制coredump文件的产生&#xff1f; ulimit 半永久限制 永久限制 四、从源码分析如何对coredump文件的名字和路径管理 命名 管理 一些问题的答案 1、为什么新的ubuntu不能产生c…