#PU1187. USACO 2022 January Contest, Gold — Problem 3. Tests for Haybales
USACO 2022 January Contest, Gold — Problem 3. Tests for Haybales
USACO 2022 January Contest, Gold — Problem 3. Tests for Haybales
题目描述
Farmer John's cows have decided to offer a programming contest for the cows on Farmer Nhoj's farm. In order to make the problems as fun as possible, they have spent considerable time coming up with challenging input cases. For one problem in particular, "Haybales", the cows need your help devising challenging inputs. This involve solving the following somewhat intriguing problem: There is an array of sorted integers (), and an integer . You don't know the array or , but you do know for each index , the largest index such that . It is guaranteed that and . Given this information, Farmer John's cows need to construct any array along with some integer that matches that information. The construction needs to satisfy for all and . It can be proven that this is always possible. Help Farmer John's cows solve this problem!
输入格式
The first line of input contains . The next line contains .
输出格式
Print , then on separate lines. Any valid output will be accepted.
数据范围
For 50% of all inputs, For the remaining inputs, there are no additional constraints. Problem credits: Danny Mittal
样例
样例 1
6
2 2 4 5 6 6
6
1
6
17
22
27
32
The sample output is the array $a = [1, 6, 17, 22, 27, 32]$ with $K = 6$.
$j_1 = 2$ is satisfied because $a_2 = 6 \leq 1 + 6 = a_1 + K$ but
$a_3 = 17 > 1 + 6 = a_1 + K$, so $a_2$ is the largest element that is at most
$a_1$. Similarly,
$j_2 = 2$ is satisfied because $a_2 = 6 \leq 6 + 6$ but
$a_3 = 17 > 6 + 6$
$j_3 = 4$ is satisfied because
$a_4 = 22 \leq 17 + 6$ but $a_5 = 27 > 17 + 6$
$j_4 = 5$ is satisfied
because $a_5 = 27 \leq 22 + 6$ but $a_5 = 32 > 22 + 6$
$j_5 = 6$ is
satisfied because $a_6 = 32 \leq 27 + 6$ and $a_6$ is the last element of the
array
$j_6 = 6$ is satisfied because $a_6 = 32 \leq 32 + 6$ and $a_6$
is the last element of the array
This is not the only possible correct output for the sample input. For example,
you could instead output the array $[1, 2, 4, 5, 6, 7]$ with $K = 1$.