Home » 国际竞赛 » Details

USACO 2020 December Contest, Bronze Problem 1. Do You Know Your ABCs?

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日下午3:40

USACO 2020 December Contest, Bronze Problem 1. Do You Know Your ABCs?

Farmer John's cows have been holding a daily online gathering on the "mooZ" video meeting platform. For fun, they have invented a simple number game to play during the meeting to keep themselves entertained.

Elsie has three positive integers $A$ , $B$ , and $C$ ( $A \leq B \leq C$ ). These integers are supposed to be secret, so she will not directly reveal them to her sister Bessie. Instead, she gives Bessie seven (not necessarily distinct) integers in the range $1 \dots 10^{9}$ , claiming that they are $A$ , $B$ , $C$ , $A + B$ , $B + C$ , $C + A$ , and $A + B + C$ in some order.

Given a list of these seven numbers, please help Bessie determine $A$ , $B$ , and $C$ . It can be shown that the answer is unique.

INPUT FORMAT (input arrives from the terminal / stdin):

The only line of input consists of seven space-separated integers.

OUTPUT FORMAT (print output to the terminal / stdout):

Print $A$ , $B$ , and $C$ separated by spaces.

SAMPLE INPUT:

2 2 11 4 9 7 9

SAMPLE OUTPUT:

2 2 7

SCORING:

Test cases 2-3 satisfy $C \leq 50$ .
Test cases 4-10 satisfy no additional constraints.

Problem credits: Benjamin Qi

USACO 2020 December Contest, Bronze Problem 1. Do You Know Your ABCs? 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Brian Dean and Benjamin Qi)

With some careful reasoning, we can deduce that the smallest two numbers must be $A$ and $B$ , and the largest must be $A + B + C$ . Subtracting the smallest two from the largest therefore gives us $C$ and we are done.

The only computational aspect of this problem therefore is locating the two smallest and the largest of the seven input numbers. One way to do this is by sorting the numbers, giving a very concise answer. E.g., in C++, this looks like:

#include <iostream>
#include <algorithm>
using namespace std;

int main(void)
{
  int nums[7];
  for (int i=0; i<7; i++) cin >> nums[i];
  sort (nums, nums+7);
  int a = nums[0], b = nums[1];
  int c = nums[6] - a - b;
  cout << a << " " << b << " " << c << "\n";
}

In Python, a similarly-concise solution might be:

nums = list(sorted(map(int,input().split())))
a,b = nums[0],nums[1]
c = nums[-1]-a-b
print(a,b,c)

Sorting isn't absolutely necessary here. One could also just scan the input to find the largest number, and then scan two more times to find the two smallest numbers (being careful to account for the possibility these might be the same value). Code for this is slightly longer but not too bad. Here's an example in C++:

#include <iostream>
using namespace std;

int main(void)
{
  int nums[7], A, B, C;
  for (int i=0; i<7; i++) cin >> nums[i];
  
  int largest = nums[0];
  for (int i=1; i<7; i++) 
    if (nums[i] > largest) largest = nums[i];

  int smallest = nums[0], count_smallest = 1;
  for (int i=1; i<7; i++) {
    if (nums[i] == smallest) count_smallest++;
    if (nums[i] < smallest) { smallest = nums[i]; count_smallest = 1; }
  }

  if (count_smallest > 1) {
    A = B = smallest;
    C = largest - A - B;
  } else {
    int second_smallest = nums[0];
    if (second_smallest == smallest) second_smallest = nums[1];
    for (int i=1; i<7; i++) 
      if (nums[i] < second_smallest && nums[i] != smallest) 
	second_smallest = nums[i]; 
    A = smallest;
    B = second_smallest;
    C = largest - A - B;
  }
  
  cout << A << " " << B << " " << C << "\n";
}

[/hide]