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

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

피자 오븐

면접 대비

시간 제한0.25초메모리 제한256 MB

요약
목표 시간에 도달하는 최소 버튼 횟수를 구하고, 같은 횟수라면 사전순으로 가장 작은 버튼 횟수 조합을 출력한다.
난이도

보통10점 중 6점

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

문제

피자를 굽는 전자식 오븐이 있다. 이 오븐에 재료를 넣고 정확히 NN분 동안 동작을 시키고자 한다. 이 오븐에는 동작 시간을 늘리거나 줄이는 버튼이 5개 있다. 처음에 오븐의 시간은 0분으로 정해져 있다. 시간을 줄이는 버튼을 눌러 시간이 0분보다 작아지면 0분으로 설정된다. tt가 현재 오븐에 세팅된 시간, t′t'이 버튼을 누른 뒤의 시간일 때, 각 버튼의 기능은 다음과 같다.

  • ADDH: t′=t+60t' = t + 60
  • ADDT: t′=t+10t' = t + 10
  • MINT: t′=t−10t' = t - 10
  • ADDO: t′=t+1t' = t + 1
  • MINO: t′=t−1t' = t - 1

예를 들어 58분을 설정하려면 ADDO(+1분) 버튼을 58번 눌러도 된다. 하지만 ADDH(+60분) 버튼을 한 번 누른 뒤 MINO(-1분) 버튼을 2번 누르면 3번의 작업으로 58분을 만들 수 있다. 42분을 설정하려면 ADDH, MINT, MINT, ADDO, ADDO 순서로 5번 누르면 된다. ADDT, ADDT, ADDT, ADDT, ADDO, ADDO 순서로 6번 눌러도 되지만, 버튼은 최소 횟수로 누르려고 한다.

설정해야 할 시간이 주어졌을 때, 그 시간을 만들기 위해 눌러야 하는 버튼의 최소 횟수와 그 방법을 구하는 프로그램을 작성하시오.

입력

입력은 TT개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 설정해야 하는 시간 NN이 분 단위의 정수로 주어진다.

출력

각 테스트 케이스마다 5개의 정수를 한 줄에 공백으로 구분해 출력한다. 이 정수는 입력으로 주어진 시간을 만들기 위해 ADDH, ADDT, MINT, ADDO, MINO 버튼을 누르는 횟수이다. 최소 횟수로 누르는 방법이 여러 가지인 경우에는 사전 순으로 가장 앞서는 방법을 출력한다.

작업 횟수가 같은 방법이 여러 가지일 때, ADDH를 누르는 횟수가 적은 것이 사전 순으로 앞서고, ADDH를 누르는 횟수가 같으면 ADDT를 누르는 횟수가 적은 것이 먼저이다. ADDT를 누르는 횟수가 같으면 MINT를 누르는 횟수가 적은 것이, MINT를 누르는 횟수가 같으면 ADDO를 누르는 횟수가 적은 것이, ADDO를 누르는 횟수가 같으면 MINO를 누르는 횟수가 적은 것이 사전 순으로 앞선다.

제한

  • 1≤T≤1001 \le T \le 100
  • 1≤N≤10,000,0001 \le N \le 10,000,000

예제1

  1. 예제 1

    입력
    3
5
12
27
    예상 출력
    0 0 0 5 0
0 1 0 2 0
0 3 0 0 3