[D] Digits

시간 제한3초메모리 제한1024 MB

요약
목표 T와 여섯 개의 수가 주어질 때, +, -, *, / 연산으로 양의 정수만 남기며 T에 도달하는 수열을 출력하거나 불가능하면 -1을 출력한다.
난이도

어려움10점 중 8점

유형
백트래킹, 완전 탐색
정답자
아직 제출이 없습니다

문제

지금은 사라졌지만, 예전에는 New York Times에 Digits라는 게임이 있었다. 이 게임의 규칙은 다음과 같다.

  1. 플레이어가 목표로 하는 양의 정수 TT가 주어진다.

  2. 게임판에 66개의 양의 정수가 적힌 상태로 시작한다.

  3. 플레이어는 게임판에 수가 22개 이상 있는 동안 아래 연산을 시행할 수 있다. 연산을 반드시 시행해야만 할 필요는 없다.

    • 게임판에서 수 하나를 선택하고 지운다. 이때 지운 수를 aa라고 하자.
    • 게임판에서 수 하나를 더 선택하고 지운다. 이때 지운 수를 bb라고 하자.
    •  a+ba+b, a−ba-b, a×ba\times b, a÷ba\div b 중 하나를 선택하여 게임판에 적는다. 단, 양의 정수가 아닌 수를 게임판에 적을 수는 없다.
  4. 모든 연산을 끝낸 뒤 게임판에 TT가 적혀 있다면 플레이어가 승리하고, 그렇지 않다면 패배한다.

하이볘는 아직 이 게임을 더 즐기고 싶었기에 이를 직접 구현하였지만, 아직 주어진 게임판에서 플레이어가 승리할 수 있는지 판별하는 방법은 모른다. 이에 착한 여러분들이 게임판의 상태를 읽고, 어떻게 하면 게임에서 승리할 수 있는지 알려주는 프로그램을 작성해 주기로 했다.

입력

첫째 줄에는 목표로 하는 값인 양의 정수 TT가 주어진다. (1≤T≤1018)\left( 1 \le T \le 10^{18} \right) 

둘째 줄에는 게임판에 적힌 66개의 양의 정수 X_1,X_2,…,X_6X\_1, X\_2, \ldots, X\_6이 공백으로 구분되어 주어진다. (1≤X_i≤1,000)(1 \le X\_i \le 1\\,000)

출력

만약 플레이어가 승리할 수 없다면 첫째 줄에 -1을 출력한다.

만약 플레이어가 승리할 수 있다면 첫째 줄에 사용한 연산의 수 KK를 출력하고, 둘째 줄부터 KK개의 줄에 걸쳐 플레이어가 승리하기 위해 수행해야 하는 연산을 순서대로 아래와 같이 출력한다.

  • 만약 게임판에서 aa와 bb를 지운 뒤 연산자 opop를 사용하여 cc를 적었다면, a op b = c를 출력한다. ++, −-, ×\times, ÷\div 연산자는 각각 +, -, *, /로 출력한다.

만약 플레이어가 승리하는 방법이 여러 가지라면 그중 아무거나 하나를 출력하면 되며,  KK를 최소화할 필요는 없다.

예제3

  1. 예제 1

    입력
    86
    1 25 5 4 10 3
    
    예상 출력
    5
    25 / 5 = 5
    5 + 4 = 9
    9 * 10 = 90
    90 - 1 = 89
    89 - 3 = 86
    
  2. 예제 2

    입력
    10
    1 1 1 1 1 1
    
    예상 출력
    -1
    
  3. 예제 3

    입력
    10
    1 3 6 10 15 21
    
    예상 출력
    0