극장 좌석 우선순위

시간 제한1초메모리 제한128 MB

요약
1행 가운데 좌석에서의 유클리드 거리로 각 좌석의 우선순위를 정하고, 거리가 같으면 행 번호와 좌석 번호로 순서를 가른 뒤 뒷줄부터 앞줄 순서로 출력한다.
난이도

쉬움10점 중 3점

유형
정렬, 수학, 구현
정답자
아직 제출이 없습니다

문제

한 극장의 좌석이 직사각형 모양으로 배치되어 있다. 한 줄에 놓인 좌석 수(폭) WW는 홀수이며 11≤W≤10111 \le W \le 101이고, 줄 수는 RR로 4≤R≤504 \le R \le 50이다. 각 줄의 좌석은 무대에서 볼 때 왼쪽부터 오른쪽으로 11번부터 WW번까지 번호가 매겨지고, 줄은 무대에 가장 가까운 줄부터 11번부터 RR번까지 번호가 매겨진다. 같은 줄에서 이웃한 두 좌석 사이의 간격은 11이며, 이 간격은 서로 인접한 두 줄에서 바로 앞뒤에 있는 두 좌석 사이의 간격과 같다. 따라서 rr번 줄의 ss번 좌석은 격자점 (s,r)(s, r)에 놓인다.

표는 온라인으로 판매되며 좌석이 자동으로 배정되므로, 모든 좌석에는 서로 다른 우선순위가 부여된다. 우선순위 11이 가장 좋다. 우선순위는 다음 규칙에 따라 정해진다.

  1. 무대에 가장 가까운 11번 줄의 한가운데 좌석, 즉 위치 (W+12, 1)\left(\frac{W+1}{2},\ 1\right)의 좌석이 가장 좋은 우선순위 11을 가진다.
  2. 나머지 좌석은 그 가장 좋은 좌석까지의 유클리드 거리로 순위를 매긴다. 좌석이 가까울수록 우선순위가 더 좋다(숫자가 더 작다).
  3. 거리가 정확히 같은 좌석들 중에서는 무대에 더 가까운 줄(줄 번호가 더 작은 쪽)의 좌석이 더 좋은 우선순위를 가진다.
  4. 거리가 같고 같은 줄에 있는 좌석들 중에서는 11번 좌석(가장 왼쪽 좌석)에 더 가까운 좌석이 더 좋은 우선순위를 가진다.

모든 좌석의 좌표 (x,y)(x, y)가 서로 다르므로, 이 규칙들은 W⋅RW \cdot R개의 좌석 각각에 서로 다른 우선순위를 부여한다. 주어진 폭과 줄 수에 대해 완성된 우선순위 표를 출력하는 프로그램을 작성하라.

입력

공백으로 구분된 두 정수 WW와 RR이 한 줄에 주어진다. WW는 홀수이고 11≤W≤10111 \le W \le 101, 4≤R≤504 \le R \le 50이다.

출력

RR개의 줄을 출력한다. i=1,2,…,Ri = 1, 2, \ldots, R에 대해 ii번째 줄에는 R−i+1R - i + 1번 줄에 있는 좌석들의 우선순위 WW개를 11번 좌석부터 WW번 좌석 순서로 공백 하나로 구분하여 출력한다. 즉 극장 뒤쪽 줄(RR번 줄)부터 맨 앞줄(11번 줄)까지 차례대로 출력한다.

예제3

  1. 예제 1

    입력
    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

  2. 예제 2

    입력
    11 4
    예상 출력
    43 37 31 25 21 18 22 26 32 38 44
41 33 23 14 12 9 13 15 24 34 42
39 29 19 10 5 4 6 11 20 30 40
35 27 16 7 2 1 3 8 17 28 36

  3. 예제 3

    입력
    13 4
    예상 출력
    51 43 37 31 25 21 18 22 26 32 38 44 52
49 41 33 23 14 12 9 13 15 24 34 42 50
47 39 29 19 10 5 4 6 11 20 30 40 48
45 35 27 16 7 2 1 3 8 17 28 36 46