【例2.12 】糖果游戏

GitHub跳转原题关系图返回列表

本题要求模拟按固定顺序在环状数组上进行除法和加法更新操作。难点在于理解连续实时更新以及正确处理固定宽度且无额外分隔符的拼接输出格式。

OJ: roj

题目 ID: 5070

难度:入门

标签:模拟

创建: 2026-10-09 07:34

更新: 2026-10-09 07:34

形式化题目

有 55 个变量 c1,c2,c3,c4,c5c_1, c_2, c_3, c_4, c_5 分别代表 1 到 5 号小朋友的糖果数量,他们坐成一圈。因此 1 号相邻的是 5 号和 2 号,5 号相邻的是 4 号和 1 号。 按 1 到 5 号的顺序,对每个变量 xx(其左右相邻变量设为 L,RL, R)依次执行以下更新:

  1. 计算均分的三份:g=⌊x/3⌋g = \lfloor x / 3 \rfloor
  2. 多余的糖果立即被吃掉(即 x mod 3x \bmod 3 直接丢弃)。
  3. 自身保留一份,其余两份给相邻的人:x←gx \leftarrow g, L←L+gL \leftarrow L + g, R←R+gR \leftarrow R + g

操作完成后,要求按 5 位宽度依次输出这 5 个人的最终糖果数,各个数值之间直接拼接,不加任何额外的空格分隔符。

正解

思路

本题需要直接按照题目描述进行模拟。每个人将手里的糖果分成 33 份,自己留一份,分给左右邻居各一份。 核心逻辑在于:顺序与状态的实时更新。 从 1 号开始分配,1 号分完糖果后,2 号手里的糖果数必须包含 1 号刚分给他的那一份。由于是严格按顺序来的,后续小朋友的操作必须基于前面小朋友分配完毕后的最新数量进行计算。

以输入样例 8 9 10 11 12 为例:

  • 初始状态:[8, 9, 10, 11, 12]
  • 1 号操作:拥有 88 颗,分成 33 份每份 22 颗(吃掉 22 颗)。自己留 22 颗,给 5 号 22 颗,给 2 号 22 颗。 当前状态:[2, 11, 10, 11, 14]
  • 2 号操作:拥有 1111 颗,分成 33 份每份 33 颗(吃掉 22 颗)。自己留 33 颗,给 1 号 33 颗,给 3 号 33 颗。 当前状态:[5, 3, 13, 11, 14]
  • 3 号操作:拥有 1313 颗,分成 33 份每份 44 颗(吃掉 11 颗)。自己留 44 颗,给 2 号 44 颗,给 4 号 44 颗。 当前状态:[5, 7, 4, 15, 14]
  • 4 号操作:拥有 1515 颗,分成 33 份每份 55 颗(吃掉 00 颗)。自己留 55 颗,给 3 号 55 颗,给 5 号 55 颗。 当前状态:[5, 7, 9, 5, 19]
  • 5 号操作:拥有 1919 颗,分成 33 份每份 66 颗(吃掉 11 颗)。自己留 66 颗,给 4 号 66 颗,给 1 号 66 颗。 最终状态:[11, 7, 9, 11, 6]

结果与样例输出 11 7 9 11 6 相符。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-09 02:20
# update_at: 2026-10-09 07:23

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    # 5 个小朋友的初始糖果数,按 1..5 号顺序读入;缺输入时该项为 None,直接结束不猜值
    a = next(data, None)
    b = next(data, None)
    c = next(data, None)
    d = next(data, None)
    e = next(data, None)
    if None in (a, b, c, d, e):
        return

    # 严格按 1 -> 5 号的顺序模拟:轮到的人用的已是前面分给他的最新数量。
    # share = floor(c / 3) 是一份的量,余数 c % 3 被当场吃掉,不再出现。
    share = a // 3  # 1 号:留一份,另两份给 2 号、5 号
    a, b, e = share, b + share, e + share

    share = b // 3  # 2 号:留一份,另两份给 1 号、3 号
    b, a, c = share, a + share, c + share

    share = c // 3  # 3 号:留一份,另两份给 2 号、4 号
    c, b, d = share, b + share, d + share

    share = d // 3  # 4 号:留一份,另两份给 3 号、5 号
    d, c, e = share, c + share, e + share

    share = e // 3  # 5 号:留一份,另两份给 4 号、1 号
    e, d, a = share, d + share, a + share

    # 题面「按 5 位宽度输出」:每个数占 5 位右对齐,相邻数字之间无分隔符
    print(f"{a:5d}{b:5d}{c:5d}{d:5d}{e:5d}")


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-09 02:20
 * update_at: 2026-10-09 07:23
 */
#include <cstdio>

typedef long long ll;

// 5 个小朋友的糖果数,下标含义即编号 1..5 号,围成一圈:
// 1 号的邻居是 2 号和 5 号,5 号的邻居是 4 号和 1 号。
ll a, b, c, d, e;

