레이팅 미적용이른 아침, 농부 존은 나무가 부서지는 소리에 잠에서 깼다. 소들이었다. 소들이 또 헛간을 부수고 탈출하고 있었다!
농부 존은 소들의 아침 탈출에 진절머리가 났고, 더는 참을 수 없다고 결심했다. 이제 강경하게 나갈 때였다. 그는 마지막 탈출 이후 지난 날 수를 기록하는 계수기를 헛간 벽에 못으로 박아 두었다. 즉, 아침에 탈출이 일어났다면 그날 계수기는 \(0\)이 되고, 가장 최근의 탈출이 \(3\)일 전이었다면 계수기는 \(3\)을 가리킨다. 농부 존은 매일 꼼꼼하게 계수기 값을 기록했다.
연말이 되어 농부 존은 결산을 하려고 한다. 소들이 대가를 치르게 하겠다는 것이다! 그런데 기록에서 뭔가가 이상해 보인다...
농부 존은 기록을 시작한 이후 탈출이 몇 번 일어났는지 알아내고 싶다. 하지만 그는 소들이 자신의 기록을 조작했다고 의심하며, 확실히 아는 것은 자신이 탈출이 있었던 날에 기록을 시작했다는 것뿐이다. 기록을 시작한 이후 일어났을 수 있는 각 탈출 횟수에 대해, 조작되었어야 하는 기록 항목의 최소 개수를 구하도록 도와주자.
출제자: Brian Dean, Dhruv Rohatgi
출제자: Brian Dean, Dhruv Rohatgi
첫째 줄에 농부 존이 소 탈출 계수기를 기록하기 시작한 이후 지난 날 수를 나타내는 정수 \(N\)이 하나 주어진다 (\(1 \leq N \leq 100\)).
둘째 줄에 공백으로 구분된 정수 \(N\)개가 주어진다. \(i\)번째 정수는 음이 아닌 정수 \(a_i\)(\(100\) 이하)로, 소들이 그날의 기록 항목을 조작하지 않았다면 \(i\)일째에 계수기가 \(a_i\)였음을 뜻한다.
출력은 한 줄에 하나씩 \(N\)개의 정수로 이루어진다. \(i\)번째 정수는 탈출이 \(i\)번 일어난 모든 가능한 탈출 순서에 대해, 그 순서와 모순되는 기록 항목 개수의 최솟값이어야 한다.
taming.in · 출력을 쓸 파일 taming.out6
1 1 2 0 0 14
2
1
2
3
4If there was only 1 breakout, then the correct log would look like 0 1 2 3 4 5,
which is 4 entries different from the given log.
If there were 2 breakouts, then the correct log might look like 0 1 2 3 0 1,
which is 2 entries different from the given log. In this case, the breakouts
occurred on the first and fifth days.
If there were 3 breakouts, then the correct log might look like 0 1 2 0 0 1,
which is just 1 entry different from the given log. In this case, the breakouts
occurred on the first, fourth, and fifth days.
And so on.
riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > February > Gold