당신은 국제적인 댄스 대회를 기획하고 있다. 현재 다음은 모두 준비되어 있다:

단위 정사각형 칸들로 이루어진 R행 C열의 댄스 플로어,
R × C명의 참가자,
최첨단 자동 심판 시스템.

하지만 아직 관객이 없다! 대회가 충분히 흥미롭지 않을까 걱정되어, 대회의 흥미도(interest level)를 계산하는 방법을 고안했다.

각 참가자는 플로어의 한 칸을 차지하고, 탈락할 때까지 그 칸에 머문다. 참가자 x의 방위 이웃(compass neighbor)이란, x와 같은 행 또는 같은 열에 있으면서, x와 y 사이에 아직 남아 있는 참가자가 하나도 없도록 선택한 다른 참가자 y를 말한다. 각 참가자는 방위 이웃을 0명에서 4명까지 가질 수 있고, 한 직교 방향의 다른 참가자들이 모두 탈락하면 그 수는 감소할 수 있다.

대회는 라운드 단위로 진행된다. i라운드와 i+1라운드 사이에, 어떤 참가자 d가 i라운드 동안 적어도 한 명의 방위 이웃을 가지고 있었고, d의 실력치가 d의 모든 방위 이웃들의 실력치 평균보다 엄격히 작다면, d는 탈락하여 i+1, i+2, i+3, ... 라운드에는 참가하지 않는다. i라운드와 i+1라운드 사이에 다른 탈락이 일어날 때, d는 여전히 자신의 다른 방위 이웃들의 이웃으로 계산된다는 점에 유의하라. 방위 이웃이 전혀 없는 참가자는 절대 탈락하지 않는다. 어떤 라운드 이후에 아무도 탈락하지 않으면 대회는 종료된다.

한 라운드의 흥미도는 그 라운드에서 춤추는 참가자들의 실력치 합이다. (그 라운드와 다음 라운드 사이에 탈락할 예정인 참가자도 포함한다.) 대회의 흥미도는 모든 라운드의 흥미도를 합한 값이다.

1라운드에 플로어 위에 있는 댄서들의 실력치가 주어질 때, 대회의 흥미도는 얼마인가?

#10366 upload 1 done 1 how_to_reg 1

Square Dance timer 40s memory 1024MB

#10366

Square Dance 40s 1024MB