luogu-B3721 [语言月赛202303] Stone Gambling S

GESP二级练习，多层循环分支练习，难度★✮☆☆☆。

luogu-B3721 [语言月赛202303] Stone Gambling S

题目要求

题目描述

Farmer John 和 Bessie 正在玩一个石头游戏。

初始时，Farmer 手中有 $x$ 块石头，Bessie 有 $y$ 块。他们的眼前有一个石头堆，可以认为里面有无限块石头。

从 Farmer John 开始，双方轮流操作。每次操作中，如果自己的石头数量小于对方的石头数，就从石头堆中拿 $1$ 块石头；否则，就要向石头堆里扔石头直到手中的石头数不超过本次操作开始时自身石头数的一半（这就是说，如果本次操作开始时自己有 $w$ 块石头，则需要扔石头直到手里还剩 $\left\lfloor\frac w 2 \right\rfloor$ 块石头）。当有一方在操作完成后手头没有石头（即石头数量为 $0$）了，那么游戏结束。

请你求出游戏结束时双方手中的石头数量。

输入格式

本题单个测试点内有多组测试数据。

第一行是一个整数，表示数据组数 $T$。接下来 $T$ 行，每行表示一组数据的输入信息。

对每组数据，输入只有一行两个整数，依次表示 Farmer John 初始的石头数 $x$ 和 Bessie 初始的石头数 $y$。

输出格式

对每组数据，输出一行两个整数，依次表示 Farmer John 最终的石头数 $x$ 和 Bessie 最终的石头数 $y$。

输入 #1

1
2 5

输出 #1

0 1

说明/提示

样例 1 解释

下表中，用 $s$ 和 $t$ 分别代表 Farmer John 和 Bessie 在对应轮次开始前手中的石头数，每行代表一次操作。

数据规模与约定

• 对 $20\%$ 的数据，保证 $x, y \leq 5$。
• 另有 $20\%$ 的数据，保证 $x = y$。
• 对 $60\%$ 的数据，保证 $x, y \leq 10^9$，$T = 1$。
• 对 $100\%$ 的数据，保证 $1\leq T \leq 100$，$1 \leq x, y \leq 10^{18}$。

题目分析

解题思路

1. 首先，我们需要理解题目的核心要求：

   • 两个玩家：Farmer John和Bessie
   • 初始时各自有一定数量的石头
   • 游戏规则：
     • 轮流操作，Farmer John先手
     • 如果石头数小于对方：从堆中拿1块
     • 如果石头数不小于对方：扔掉一半（向下取整）
     • 当一方石头数为0时游戏结束

2. 解题思路：

   • 输入处理：
     • 读取测试用例数量T
     • 每组测试用例包含两个数x,y（分别是Farmer John和Bessie的初始石头数）
   • 游戏模拟：
     • 使用循环模拟游戏过程
     • 用布尔变量标记当前回合的玩家
     • 根据规则更新石头数量
     • 直到有一方石头数为0
   • 输出结果：
     • 输出最终两人的石头数量
   • 注意：
     • 数据范围较大，需要使用long long类型
     • 需要处理多组测试数据

{% include custom/custom-post-content-inner.html %}

示例代码

#include <iostream>
using namespace std;
int main() {
    // 读取测试用例数量
    int T;
    cin >> T;
    // 循环处理每个测试用例
    for (int i = 0; i < T; i++) {
        // 读取初始石头数量
        long long x, y;
        cin >> x >> y;
        // 使用临时变量存储当前状态
        long long tmp_x = x;
        long long tmp_y = y;
        // is_f为true表示当前是Farmer John的回合
        bool is_f = true;
        // 当双方都还有石头时继续游戏
        while (tmp_x != 0 && tmp_y != 0) {
            if (is_f) {
                // Farmer John的回合
                if (tmp_x < tmp_y) {
                    // 如果石头少于对方，拿一块
                    tmp_x += 1;
                } else {
                    // 否则扔掉一半
                    tmp_x /= 2;
                }
            } else {
                // Bessie的回合
                if (tmp_y < tmp_x) {
                    // 如果石头少于对方，拿一块
                    tmp_y += 1;
                } else {
                    // 否则扔掉一半
                    tmp_y /= 2;
                }
            }
            // 切换回合
            is_f = !is_f;
        }
        // 输出最终结果
        cout << tmp_x << " " << tmp_y << endl;
    }
    return 0;
}

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号