레이팅 미적용소 베시는 차세대 히트 비디오 게임이 될 것이라 믿는 "성난 소들(Angry Cows)"을 설계했다. 베시가 완전히 독창적이라고 믿는 이 게임의 전제는, 플레이어가 새총으로 소를 쏘아 수직선 위 여러 지점에 놓인 건초 더미들로 이루어진 일차원 장면에 날려 보내는 것이다. 소는 건초 더미에 충분한 힘으로 착지하여 그 더미를 폭발시키고, 이는 근처의 다른 건초 더미들을 연쇄적으로 폭발시키는 반응을 일으킬 수 있다. 목표는 한 마리의 소로 연쇄 반응을 일으켜 가능한 한 많은 건초 더미를 폭발시키는 것이다.
수직선 위의 서로 다른 정수 위치 \(x_1, x_2, \ldots, x_N\)에 \(N\)개의 건초 더미가 있다. 소가 위치 \(x\)의 건초 더미에 발사되면, 이 더미는 "폭발 반경" 1로 폭발하며, 거리 1 이내에 있는 다른 건초 더미들도 폭발에 휩싸인다. 이 이웃 더미들은 (모두 동시에) 각각 폭발 반경 2로 폭발하므로, 이 폭발들은 거리 2 이내의 아직 폭발하지 않은 더미들을 추가로 휩쓸 수 있다. 다음 시간 단계에서는 이 더미들도 (모두 동시에) 폭발 반경 3으로 폭발한다. 일반적으로, 시각 \(t\)에 폭발하는 건초 더미들은 각각 폭발 반경 \(t\)를 가진다. 이 폭발에 휩싸인 더미들은 시각 \(t+1\)에 폭발 반경 \(t+1\)로 폭발하며, 이런 식으로 계속된다.
연쇄 반응을 시작하기에 가장 좋은 건초 더미에 소 한 마리를 발사했을 때 폭발할 수 있는 건초 더미의 최대 개수를 구하시오.
Problem credits: Brian Dean
Problem credits: Brian Dean
입력의 첫째 줄에 \(N\)(\(1 \leq N \leq 100\))이 주어진다. 나머지 \(N\)개의 줄에 정수 \(x_1 \ldots x_N\)(각각 \(0 \ldots 1,000,000,000\) 범위)이 주어진다.
소 한 마리로 폭발시킬 수 있는 건초 더미의 최대 개수를 출력한다.
angry.in · 출력을 쓸 파일 angry.out6
8
5
6
13
3
45In this example, launching a cow onto the hay bale at position 5 will cause the
bales at positions 4 and 6 to explode, each with blast radius 2. These
explosions in turn cause the bales at positions 3 and 8 to explode, each with
blast radius 3. However, these final explosions are not strong enough to reach
the bale at position 13.
riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > January > Bronze