텔레점프

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

요약
1칸 이동권 a장, 2칸 이동권 b장, 3칸 이동권 c장이 있고 n = a+b+c+1일 때, 행성 0부터 n-1까지를 정확히 한 번씩 방문하면서 모든 이동권을 정확히 한 번씩 쓰는 경로를 출력한다.
난이도

보통10점 중 6점

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

문제

홍준이와 친구들은 2014년을 맞이해 nn개의 행성을 여행하려 한다. 행성에는 00번부터 n−1n-1번까지 번호를 붙인다. 우주선 대신 사성(Sasung)과 부글(Boogle)이 공동 개발한 텔레점프 텔레포트 시스템으로 순간이동한다. 출발지는 00번 행성이며, 마지막 행성은 어디든 된다.

텔레점프에는 세 종류의 티켓이 있다.

  • 1번 티켓: xx에서 x+1x+1 또는 x−1x-1로 이동 (0≤x±1≤n−10 \le x \pm 1 \le n-1)
  • 2번 티켓: xx에서 x+2x+2 또는 x−2x-2로 이동 (0≤x±2≤n−10 \le x \pm 2 \le n-1)
  • 3번 티켓: xx에서 x+3x+3 또는 x−3x-3로 이동 (0≤x±3≤n−10 \le x \pm 3 \le n-1)

1번 티켓 aa장, 2번 티켓 bb장, 3번 티켓 cc장을 가지고 있으며 a+b+c+1=na+b+c+1=n이다. 각 종류는 최소 3장 이상이므로 n≥10n \ge 10이다.

모든 행성을 정확히 한 번씩 방문하는 순서를 출력하라. 각 티켓은 정확히 한 번씩 쓰여야 한다.

입력

첫 줄에 테스트 케이스 수 TT (1≤T≤201 \le T \le 20)가 주어진다.

각 테스트 케이스는 한 줄에 세 정수 aa, bb, cc (3≤a,b,c≤50003 \le a,b,c \le 5000)가 주어지며, 이때 n=a+b+c+1n=a+b+c+1이다.

출력

각 테스트 케이스마다 한 줄에 nn개의 행성 번호를 공백으로 구분해 출력한다. 방문 순서는 00번 행성에서 시작해야 한다.

해가 여러 개면 아무 순서나 출력해도 된다. 입력에는 항상 해가 존재한다.

힌트

티켓 길이가 3인 이동으로 큰 간격을 먼저 확보한 뒤, 남은 1·2번 티켓으로 아직 방문하지 않은 행성을 메운다. a=b=ca=b=c일 때는 세 종류를 번갈아 쓰는 반복 패턴 하나로 전체를 덮을 수 있다.

예제3

  1. 예제 1

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

    입력
    1
    3 3 3
    
    예상 출력
    0 3 1 2 5 4 6 9 7 8
    
  3. 예제 3

    입력
    1
    3 4 3
    
    예상 출력
    0 3 1 2 5 4 6 9 7 8 10