아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

육각형 목장 네트워크

면접 대비

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

요약
육각형 모양으로 배치된 목초지에서 시작 지점 H로부터 정확히 거리 L인 모든 목초지의 번호를 BFS로 구해 오름차순으로 출력한다.
난이도

보통10점 중 5점

유형
그래프, BFS, 구현
정답자
아직 제출이 없습니다

문제

농부 존이 최근 농장을 넓히려고 새 땅을 얻었습니다. 그의 소들은 벌집의 육각형 구조를 좋아하게 되어서, 농부 존은 그 모양을 본떠 새로운 목초지와 소길(cowpath) 체계를 만들었습니다.

목초지와 소길 전체는 한 변의 길이가 KK (2≤K≤502 \le K \le 50)인 육각형을 이룹니다. 목초지에는 1…3K(K−1)+11 \ldots 3K(K-1)+1 번호가 매겨집니다.

이 육각형을 세로 방향 열들의 모임으로 생각해 보세요. 왼쪽에서 오른쪽으로 각 열에 들어 있는 목초지의 수는 K,K+1,…,2K−1,…,K+1,KK, K+1, \ldots, 2K-1, \ldots, K+1, K 개입니다(가운데 열이 2K−12K-1개로 가장 많습니다). 목초지 번호는 11번부터 차례대로 매겨지며, 왼쪽 열부터 오른쪽 열 순서로, 그리고 각 열 안에서는 아래에서 위로 올라가며 붙입니다. 따라서 11번 목초지는 가장 왼쪽 열의 맨 아래에 있고, 마지막 목초지인 3K(K−1)+13K(K-1)+1번은 가장 오른쪽 열의 맨 위에 있습니다.

각 목초지는 인접한 모든 목초지와 소길로 연결됩니다. 육각형 내부에 있는 목초지는 정확히 여섯 개의 목초지와 인접합니다. 예를 들어 K=3K = 3일 때 1010번 목초지는 55, 66, 99, 1111, 1414, 1515번과 인접합니다. 모서리(꼭짓점은 제외)에 있는 목초지는 정확히 네 개와 인접하며(예: 44번 목초지는 11, 55, 88, 99번과 인접), 꼭짓점에 있는 목초지는 세 개와만 인접합니다(예: 11번 목초지는 22, 44, 55번과 인접). 모든 소길의 길이는 11이고, 두 목초지 사이의 거리는 두 목초지를 잇는 가장 짧은 경로의 길이로 정의합니다.

농부 존의 홀스타인 소들은 며칠 동안 HH (1≤H≤3K(K−1)+11 \le H \le 3K(K-1)+1)번 목초지에서 풀을 뜯으며 살이 찌고 게을러졌습니다. 소들을 운동시키기 위해, 농부 존은 소가 있는 곳에서 거리가 정확히 LL (1≤L≤2K−21 \le L \le 2K-2)인 모든 목초지에 맛있는 간식을 놓아 둡니다. 간식을 적어도 하나는 놓았다고 약속하지만, 어느 목초지에 두었는지는 알려 주지 않습니다.

소들이 쓸데없이 걷지 않도록 도와주세요. 간식이 놓여 있을 수 있는 목초지의 개수를 구하고, 그 번호들을 오름차순으로 나열하세요.

입력

첫째 줄에 공백으로 구분된 세 정수 KK, HH, LL이 주어집니다.

출력

첫째 줄에 목초지 HH에서 거리가 정확히 LL인 목초지의 개수를 정수로 출력합니다.

이어지는 각 줄에 그러한 목초지의 번호를 오름차순으로 하나씩 출력합니다.

예제3

  1. 예제 1

    입력
    3 1 2
    
    예상 출력
    5
    3
    6
    8
    9
    10
    
  2. 예제 2

    입력
    2 1 1
    
    예상 출력
    3
    2
    3
    4
    
  3. 예제 3

    입력
    3 10 1
    
    예상 출력
    6
    5
    6
    9
    11
    14
    15