USACO 2022 February Contest, Platinum

Problem 2. Sleeping in Class


Contest has ended.

Log in to allow submissions in analysis mode


Bessie the cow was excited to recently return to in-person learning! Unfortunately, her instructor, Farmer John, is a very boring lecturer, and so she ends up falling asleep in class often.

Farmer John has noticed that Bessie has not been paying attention in class. He has asked another student in class, Elsie, to keep track of the number of times Bessie falls asleep in a given class. There are $N$ class periods ($2\le N\le 10^5$), and Elsie logs that Bessie fell asleep $a_i$ times ($1\le a_i\le 10^{18}$) in the $i$-th class period. The total number of times Bessie fell asleep across all class periods is at most $10^{18}$.

Elsie, feeling very competitive with Bessie, wants to make Farmer John feel like Bessie is consistently falling asleep the same number of times in every class -- making it appear that the issue is entirely Bessie's fault, with no dependence on Farmer John's sometimes-boring lectures.

The only ways Elsie may modify the log are by combining two adjacent class periods or splitting a class period into two. For example, if $a=[1,2,3,4,5],$ then if Elsie combines the second and third class periods the log will become $[1,5,4,5]$. If Elsie then chooses to split the third class period into two, the log can become any of $[1,5,0,4,5]$, $[1,5,1,3,5]$, $[1,5,2,2,5]$, $[1,5,3,1,5]$, or $[1,5,4,0,5]$.

Given $Q$ ($1\le Q\le 10^5$) candidates $q_1,\ldots,q_Q$ for Bessie's least favorite number ($1\le q_i\le 10^{18}$), for each of them help Elsie compute the minimum number of modifications to the log that she needs to perform so that all the numbers in the log become the same.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of each test case contains $N$, and the second contains $a_1,a_2,\ldots,a_N$. The third contains $Q$, followed by $Q$ lines each containing an integer $q_i$, a candidate for Bessie's least favorite number.

OUTPUT FORMAT (print output to the terminal / stdout):

For each $q_i$, compute the minimum number of modifications required for Elsie to convert every entry of the log into $q_i$, or $-1$ if it is impossible.

SAMPLE INPUT:

6
1 2 3 1 1 4
7
1
2
3
4
5
6
12

SAMPLE OUTPUT:

6
6
4
5
-1
4
5

Elsie needs at least four modifications to convert the log into all 3s. 

   1 2 3 1 1 4
-> 3 3 1 1 4
-> 3 3 1 5
-> 3 3 6
-> 3 3 3 3

It is impossible for Elsie to convert the log into all 5s, which is why the correct output for that candidate is $-1$.

SCORING:

  • In test cases 2-4, $N,Q\le 5000$
  • In test cases 5-7, all $a_i$ are at most $10^9$.
  • Test cases 8-26 satisfy no additional constraints.

Problem credits: Jesse Choe and Benjamin Qi

Contest has ended. No further submissions allowed.