Home » 国际竞赛 » Details

USACO 2021 US Open, Silver Problem 2. Do You Know Your ABCs?

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日上午11:52

USACO 2021 US Open, Silver Problem 2. 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$ ( $1 \leq 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 tells Bessie $N$ ( $4 \leq N \leq 7$ ) distinct integers $x_{1}, x_{2}, \dots, x_{N}$ ( $1 \leq x_{i} \leq 10^{9}$ ), claiming that each $x_{i}$ is one of $A$ , $B$ , $C$ , $A + B$ , $B + C$ , $C + A$ , or $A + B + C$ . However, Elsie may be lying; the integers $x_{i}$ might not correspond to any valid triple $(A, B, C)$ .

This is too hard for Bessie to wrap her head around, so it is up to you to determine the number of triples $(A, B, C)$ that are consistent with the numbers Elsie presented (possibly zero).

Each input file will contain $T$ ( $1 \leq T \leq 100$ ) test cases that should be solved independently.

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

The first input line contains $T$ .Each test case starts with $N$ , the number of integers Elsie gives to Bessie.

The second line of each test case contains $N$ distinct integers $x_{1}, x_{2}, \dots, x_{N}$ .

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

For each test case, output the number of triples $(A, B, C)$ that are consistent with the numbers Elsie presented.

SAMPLE INPUT:

10
7
1 2 3 4 5 6 7
4
4 5 7 8
4
4 5 7 9
4
4 5 7 10
4
4 5 7 11
4
4 5 7 12
4
4 5 7 13
4
4 5 7 14
4
4 5 7 15
4
4 5 7 16

SAMPLE OUTPUT:

For $x = {4, 5, 7, 9}$ , the five possible triples are as follows:

(2, 2, 5), (2, 3, 4), (2, 4, 5), (3, 4, 5), (4, 5, 7) .

SCORING:

In test cases 1-4, all $x_{i}$ are at most $50$ .
Test cases 5-6 satisfy $N = 7$ .
Test cases 7-15 satisfy no additional constraints.

Problem credits: Benjamin Qi

USACO 2021 US Open, Silver Problem 2. Do You Know Your ABCs? 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Consider the list $x$ for a single test case.

Solution 1: Solve $\frac{7!}{(7 - N)!}$ distinct linear systems using Gaussian elimination. But of course, Silver contestants are not expected to know how to do this.

Solution 2: Add $0$ to $x$ , so $x$ now contains between $5$ and $8$ elements inclusive. Suppose that $x$ is compatible with a triple $(A, B, C)$ . Then consider the following pairs of integers:

$(0, A)$
$(B, A + B)$
$(C, A + C)$
$(B + C, A + B + C)$

Since the size of $x$ is greater than $4$ , $x$ must contain two elements from the same pair, implying that there exist two elements of $x$ such that their difference equals $A$ . Similar reasoning holds for $B$ and $C$ .

So it suffices to iterate through all possibilities for $A$ , $B$ , and $C$ and increment the answer whenever we come across a candidate triple that works.

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class DoYouKnowYourABCsCounting {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        int t = Integer.parseInt(in.readLine());
        for (int tc = 1; tc <= t; tc++) {
            int n = Integer.parseInt(in.readLine());
            int[] numbers = new int[n];
            StringTokenizer tokenizer = new StringTokenizer(in.readLine());
            for (int j = 0; j < n; j++) {
                numbers[j] = Integer.parseInt(tokenizer.nextToken());
            }
            int answer = 0;
            Set<Integer> expanded = new HashSet<>();
            for (int x : numbers) {
                expanded.add(x);
                for (int y : numbers) {
                    if (x < y) {
                        expanded.add(y - x);
                    }
                }
            }
 
            for (int a : expanded) {
                for (int b : expanded) {
                    for (int c : expanded) {
                        if (a <= b && b <= c) {
                            List<Integer> allNumbers = Arrays.asList(a, b, c, a + b, b + c, c + a, a + b + c);
                            boolean works = true;
                            for (int x : numbers) {
                                if (!allNumbers.contains(x)) {
                                    works = false;
                                }
                            }
                            if (works) {
                                answer++;
                            }
                        }
                    }
                }
            }
            out.append(answer).append('\n');
        }
        System.out.print(out);
    }
}

Solution 3: There exist two elements of $x$ such that their sum equals $A + B + C$ (by similar reasoning as solution 2). Given the sum, we only need to check two candidate solutions.

My code:

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> x;
set<multiset<int>> sols;

void check_sol(int sum, int b, int c) {
	int a = sum-b-c;
	assert(a > 0 && b > 0 && c > 0);
	set<int> s{0,a,b,c,a+b,b+c,c+a,a+b+c};
	for (int t: x) if (!s.count(t)) return;
	sols.insert({a,b,c});
}
 
void test(int sum) {
	set<int> candidates;
	for (int t: x) {
		if (t > sum) return;
		if (t == 0 || t == sum) continue;
		candidates.insert(min(t,sum-t));
	}
	assert(candidates.size() >= 2);
	int a = *begin(candidates);
	int b = *next(begin(candidates));
	check_sol(sum,a,b);
	check_sol(sum,a,sum-b);
}
 
int solve() {
	cin >> N; 
	x.resize(N); for (int& t : x) cin >> t;
	x.push_back(0);

	sols.clear();
	for (int i = 0; i < (int)x.size(); ++i)
		for (int j = i+1; j < (int)x.size(); ++j)
			test(x[i]+x[j]);
	return (int)sols.size();
}
 
int main() {
	int T; cin >> T;
	while (T--) cout << solve() << "\n";
}

[/hide]