KOI 2차 2020 초2/중1- 종이접기 > 문제은행 : 정보올림피아드&알고리즘




4601 : 종이접기

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
0 회   
시도횟수
0 회   

문제

정사각형의 종이를 중앙선을 중심으로 접는 방법은 아래 그림에서 보인 것처럼 4가지가 있다.



  • D: 가로 중심선을 중심으로 반으로 접되 윗 면이 아랫 면을 덮도록 접음

  • U: 가로 중심선을 중심으로 반으로 접되 아랫 면이 윗 면을 덮도록 접음

  • R: 세로 중심선을 중심으로 반으로 접되 왼쪽 면이 오른쪽 면을 덮도록 접음

  • L: 세로 중심선을 중심으로 반으로 접되 오른쪽 면이 왼쪽 면을 덮도록 접음


한 변의 길이가 2k인 정사각형 종이가 있을 때, 이를 세로로 k번, 가로로 k번 접으면 (접는 순서는 상관없음) 각 변의 길이가 1인 정사각형이 된다. 아래 그림에서 보인 것처럼 각 변의 길이가 1인 정사각형의 네 귀퉁이 중 한 군데에 구멍을 낸다. 구멍의 위치는 그림에서 보인 것처럼 숫자로 표시한다.



구멍을 낸 후 접은 순서의 역순으로 종이를 펼치면, 종이에 22k개의 구멍이 있게 된다. 예를 들어, 한 변의 길이가 4(= 22)인 정사각형을 <R, D, D, R> 순서대로 접은 후, 3번 위치에 구멍을 낸 다음 종이를 펼치면 아래 그림처럼 구멍이 나게 된다.



종이의 크기를 나타내는 정수 k, 종이를 접는 순서를 나타내는 정보, 구멍 뚫는 위치를 나타내는 정수가 주어질 때, 2k × 2k 격자에 뚫린 구멍의 위치를 출력하는 프로그램을 작성하시오.​



제약 조건


  • 1 ≤ k ≤ 8
  • 반드시 가로로 k번, 세로로 k번 접는다.


부분문제


  1. (29점) k = 1
  2. (34점) 종이를 접는 순서는 U와 R로만 이루어진다.
  3. (37점) 추가 제약 조건 없음​

입력형식

첫 번째 줄에 k가 주어진다.

 

다음 줄에는 종이 접는 방법을 나타내는 문자가 2k개 주어지는데, 각 문자는 공백으로 구분된다. 종이를 접는 방법 D, U, R, L은 각각 해당하는 대문자 알파벳으로 주어진다.

 

다음 줄에는 구멍 뚫는 위치를 나타내는 정수 h(0 ≤ h ≤ 3) 가 주어진다.​ 


출력형식

접힌 종이를 접은 순서의 역순으로 펼친 후 정사각형에 뚫린 구멍의 위치를 번호로 출력한다. 출력은 총 2k줄로 이루어지며 i (1 ≤ i ≤ 2k)번째 줄에는 격자의 i번 행에 뚫린 구멍의 번호를 왼쪽에서 오른쪽 순서로, 공백을 사이에 두고 출력한다.

 


입력 예

2
R D D R
3

출력 예

0 1 0 1
2 3 2 3
0 1 0 1
2 3 2 3


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP