問題
농부 존은 선 상에
초기에 일부 소는 감염되어 있습니다. 매일 밤 감염된 소는 그들의 왼쪽과 오른쪽에 있는 소들에게 전염병을 퍼뜨립니다 (존재한다면). 소가 감염되면 계속해서 감염된 상태를 유지합니다.
몇 번의 밤이 지난 후, 농부 존은 문제가 통제 불능으로 가고 있다는 것을 깨닫고 소들을 테스트하여 누가 전염병에 걸렸는지 확인하려고 합니다. 전염병이 시작된 소의 최소 수를 찾으세요.
入力
첫 번째 줄에는 농부 존이 가진 소의 수
다음 줄에는
出力
한 개의 정수를 출력하세요: 전염병이 시작된 소의 최소 수.
例題 #1
5
11111
1
가운데에 있는 소만이 초기에 감염되었다고 가정해 봅시다. 그런 경우 소들은 다음과 같은 순서로 감염될 것입니다:
0 밤: 00100 (세 번째 소가 초기에 감염됨)
1 밤: -> 01110 (두 번째와 네 번째 소가 이제 감염됨)
2 밤: -> 11111 (첫 번째와 다섯 번째 소가 이제 감염됨)
3 밤: -> 11111 (이미 모든 소가 감염되어 있으므로 추가로 감염되는 소는 없음)
-> ...
두 번 이상의 밤이 지난 후 소들의 최종 상태는 입력과 같을 것입니다. 이 입력 상태를 생성할 수 있는 다양한 초기 상태와 밤의 수가 있습니다. 예를 들어 다음과 같습니다:
0 밤: 10001
1 밤: -> 11011
2 밤: -> 11111
또는:
0 밤: 01001
1 밤: -> 11111
또는:
0 밤: 01000
1 밤: -> 11100
2 밤: -> 11110
3 밤: -> 11111
이러한 초기 상태 중에는 적어도 하나의 감염된 소가 포함되어 있습니다.
例題 #2
6
011101
4
입력 상태와 이 최종 상태를 생성할 수 있는 유일한 초기 상태 및 밤의 수는 모든 네 마리의 감염된 소가 초기에 전염병에 걸렸을 때입니다.
ログインしないとコードを書けません。