[D] Digits
시간 제한3초메모리 제한1024 MB
목표 T와 여섯 개의 수가 주어질 때, +, -, *, / 연산으로 양의 정수만 남기며 T에 도달하는 수열을 출력하거나 불가능하면 -1을 출력한다.
문제
지금은 사라졌지만, 예전에는 New York Times에 Digits라는 게임이 있었다. 이 게임의 규칙은 다음과 같다.
-
플레이어가 목표로 하는 양의 정수 가 주어진다.
-
게임판에 개의 양의 정수가 적힌 상태로 시작한다.
-
플레이어는 게임판에 수가 개 이상 있는 동안 아래 연산을 시행할 수 있다. 연산을 반드시 시행해야만 할 필요는 없다.
- 게임판에서 수 하나를 선택하고 지운다. 이때 지운 수를 라고 하자.
- 게임판에서 수 하나를 더 선택하고 지운다. 이때 지운 수를 라고 하자.
- , , , 중 하나를 선택하여 게임판에 적는다. 단, 양의 정수가 아닌 수를 게임판에 적을 수는 없다.
-
모든 연산을 끝낸 뒤 게임판에 가 적혀 있다면 플레이어가 승리하고, 그렇지 않다면 패배한다.
하이볘는 아직 이 게임을 더 즐기고 싶었기에 이를 직접 구현하였지만, 아직 주어진 게임판에서 플레이어가 승리할 수 있는지 판별하는 방법은 모른다. 이에 착한 여러분들이 게임판의 상태를 읽고, 어떻게 하면 게임에서 승리할 수 있는지 알려주는 프로그램을 작성해 주기로 했다.
입력
첫째 줄에는 목표로 하는 값인 양의 정수 가 주어진다.
둘째 줄에는 게임판에 적힌 개의 양의 정수 이 공백으로 구분되어 주어진다.
출력
만약 플레이어가 승리할 수 없다면 첫째 줄에 -1을 출력한다.
만약 플레이어가 승리할 수 있다면 첫째 줄에 사용한 연산의 수 를 출력하고, 둘째 줄부터 개의 줄에 걸쳐 플레이어가 승리하기 위해 수행해야 하는 연산을 순서대로 아래와 같이 출력한다.
- 만약 게임판에서 와 를 지운 뒤 연산자 를 사용하여 를 적었다면,
a op b = c를 출력한다. , , , 연산자는 각각+,-,*,/로 출력한다.
만약 플레이어가 승리하는 방법이 여러 가지라면 그중 아무거나 하나를 출력하면 되며, 를 최소화할 필요는 없다.