레이팅 미적용농부 존에게는 일렬로 늘어선 \(N\)마리의 소가 있다 (\(1 \leq N \leq 3\cdot 10^5\)). 안타깝게도 소들 사이에 병이 퍼지고 있다.
처음에 일부 소들이 감염된 상태로 시작한다. 매일 밤, 감염된 소는 자신의 왼쪽과 오른쪽에 있는 소(존재한다면)에게 병을 퍼뜨린다. 한 번 감염된 소는 계속 감염된 상태로 남는다.
며칠 밤이 지난 후, 농부 존은 상황이 통제 불능이 되었음을 깨닫고 소들을 검사하여 누가 병에 걸렸는지 알아냈다. 처음에 병을 가지고 시작했을 수 있는 소의 최소 마릿수를 구하라.
문제 제공: Suhas Nagar
채점 방식
- 입력 3-7: \(N \le 1000\)
- 입력 8-12: 추가 제약 조건 없음.
문제 제공: Suhas Nagar
첫째 줄에 농부 존이 가진 소의 수 \(N\)이 주어진다.
다음 줄에 \(1\)과 \(0\)으로만 이루어진 길이 \(N\)의 비트 문자열이 주어진다. \(1\)은 며칠 밤이 지난 후 감염된 소를, \(0\)은 감염되지 않은 소를 나타낸다.
처음에 병을 가지고 시작했을 수 있는 소의 최소 마릿수를 하나의 정수로 출력한다.
5
111111Suppose the middle cow was the only cow to start off infected. Then the cows
would be infected in the following order:
0 nights: 00100 (the third cow is initially infected)
1 night: -> 01110 (the second and fourth cows are now infected)
2 nights: -> 11111 (the first and fifth cows are now infected)
3 nights: -> 11111 (all cows already were infected, so no additional cows are infected)
-> ...
After two or more nights, the final state of the cows would look like the input.
There are many other initial states and number of nights that could have
produced the input state, such as:
0 nights: 10001
1 night: -> 11011
2 nights: -> 11111
or:
0 nights: 01001
1 night: -> 11111
or:
0 nights: 01000
1 night: -> 11100
2 nights: -> 11110
3 nights: -> 11111
All of these initial states contain at least one infected cow.
6
0111014The only initial state and number of nights that could have led to this final
state is if no nights have passed and each of the four infected cows in the
input started off with the sickness.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > December > Bronze