|
#2
rjsp2021-03-28 11:52
|
【题目描述】
Alice、Bob 和 Cindy 三个好朋友得到了一个圆形蛋糕，他们打算分享这个蛋糕。
三个人的需求量分别为 a,b,c，现在请你帮他们切蛋糕，规则如下：
1. 每次切蛋糕可以选择蛋糕的任意一条直径，并沿这条直径切一刀（注意切完后不
会立刻将蛋糕分成两部分）。
2. 设你一共切了 n 刀，那么你将得到 2n 个扇形的蛋糕（特别地，切了 0 刀被认为
是有一个扇形，即整个圆形蛋糕），将这些蛋糕分配给 Alice，Bob 和 Cindy，要
求每个扇形蛋糕只能完整地分给一个人。
3. 三人分到的蛋糕面积比需要为 a : b : c（不保证是最简比例，且如果 a,b,c 中某个
数为 0，表示那个人不吃蛋糕）。
为了完成这个任务，你至少需要切几刀？
【样例输入】
6
0 0 8
0 5 3
9 9 0
6 2 4
1 7 4
5 8 5
【样例输出】
0
2
1
2
3
2
【数据范围与提示】
30% 的数据满足：a = b = 0。
60% 的数据满足：a = 0。
100% 的数据满足：1 ≤ T ≤ 10 4 ，0 ≤ a,b,c ≤ 10 8 ，保证 a + b + c > 0。