当前位置:首页 > 语法入门 > 分支结构 > 正文
洛谷P7471切蛋糕[2021NOIOnline]
48+

题目大意:一个圆柱形蛋糕分三份,要求比值是a:b:c,至少需要切几刀?(要求每刀都是直径)

题目描述

Alice、Bob 和 Cindy 三个好朋友得到了一个圆形蛋糕,他们打算分享这个蛋糕。

三个人的需求量分别为 ,现在请你帮他们切蛋糕,规则如下:

  1. 每次切蛋糕可以选择蛋糕的任意一条直径,并沿这条直径切一刀(注意切完后不会立刻将蛋糕分成两部分)。
  2. 设你一共切了 刀,那么你将得到 个扇形的蛋糕(特别地,切了 刀被认为是有一个扇形,即整个圆形蛋糕),将这些蛋糕分配给 Alice,Bob 和 Cindy,要求每个扇形蛋糕只能完整地分给一个人。
  3. 三人分到的蛋糕面积比需要为 (不保证是最简比例,且如果 中某个数为 ,表示那个人不吃蛋糕)。

为了完成这个任务,你至少需要切几刀?

输入格式

本题单个测试点包含多组数据。

第一行包含一个整数 ,表示数据组数。

接下来 行,每行包含三个整数 ,表示三人的需求量。

输出格式

输出 行,第 行的输出表示第 组数据中你至少需要切蛋糕的次数。

输入输出样例

输入 #1
6
0 0 8
0 5 3
9 9 0
6 2 4
1 7 4
5 8 5
输出 #1
0
2
1
2
3
2

说明/提示

样例 解释

数据范围与提示

的数据满足:

的数据满足:

的数据满足:,保证

解题思路

至多只需要3刀,分类讨论就行,不妨设A <= B <= C

不需要切:有两个是0,整个蛋糕给C即可。

切1刀:有一个是零,另外两个相等,第一刀切成两半即可。

切2刀:至少有一块是自定义大小的。有一个零只需2刀,因为切出B,剩下的是C;有两个数相等也只需要两刀,切出一个后,另一个就是对面那份;A+B==C也只需两刀,因为第一刀分一半,第二刀可以分出A和B。

切3刀:至少有两块是自定义大小的,第三块也自动确定大小了。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,

洛谷P7471切蛋糕[2021NOIOnline]:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter