레이팅 미적용소 베시는 최근 대면 수업으로 돌아오게 되어 신이 났다! 안타깝게도 강사인 농부 존의 강의가 너무 지루해서, 베시는 수업 중에 자주 잠들어 버린다.
농부 존은 베시가 수업에 집중하지 않는다는 것을 눈치챘다. 그는 같은 수업의 다른 학생인 엘시에게 각 수업에서 베시가 잠든 횟수를 기록해 달라고 부탁했다. 수업은 \(N\)교시(\(2\le N\le 10^5\))가 있고, 엘시는 \(i\)번째 수업에서 베시가 \(a_i\)번(\(1\le a_i\le 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]\) 중 하나가 될 수 있다.
베시가 가장 싫어하는 수의 후보 \(q_1,\ldots,q_Q\) (\(1\le Q\le 10^5\), \(1\le q_i\le 10^{18}\))가 주어질 때, 각 후보에 대해 기록의 모든 수가 같아지도록 만들기 위해 엘시가 수행해야 하는 최소 수정 횟수를 계산하는 것을 도와주어라.
Problem credits: Jesse Choe and Benjamin Qi
채점 방식
- 테스트 케이스 2-4에서는 \(N,Q\le 5000\)이다.
- 테스트 케이스 5-7에서는 모든 \(a_i\)가 최대 \(10^9\)이다.
- 테스트 케이스 8-26은 추가 제약이 없다.
Problem credits: Jesse Choe and Benjamin Qi
각 테스트 케이스의 첫째 줄에 \(N\)이 주어지고, 둘째 줄에 \(a_1,a_2,\ldots,a_N\)이 주어진다. 셋째 줄에 \(Q\)가 주어지고, 이어지는 \(Q\)개의 줄에는 베시가 가장 싫어하는 수의 후보인 정수 \(q_i\)가 한 줄에 하나씩 주어진다.
각 \(q_i\)에 대해, 엘시가 기록의 모든 항목을 \(q_i\)로 바꾸는 데 필요한 최소 수정 횟수를 계산하여 출력한다. 불가능하면 \(-1\)을 출력한다.
6
1 2 3 1 1 4
7
1
2
3
4
5
6
126
6
4
5
-1
4
5Elsie 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\).
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > February > Platinum