经典的鸡兔同笼问题,通过解二元一次方程组求出鸡和兔的数量,复杂度 $O(1)$。
OJ: roj
题目 ID: 5069
难度:入门
标签:数学
创建: 2026-10-09 02:04
更新: 2026-10-09 02:04
形式化题目
已知笼中鸡和兔的头总数为
输入包含两个非负整数
正解
思路
设鸡的数量为
题目要求按“鸡 兔”的顺序输出,因此分别输出
代码
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;
}复杂度
- 时间复杂度:
,只需常数次算术运算。 - 空间复杂度:
,只需常数个变量存储输入和结果。
总结
- 核心算法与输出顺序:通过数学公式推导得出 鸡
、兔 ,时间复杂度 。反事实测试 ( V1) 将输出对调后 10/10 全失败;两候选探测 (V8) 鸡在前 0 失败,兔在前 10 失败。输出顺序“鸡在前、兔在后”被数据唯一确定。 - 边界覆盖(数据设计亮点):数据设计极其严谨,完美覆盖了合法区间
的两个端点: p9():输出 1000000 0,即全是鸡。p10():输出 0 1000000,即全是兔。 并且0是合法输出(真实数据中共出现 4 处 0)。
- 跨语言语义一致性分歧(精确刻画):
- 当遇到“无解”情形时,公式会产生负数分子且伴随奇数。C++ 的
/运算向零取整,而 Python 的//向下取整。 - 分歧集合被精确刻画为:
。在 穷举中,共有 15150/40501 组发生分歧。 - 机制与特例:C++
trunc(-5/2) = -2vs Pythonfloor(-5/2) = -3;然而对于1 3这种全正奇数的情形,两者皆得0,并不分歧。与“仅负分子才分歧”的机制高度一致。 - 最小复现:bash
printf '10 15' | ./main # 12 -2 printf '10 15' | python3 main.py # 12 -3 - 由于本题 10 个测试点全落在合法区间内,未覆盖该类无解数据(题面亦未定义无解输出),故按题意保持公式直算,不加特判。
- 当遇到“无解”情形时,公式会产生负数分子且伴随奇数。C++ 的
- 数据类型的两层次分析:本题中最大值
,推导中间值 ,在数据内使用 int不会溢出,此时long long是项目规范选择。而在离数据测试中(如),旧 int版触发了 UBSansigned integer overflow,long long表现正常,即在数据外承重。 - 探针有效性 (
V9):C++ 版的 stderr 干净无输出,对照组强制将INT_MIN取反确实触发了runtime error,证实了探针监测的有效性。 - 验证强度与硬编码检查:
- 枚举验证(
V6):穷举组数据,其中有解的 组与“鸡由 遍历到 ”的异源算法 0 分歧。 - 真实数据二进制复核(400组)完全匹配。
- 非硬编码(
V2):代码字面量集合为{0,2,4}及{2,4},答案值一次均未出现,且将除以2改为3会导致 10/10 测试点全失败,逻辑坚固。
- 枚举验证(
- 输出格式:鸡与兔的数量通过单空格分隔,无行尾空格,有换行符。