Home » 國際競賽 » Details

USACO 2020 January Contest, Bronze Problem 2. Photoshoot

Category: 國際競賽, 計算機國際競賽 Date: 2022年7月1日下午5:06

USACO 2020 January Contest, Bronze Problem 2. Photoshoot

Farmer John is lining up his? $N$ ?cows ( $2 \leq N \leq 10^{3}$ ), numbered? $1 \dots N$ , for a photoshoot. FJ initially planned for the? $i$ -th cow from the left to be the cow numbered? $a_{i},$ ?and wrote down the permutation? $a_{1}, a_{2}, \dots, a_{N}$ ?on a sheet of paper. Unfortunately, that paper was recently stolen by Farmer Nhoj!

Luckily, it might still be possible for FJ to recover the permutation that he originally wrote down. Before the sheet was stolen, Bessie recorded the sequence? $b_{1}, b_{2}, \dots, b_{N - 1}$ ?that satisfies? $b_{i} = a_{i} + a_{i + 1}$ ?for each? $1 \leq i < N .$

Based on Bessie's information, help FJ restore the "lexicographically minimum" permutation? $a$ ?that could have produced? $b$ . A permutation? $x$ ?is lexicographically smaller than a permutation? $y$ ?if for some? $j$ ,? $x_{i} = y_{i}$ ?for all? $i < j$ ?and? $x_{j} < y_{j}$ ?(in other words, the two permutations are identical up to a certain point, at which? $x$ ?is smaller than? $y$ ). It is guaranteed that at least one such? $a$ ?exists.

SCORING:

Test cases 2-4 satisfy? $N \leq 8.$
Test cases 5-10 satisfy no additional constraints.

INPUT FORMAT (file photo.in):

The first line of input contains a single integer? $N .$ The second line contains? $N - 1$ ?space-separated integers? $b_{1}, b_{2}, \dots, b_{N - 1} .$

OUTPUT FORMAT (file photo.out):

A single line with? $N$ ?space-separated integers? $a_{1}, a_{2}, \dots, a_{N} .$

SAMPLE INPUT:

5
4 6 7 6

SAMPLE OUTPUT:

3 1 5 2 4

$a$ ?produces? $b$ ?because? $3 + 1 = 4$ ,? $1 + 5 = 6$ ,? $5 + 2 = 7$ , and? $2 + 4 = 6.$

Problem credits: Benjamin Qi and Chris Zhang

USACO 2020 January Contest, Bronze Problem 2. Photoshoot 題解(翰林國際教育提供，僅供參考)

題解請注冊或登錄查看

[/hide]

(Analysis by Benjamin Qi)

For each? $i$ ?from? $1$ ?to? $N,$ ?try setting? $a_{1} = i .$ ?Then we can determine the rest of the elements of? $a$ ?by setting? $a_{i} = b_{i - 1} - a_{i - 1}$ ?for each? $2 \leq i \leq N .$ ?If this indeed produces a valid permutation (all elements of? $a$ ?are in? $[1, N]$ ?and none repeat), then return the result. This runs in? $O (N^{2})$ ?time.

Dhruv Rohatgi's code:

#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int b[100000], d[100000], ans[100000];
bool used[100000];
 
int main() {
	freopen("photo.in","r",stdin);
	freopen("photo.out","w",stdout);
	cin >> N;
	for(int i=0;i<N-1;i++)
		cin >> b[i];
	for(int i=2;i<N;i++)
		d[i] = b[i-1]-b[i-2];
	for(int a=1;a<=N;a++)
	{
		ans[0] = a, ans[1] = b[0] - a;
		for(int i=2;i<N;i++)
			ans[i] = ans[i-2] + d[i];
		for(int i=1;i<=N;i++)
			used[i] = 0;
		bool bad = 0;
		for(int i=0;i<N;i++)
		{
			if(used[ans[i]] || ans[i] <= 0 || ans[i] > N)
			{
				bad = 1;
				break;
			}
			used[ans[i]] = 1;
		}
		if(!bad)
		{
			for(int i=0;i<N;i++)
			{
				cout << ans[i];
				if(i<N-1) cout << ' ';
			}
			cout << '\n';
			return 0;
		}
	}
}

Bonus: Solve the problem in? $O (N) .$

[/hide]