파일 업로드

육각형 방탈출

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

사업가인 주민은 최근에 방탈출 카페를 만들기 위해 새로운 땅을 구매했습니다. 육각형 구조에 매료된 주민은 새로운 카페의 방과 통로를 육각형 구조로 만들었습니다.

방과 통로의 전체 구획은 변의 길이가 K (2 <= K <= 50)인 육각형을 형성합니다. 방들은 왼쪽 하단에서 시작해 오른쪽 상단에서 끝나는 패턴에 따라 1..3*K*(K-1)+1까지 번호가 매겨져 있으며, 이는 아래 그림에서 K = 3일 때의 일반화된 패턴의 예시를 확인할 수 있습니다.

각 방은 주변 모든 방과 연결되어 있습니다. 이는 육각형 안쪽에 위치한 방은 정확히 다른 6개의 방과 인접해 있다는 것을 의미합니다. 예를 들어, 위의 다이어그램에서 방 #10은 방 #5, #6, #11, #15, #14, #9와 인접해 있습니다. 맨 끝(하지만 모서리는 아님)에 있는 방들은 정확히 다른 4개의 방과 인접해 있습니다 (예를 들어 방 #4는 방 #1, #5, #9, #8와 인접) 모서리에 있는 방들은 오직 다른 세 개의 방만 인접합니다 (즉 방 #1은 방 #2, #5, #4와 연결돼 있습니다). 두 방을 연결하는 통로의 길이는 1이며, 두 방 간의 거리는 그들 사이의 최단 가능 경로의 길이로 정의됩니다.

이 카페의 손님들은 며칠 동안 방 H(1 <= H <= 3*K*(K-1)+1)을 정복하지 못하고 있었습니다. 주민은 손님들이 탈출하길 바라는 마음으로, 손님들이 정복하지 못한 방으로부터 L(1 <= L <= 2*K-2)의 거리에 힌트를 놓아두었습니다. 그는 손님들에게 최소한 하나의 힌트를 준다는 것을 보장하지만, 힌트를 어느 방에 놓았는지는 손님들에게 말해주지 않습니다.

손님들이 힌트를 얻어 방을 탈출할 수 있도록, 힌트가 있을 수 있는 방의 숫자와 오름차순으로 정렬된 방의 목록을 출력해 주세요.

예를 들어, K = 3, 손님이 방 #1에 있고, 주민이 2의 거리에 힌트를 놓아두었다고 가정할 때. 가능한 힌트의 위치는 방 #3, #6, #10, #9, 그리고 #8이며, 아래 그림처럼 나타납니다.

💻 입력
  • 첫 번째 줄 : 세 개의 공백으로 구분된 정수: K, H, and L
🖨️ 출력
  • 첫 번째 줄 : 방 H와의 거리가 L인 방의 수를 나타내는 하나의 정수
  • 두 번째 줄부터 N+1 번째 줄 : 각 i+1 번째 줄은 오름차순으로 정렬된 이러한 방 중 i번째 방을 나타냅니다

💻 예제 입력 1
3 1 2
🖨️ 예제 출력 1
5
3
6
8
9
10

출처: USACO 2011 February Bronze 3