레이팅 미적용끔찍한 신종 질병 COWVID-19가 전 세계 소들 사이에 퍼지기 시작했다. 농부 존은 자신의 소 떼를 감염으로부터 보호하기 위해 가능한 한 많은 예방 조치를 취하려고 한다.
농부 존의 헛간은 \(N\)개의 축사(\(2 \leq N \leq 10^5\))가 한 줄로 늘어선 길고 좁은 건물이다. 이 축사들 중 일부에는 현재 소가 있고, 일부는 비어 있다. "사회적 거리두기"의 중요성에 대해 읽은 농부 존은 \(D\)를 최대화하고 싶다. 여기서 \(D\)는 소가 있는 축사들 중 가장 가까운 두 축사 사이의 거리이다. 예를 들어 소가 있는 축사 중 3번과 8번이 가장 가깝다면 \(D = 5\)이다.
최근 새 소 두 마리가 농부 존의 소 떼에 합류했고, 그는 원래 비어 있던 축사들 중 어디에 이들을 배정할지 결정해야 한다. 새 소 두 마리를 배치한 후의 \(D\) 값이 여전히 최대한 크도록 하려면 어떻게 배치해야 하는지 구하시오. 농부 존은 기존의 소들을 옮길 수 없으며, 새 소들에게 축사를 배정하기만 하려 한다.
문제 제공: Brian Dean
배점
- 테스트 케이스 2-6은 \(N\le 10\)을 만족한다.
- 테스트 케이스 7-8은 \(N\le 100\)을 만족한다.
- 테스트 케이스 9-11은 \(N \le 5000\)을 만족한다.
- 테스트 케이스 12-15는 추가 제약이 없다.
문제 제공: Brian Dean
입력의 첫째 줄에 \(N\)이 주어진다. 다음 줄에 헛간의 축사 배열을 나타내는, 0과 1로 이루어진 길이 \(N\)의 문자열이 주어진다. 0은 빈 축사를, 1은 소가 있는 축사를 나타낸다. 문자열에는 0이 두 개 이상 있으므로, 적어도 새 소 두 마리를 위한 공간은 있다.
농부 존이 새 소 두 마리를 최적으로 배치한 후 얻을 수 있는 \(D\)(소가 있는 두 축사 사이의 가장 가까운 거리)의 최댓값을 출력한다.
socdist1.in · 출력을 쓸 파일 socdist1.out14
100010010000102In this example, Farmer John could add cows to make the occupancy string look
like 10x010010x0010, where x's indicate the new cows. In this case \(D = 2\). It
is impossible to add the new cows to achieve any higher value of \(D\).
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > US Open > Bronze