// 严格按 1 -> 5 号的顺序依次操作:轮到某人时,他手里已经是前面的人分给他的
// 最新数量(不是本轮开始时的旧值);用 share 记 floor(手中糖果 / 3) 这一份,
// 余数 c % 3 无人接手,当场吃掉,故直接丢弃。
void solve() {
    ll share;

    // 1 号:留一份,另两份给 2 号、5 号
    share = a / 3;
    a = share;
    b += share;
    e += share;

    // 2 号:留一份,另两份给 1 号、3 号
    share = b / 3;
    b = share;
    a += share;
    c += share;

    // 3 号:留一份,另两份给 2 号、4 号
    share = c / 3;
    c = share;
    b += share;
    d += share;

    // 4 号:留一份,另两份给 3 号、5 号
    share = d / 3;
    d = share;
    c += share;
    e += share;

    // 5 号:留一份,另两份给 4 号、1 号
    share = e / 3;
    e = share;
    d += share;
    a += share;

    // 题面要求「按 5 位宽度输出」:%5lld 右对齐补空格,五个数之间不加任何分隔符
    printf("%5lld%5lld%5lld%5lld%5lld\n", a, b, c, d, e);
}

int main() {
    if (scanf("%lld %lld %lld %lld %lld", &a, &b, &c, &d, &e) != 5) {
        return 0;
    }

    solve();

    return 0;
}

复杂度

  • 时间复杂度:O(1)O(1),只有固定次数的算术运算。
  • 空间复杂度:O(1)O(1),只使用了 5 个变量用于状态保存与修改。

总结

  1. 核心算法:严格按 1…5 顺序模拟,每个人的操作为求 g = c[i]/3,自身更新为 c[i] = g,左右邻居 c[左] += g 和 c[右] += g,多余的 c[i]%3 自动吃掉。复杂度为 O(1)O(1)。
  2. 输出格式(极易错,★★★):题目要求按 5 位宽度输出(如 %5d 格式化),并且直接拼接无额外分隔符。
    • 所有 10 个数据点的输出字节数恒为 26 字节(5×5=255 \times 5 = 25 个字符,外加 \n)。
    • 在数据点 p2(全 10000)中,正确的五段是 13867、 9258、 9752、11028、 6090,其中 9752 和 11028 拼接后为 975211028,两者之间毫无分隔符。不要将其误认为是一个九位数 97521。
  3. 和守恒不变量(★★):p2 的最终和为 13867+9258+9752+11028+6090=4999513867 + 9258 + 9752 + 11028 + 6090 = 49995。这恰等于初始总量 5000050000 减去各轮吃掉的糖果数量和 55 颗,符合物理守恒定律,可作为非常强力的不变量验证手段。
  4. 圆桌邻接规律(★):座位是首尾相连的圆桌,因此 1 号的邻居是 5 号和 2 号;5 号的邻居是 4 号和 1 号。
  5. 边界条件(★):
    • 数据点 p1 是全零,结果将是 5 个 0 附加分别的 4 个补齐空格,即总共 55 个 0 和 2020 个空格的输出组合,总计 2626 字节。
    • 数据点 p2 为全 10000,测试了边界上的最大取值和格式拼接的无缝衔接。
  6. 证据强度分层(★):
    • 「均分三份,多余吃掉,留一份」:有确切的题面支持,并且验证代码实现 10/10 与 std 完全一致(确证)。
    • 「%5d 拼接,无分隔符」:仅有题面说的「按 5 位宽度输出」+ 样例 p3 表现及数据文件内容共同支持得出,题面并无明确提示不要空格。
  7. 数据类型要求(★):初始值最大为 10000,全场最高总和为 50000。中间计算结果不可能超过这 5000050000 的总和,远小于 int 的极限范围。在此使用 long long 只是工程上的防患未然和一致性规范选择,并非本题正确性必需。
  8. T9 跨语言语义与易错点(★):
    • 整除取模:C++ / 与 Python // 对于负数的处理有分歧,但本题输入数据恒非负,故没有任何运行风险。
    • 溢出 / 类型转换 / 浮点格式化 / 排序字典序:均未涉及或无风险。
    • 易错提醒:若误用 printf("%5d ", x)(末尾多加空格)或者 Python print(..., sep=' ') 输出,会导致总长度越界和格式错乱,触发判定系统给出一堆错误点(具体错误点数 worker 报告未给出)。
  9. 反事实(V1)与其他验证实验:
    • 把邻接改成 (0,2)/(1,3)/…;把顺序改成 5→1;把 c[i] = g 改成 c[i] = 0(不留给自己);在输出串中多加空格:均会导致判题失败(具体失败点数 worker 报告未给出)。
    • V2、V6、V9、闸门对照组等更多实验现象,由于 worker 报告中未给出,不再赘述。