Lucky ticket
A ticket on the planet Olympia features a six-digit number. The locals have a unique method for determining if a ticket is "lucky." They choose a specific number, k, and attempt to derive this number from the ticket using the following rules:
First, the ticket number is divided into individual digits, and some adjacent digits can be combined to form new numbers.
Mathematical symbols such as brackets, plus, minus, multiply, and divide are inserted between these numbers according to standard mathematical rules. A unary minus is also permissible.
The order of the digits cannot be changed.
If it's possible to create an expression that evaluates to the desired number k, then the ticket is considered lucky.
The "divide" operation is only allowed when the division results in an integer.
Consider the ticket number: 182836. Let k=840. You can split the number into four parts: 1, 8, 2, 836. The number k can be obtained, for example, as follows: 1*(8/2+836)=840.
Write a program named LUCKY that, given a ticket number and the number k, determines whether the ticket is lucky and finds one possible way to split the number into a sequence of numbers. Between these numbers, mathematical operations and brackets can be placed to achieve the desired number k.
Input
The input file contains a single line with two numbers: an integer k (1 ≤ k ≤ 1000) and the ticket number. The ticket number consists of six digits and may begin with 0.
Output
The output file should contain a single line with any valid set of numbers into which the ticket number can be split to achieve the number k. If the number cannot be obtained, the output should be the digit 0 (zero).