【例2.6】鸡兔同笼

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

经典的鸡兔同笼问题,通过解二元一次方程组求出鸡和兔的数量,复杂度 $O(1)$。

OJ: roj

题目 ID: 5069

难度:入门

标签:数学

创建: 2026-10-09 02:04

更新: 2026-10-09 02:04

形式化题目

已知笼中鸡和兔的头总数为 xx,脚总数为 yy。 求鸡的数量 cc 和兔的数量 rr 各是多少。

输入包含两个非负整数 xx 和 yy。 输出鸡的数量和兔的数量,中间用一个空格隔开,且末尾有换行、无行末空格。

正解

思路

设鸡的数量为 cc,兔的数量为 rr。 根据题意,可以列出如下二元一次方程组:

{c+r=x2c+4r=y \begin{cases} c + r = x \\ 2c + 4r = y \end{cases}
将第一个方程两边同乘以 44,得到 4c+4r=4x4c + 4r = 4x,减去第二个方程,可得:
2c=4x−y  ⟹  c=4x−y2 2c = 4x - y \implies c = \frac{4x - y}{2}
同理,将第一个方程两边同乘以 22,得到 2c+2r=2x2c + 2r = 2x,用第二个方程减去它,可得:
2r=y−2x  ⟹  r=y−2x2 2r = y - 2x \implies r = \frac{y - 2x}{2}

题目要求按“鸡 兔”的顺序输出,因此分别输出 cc 和 rr 即可。

代码

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:01
# update_at: 2026-10-09 02:01

import sys


def solve() -> None:
    """读入头数 x、脚数 y,按「鸡 兔」顺序输出各自数量(与 C++ 侧同一公式)。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    x = next(data, None)  # 头的数量;无输入则静默退出,与 C++ 侧 cin 失败的行为一致
    if x is None:
        return
    y = next(data, None)
    if y is None:
        return
    chicken = (4 * x - y) // 2  # 鸡:每只 2 只脚
    rabbit = (y - 2 * x) // 2   # 兔:每只 4 只脚
    print(chicken, rabbit)


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:01
 * update_at: 2026-10-09 02:01
 */
// 一本通 2068《【例2.6】鸡兔同笼》
// 题面三步判据(关键词 / 括号内算法名 / 标题)全空 ⇒ 未指定实现手段,直接用代数公式。
// 设鸡 c 只、兔 r 只:c + r = x,2c + 4r = y ⇒ c = (4x - y) / 2,r = (y - 2x) / 2。
// 【输出顺序】鸡在前、兔在后,由数据判定:
//   p1 (1 2) -> "1 0"、p2 (1 4) -> "0 1",两点即可判别顺序(0 是合法输出)。
// 数据实测:10 个点全部满足 2x <= y <= 4x 且 y 为偶数,两个分子都是非负偶数,整除无歧义;
// 无解输入(y 为奇 / y < 2x / y > 4x)题面未定义,故不加特判、按公式直算。
// 范围:数据最大 x = y/2 = 10^6 ⇒ 中间量 4x <= 4 * 10^6 << 2^31 - 1;
// 仍按规范统一用 ll,避免任何隐含的 32 位假设。
#include <iostream>

using namespace std;

typedef long long ll;

ll x; // 头的数量
ll y; // 脚的数量

// 由方程组解出鸡、兔数量并按「鸡 兔」顺序输出。
void solve() {
    ll chicken = (4 * x - y) / 2; // 鸡:每只 2 只脚
    ll rabbit = (y - 2 * x) / 2;  // 兔:每只 4 只脚
    cout << chicken << " " << rabbit << "\n";
}

int main() {
    if (!(cin >> x >> y)) return 0; // 无输入 / 非法 token:静默退出
    solve();
    return 0;
}

复杂度

  • 时间复杂度:O(1)O(1),只需常数次算术运算。
  • 空间复杂度:O(1)O(1),只需常数个变量存储输入和结果。

总结

  1. 核心算法与输出顺序:通过数学公式推导得出 鸡 =4x−y2= \frac{4x-y}{2}、兔 =y−2x2= \frac{y-2x}{2},时间复杂度 O(1)O(1)。反事实测试 (V1) 将输出对调后 10/10 全失败;两候选探测 (V8) 鸡在前 0 失败,兔在前 10 失败。输出顺序“鸡在前、兔在后”被数据唯一确定。
  2. 边界覆盖(数据设计亮点):数据设计极其严谨,完美覆盖了合法区间 2x≤y≤4x2x \le y \le 4x 的两个端点:
    • p9(x=1000000,y=2000000  ⟹  y=2xx=1000000, y=2000000 \implies y=2x):输出 1000000 0,即全是鸡。
    • p10(x=1000000,y=4000000  ⟹  y=4xx=1000000, y=4000000 \implies y=4x):输出 0 1000000,即全是兔。 并且 0 是合法输出(真实数据中共出现 4 处 0)。
  3. 跨语言语义一致性分歧(精确刻画):
    • 当遇到“无解”情形时,公式会产生负数分子且伴随奇数。C++ 的 / 运算向零取整,而 Python 的 // 向下取整。
    • 分歧集合被精确刻画为:{y 为奇}∩{y<2x∨y>4x}\{y \text{ 为奇}\} \cap \{y < 2x \vee y > 4x\}。在 0..100×0..4000..100 \times 0..400 穷举中,共有 15150/40501 组发生分歧。
    • 机制与特例:C++ trunc(-5/2) = -2 vs Python floor(-5/2) = -3;然而对于 1 3 这种全正奇数的情形,两者皆得 0,并不分歧。与“仅负分子才分歧”的机制高度一致。
    • 最小复现:
      bash
      printf '10 15' | ./main            # 12 -2
      printf '10 15' | python3 main.py   # 12 -3
    • 由于本题 10 个测试点全落在合法区间内,未覆盖该类无解数据(题面亦未定义无解输出),故按题意保持公式直算,不加特判。
  4. 数据类型的两层次分析:本题中最大值 x=106x=10^6,推导中间值 4x=4×106≪INT_MAX4x = 4 \times 10^6 \ll \text{INT\_MAX},在数据内使用 int 不会溢出,此时 long long 是项目规范选择。而在离数据测试中(如 x=6×108x=6\times 10^8),旧 int 版触发了 UBSan signed integer overflow,long long 表现正常,即在数据外承重。
  5. 探针有效性 (V9):C++ 版的 stderr 干净无输出,对照组强制将 INT_MIN 取反确实触发了 runtime error,证实了探针监测的有效性。
  6. 验证强度与硬编码检查:
    • 枚举验证(V6):穷举 4050140501 组数据,其中有解的 51515151 组与“鸡由 00 遍历到 xx”的异源算法 0 分歧。
    • 真实数据二进制复核(400组)完全匹配。
    • 非硬编码(V2):代码字面量集合为 {0,2,4} 及 {2,4},答案值一次均未出现,且将除以 2 改为 3 会导致 10/10 测试点全失败,逻辑坚固。
  7. 输出格式:鸡与兔的数量通过单空格分隔,无行尾空格,有换行符。