레이팅 미적용베시는 초기 HP가 목록 \(v_1\dots v_N\) (\(1\le N\le 2\cdot 10^5, 0\le v_i\le 10^9\))으로 주어지는 일렬로 늘어선 \(N\)명의 적을 물리쳐야 하는 비디오 게임을 하고 있다. 한 번의 공격에서 그녀는 다음 단계들을 수행할 수 있다.
- \(i\)번째 적이 아직 살아 있는 (즉, \(v_i>0\)인) \(i\)를 선택한다.
- \(i\)번째 적과 그에 인접한 살아 있는 모든 적에게 피해를 1씩 준다. 구체적으로, 각 \(j\in [\max(i-1, 1), \min(i+1, N)]\)에 대해 \(v_j>0\)이면 \(v_j\)에서 1을 뺀다.
베시가 모든 적을 물리치기 위해 (즉, 모든 \(v_i\)를 0으로 만들기 위해) 필요한 최소 공격 횟수를 구하는 것을 도와주자.
추가로 매개변수 \(M\) (\(0\le M\le 2\))이 주어진다. \(M>0\)이면, 최소 공격 횟수를 달성하면서 런의 수가 적은 구성을 출력해야 한다. 여기서 런이란 같은 적을 연속해서 공격하는 것을 말한다.
구성에서의 런의 수를 \(R\)라 하자. 구성은 다음 형식이어야 한다: \(R\)을 한 줄에 출력한 뒤, 각각 두 정수 \(i\)와 \(r\) (\(1\le i\le N, 0\le r\le 10^9\))을 담은 \(R\)개의 줄을 출력한다. 이는 베시가 \(i\)번째 적을 연속으로 \(r\)번 공격한다는 의미이다.
\(M\)의 값에 따라 \(R\)는 다음 제약 중 하나를 만족해야 한다.
- \(M=1\): \(R\le 2N\) (구성이 항상 존재함을 증명할 수 있다).
- \(M=2\): \(R\le f(N)\), 여기서 \(f(N)\)은 길이 \(N\)의 모든 목록에 대한 최소 런 수의 최댓값이다.
문제 제공: Benjamin Qi
채점 방식
- 입력 4-7: \(M=0\)
- 입력 8-11: \(M=1\)
- 입력 12-13: \(M=2\)
문제 제공: Benjamin Qi
각 입력은 \(T\) (\(1\le T\le 10^5\))개의 독립적인 테스트로 구성된다. 첫째 줄에 \(T\)와 \(M\)이 주어진다.
각 테스트는 다음과 같이 주어진다.
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 \(v_1\dots v_N\)이 주어진다.
모든 테스트에 대한 \(N\)의 합은 \(10^6\)을 넘지 않음이 보장된다.
각 테스트마다 첫째 줄에 최소 공격 횟수를 출력한다.
그런 다음 \(M>0\)이면 위에서 설명한 대로 \(R+1\)개의 줄을 추가로 출력한다. 유효한 구성이라면 무엇이든 정답으로 인정된다.
2 0
1
10
3
6 1 710
12For the second test, you can first perform one attack on the middle enemy. Then,
in any order after that, perform five attacks on the first enemy and six attacks
on the last enemy.
2 1
1
10
3
6 1 710
2
1 0
1 10
12
4
2 1
1 5
3 2
3 4This output receives credit because \(R=2\le 2\) for test 1 and \(R=4\le 6\) for test 2.
2 2
1
10
3
6 1 710
1
1 10
12
3
2 1
3 6
1 5This output receives credit because \(R=1\le f(1)\) for test 1 and \(R=3\le f(3)\)
for test 2.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Third Contest > Platinum