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】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

美国AI奥赛首次新增低龄组！2027 USAAIO报名中，2月正式开考！

不考编程实操？2026 CAICP人工智能能力认证首轮11月22日开考，备考指南速递！