NOI Online 2021 入门组 T1

Description

题目描述

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

三个人的需求量分别为 \(a, b, c\)，现在请你帮他们切蛋糕，规则如下：

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

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

输入格式

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

第一行包含一个整数 \(T\)，表示数据组数。

接下来 \(T\) 行，每行包含三个整数 \(a, b, c\)，表示三人的需求量。

输出格式

输出 \(T\) 行，第 \(i\) 行的输出表示第 \(i\) 组数据中你至少需要切蛋糕的次数。

Solution

显然的，\(2\) 刀可以分出任意比例的蛋糕（\(a, b, c\) 的比例分别是 \(\dfrac{a}{a + b + c},\dfrac{b}{a + b + c},\dfrac{c}{a + b + c}\)），所以给 \(3\) 个人分蛋糕最多只需要 \(2 \times 3 = 6\) 刀。但注意，这 \(6\) 刀中有 \(3\) 刀必然是可以重合的，所以最多只需要 \(6 - 3 = 3\) 刀。

以下约定答案为 \(s\)。

现在来进行分类讨论：

首先将 \(a, b, c\) 排序，使 \(a \leq b \leq c\)。

• 如果 \(a = 0\)

  • 如果 \(b = 0\)，\(s = 0\)
  • 如果 \(b = c\)，\(s = 1\)
  • 否则 \(s = 2\)

• 如果 \(a \neq 0\)，说明 \(a, b, c\) 三值都是非零的

  • 如果 \(a + b = c\) 或 \(a = b\) 或 \(b = c\)，\(s = 2\)
  • 否则 \(s = 3\)

Code

#include 

void solve()
{
    int a[3];
    int answer;

    for (int i = 0; i < 3; i++)
    {
        scanf("%d", &a[i]);
    }

    std::sort(a, a + 3);

    if (a[0] == 0)
    {
        if (a[1] == 0) { answer = 0; }
        else
        {
            if (a[1] == a[2]) { answer = 1; }
            else { answer = 2; }
        }
    }
    else
    {
        if (a[0] + a[1] == a[2] || a[0] == a[1] || a[1] == a[2]) { answer = 2; }
        else { answer = 3; }
    }

    printf("%d\n", answer);

    return;
}

int main()
{
    int tests;

    scanf("%d", &tests);

    while (tests--)
    {
        solve();
    }

    return 0;
}

参考文献

• 洛谷博客：lzqy_
• 洛谷博客：子丑