실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 1024 MB |
소 베시는 최근에 대면 학습에 다시 참여하게 되어 기뻤습니다! 불행히도, 그녀의 강사인 농부 존은 매우 지루한 강사이기 때문에, 그녀는 종종 수업 중에 자주 자게 됩니다.
농부 존은 베시가 수업에 집중하지 않는 것을 알아챘습니다. 그는 다른 학생 엘시에게 베시가 한 수업에서 몇 번이나 잠이 드는지 기록하도록 부탁했습니다. 총 2 이상 10^5 이하의 N 수업 기간이 있으며, 엘시는 i번째 수업 기간에 베시가 a_i 번 (1 이상 10^18 이하) 잠이 들었다고 기록합니다. 모든 수업 기간 동안 베시가 잠든 총 횟수는 최대 10^18입니다.
엘시는 베시와 매우 경쟁적이며, 베시가 모든 수업에서 항상 같은 횟수로 잠이 드는 것처럼 보이게 하여 농부 존에게 문제가 완전히 베시의 잘못이며, 농부 존의 가끔 지루한 강의와는 전혀 무관하다는 것을 느끼게 하고 싶어합니다.
엘시가 로그를 수정할 수 있는 유일한 방법은 두 개의 인접한 수업 기간을 결합하거나 수업 기간을 두 개로 분할하는 것입니다. 예를 들어, a=[1,2,3,4,5]라면, 엘시가 두 번째와 세 번째 수업 기간을 결합하면 로그는 [1,5,4,5]가 됩니다. 그러면 엘시는 세 번째 수업 기간을 두 개로 분할하기로 결정하면, 로그는 [1,5,0,4,5], [1,5,1,3,5], [1,5,2,2,5], [1,5,3,1,5], [1,5,4,0,5] 중 어느 것이든 될 수 있습니다.
1이상 10^5 이하의 Q개의 베시의 최소 좋아하는 수 후보 q_1,...,q_Q (1 이상 10^18 이하)가 주어졌을 때, 각각의 후보에 대해 엘시가 로그의 모든 숫자를 같게 만들기 위해 수행해야 하는 로그 수정의 최소 횟수를 계산해 주십시오.
각 테스트 케이스의 첫 번째 줄에는 N이 있고, 두 번째 줄에는 a_1, a_2, ..., a_N이 있습니다. 세 번째 줄에는 Q가 있고, 그 뒤에는 베시의 가장 싫어하는 수의 후보인 정수 q_i가 포함된 Q개의 줄이 있습니다.
각 q_i에 대해, 엘시가 모든 로그 항목을 q_i로 변환하기 위해 필요한 최소 수정 횟수를 계산하거나, 불가능한 경우 -1을 출력합니다.
6 1 2 3 1 1 4 7 1 2 3 4 5 6 12
6 6 4 5 -1 4 5
엘시는 모든 로그를 모두 3으로 변환하기 위해 최소 네 번의 수정이 필요합니다.
1 2 3 1 1 4
-> 3 3 1 1 4
-> 3 3 1 5
-> 3 3 6
-> 3 3 3 3
엘시가 모든 로그를 5로 변환하는 것은 불가능하므로, 그 후보에 대한 올바른 출력값은 -1입니다.
점수:
출처: USACO 2022 February Contest, Platinum Problem 2. Sleeping in Class