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]