Bessie the cow가 다음 큰 히트작이 될 것이라고 생각하는 비디오 게임 "Angry Cows"를 디자인했다. 그녀는 이 게임의 개념이 완전히 독창적이라고 믿고 있다. 게임의 기본 개념은 플레이어가 소를 새총으로 발사하여 1차원 선상에 위치한 건초 더미들을 향해 쏘는 것이다. 소가 건초 더미에 착지하면 충분한 힘으로 인해 건초 더미가 폭발하며, 이로 인해 인접한 건초 더미들도 연쇄적으로 폭발할 수 있다. 목표는 한 번의 발사로 최대한 많은 건초 더미를 폭발시키는 것이다.

N개의 건초 더미가 정수 좌표 x_1, x_2, \ldots, x_N에 위치해 있다. 소가 좌표 x에 있는 건초 더미 위에 착지하면, 이 건초 더미는 "폭발 반경"이 1인 폭발을 일으킨다. 즉, 거리 1 이내에 있는 다른 건초 더미들도 폭발에 휩싸이게 된다. 이렇게 폭발한 건초 더미들은 (모두 동시에) 다시 폭발하며, 이번에는 반경 2의 폭발을 일으켜 거리 2 이내의 추가적인 건초 더미들을 폭발시킬 수 있다. 다음 시간 단계에서는 이 건초 더미들도 (모두 동시에) 반경 3의 폭발을 일으킨다. 일반적으로, 시간 t에서 한 무리의 건초 더미가 폭발하면, 각 건초 더미는 반경 t의 폭발을 일으킨다. 이 폭발에 휩싸인 건초 더미들은 시간 t+1에서 반경 t+1의 폭발을 일으키며, 이러한 과정이 계속된다.

한 번의 소 발사로 최대한 많은 건초 더미를 폭발시킬 수 있도록, 최적의 시작 위치를 찾아 최대 폭발 개수를 구하라.

#3960 upload 6 done 3 how_to_reg 3

Angry Cows timer 2s memory 512MB

#3960

Angry Cows 2s 512MB