같은 행에서 두 인접한 좌석 사이의 거리와 앞뒤에 있는 인접한 거리는 같다.
소들은 좌석을 인터넷으로 팔기를 원하고 판매한 각 티켓의 자동 좌석 지정을 하기를 원한다. 티켓을 산 사람은 항상 가장 좋은 좌석을 사기를 원한다. 그래서 모든 좌석은 그것과 관계된 유일한 '우선순위' 를 가진다.
첫 행의 중간 좌석은(무대와 가장 가까운)은 1 , (w+1)/2 에 위치하고 있다. 그리고 가장 좋은 우선순위를 가진다.
이 좌석과 유클리디언 거리로 가장 가까운 좌석은 다음으로 높은 우선순위를 가진다. 이런 식으로 우선순위가 정해 진다.
첫 행에서 같은 거리에 있는 모든 좌석은 두 번째 행에서 같은 거리에 있는 모든 좌석보다 우선순위가 높다.
어떤 좌석은 가장 좋은 좌석으로 부터 거리가 같기때문에 , 좌석 번호 1 에 가장 가까운 같은 행에는 ( 가장 왼쪽의 좌석... 무대로에서 좌석을 볼때) 아래 도표에서 보듯이 더 좋은 우선군이 주어진다.
아래 도표는 작은(11 x 5) 의 극장의 보기이다.
Seat Number
1 2 3 4 5 6 7 8 9 10 11
+----------------------------------
Row 5 | 54 50 44 38 32 29 33 39 45 51 55
Row 4 | 52 42 34 25 21 18 22 26 35 43 53
Row 3 | 48 36 23 14 12 9 13 15 24 37 49
Row 2 | 46 30 19 10 5 4 6 11 20 31 47
Row 1 | 40 27 16 7 2 1 3 8 17 28 41
좌석의 우선순위를 정하는 것이 문제이다.
입력 11 5 출력 54 50 44 38 32 29 33 39 45 51 55 52 42 34 25 21 18 22 26 35 43 53 48 36 23 14 12 9 13 15 24 37 49 46 30 19 10 5 4 6 11 20 31 47 40 27 16 7 2 1 3 8 17 28 41
출처:USACO JAN 2010 bronze