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]

以上就是关于【USACO 2020 January Contest, Bronze Problem 2. Photoshoot】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

耗时一年备考 USACO 却毫无收获？一文教你找准最佳备考起步时间！

2026 NOAI国际AI奥赛中国站即将开考！赛事地址&日程已出！