USACO 2020 Jan Bronze P2

USACO analysis

---

yff | 18 Dec 2020

报告错误

如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：

1. 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
2. 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库

Link to the Problem

Problem Description

Sequence $a$ contains numbers from 1 to $N$ ($2 ≤ N ≤ 10^3$) in no order, and sequence $b$ contains $N-1$ numbers that satisfied $b_i = a_i + a_{i + 1}$. Given sequence $b$, find the “minimum” sequence $a$

Proposed Solution

If we know the first number of sequence $a$, we can construct the whole sequence with sequence $b$. Therefore we will try to guess the first number from 1 to $N$

Time Complexity Analysis

Guessing the first number of sequence $a$ and constructing the whole sequence $a$ both have a time complexity of $O(N)$, so the total time complexity is $O(N^2)$

Code

def valid(start):
	global bcows
	visited = set()
	acows = [start]
	for i in range(len(bcows)):
		next = bcows[i] - acows[i]
		if next in visited: return False, acows
		visited.add(next)
		acows.append(next)
	return True, acows
		
lines = open('photo.in').read().strip().split('\n')
n, bcows = int(lines[0]), list(map(int, lines[1].split(' ')))

result = ''
for i in range(1, n + 1):
	test = valid(i)
	if test[0]: 
		acows = test[1]
		for acow in acows: result += str(acow) + ' '
		break

print(result)
file = open('photo.out', 'w')
file.write(result.strip())
file.close()

评论区