Problem 1: Divisibility by 13
Permuting a number so that it is divisible by 13
Description
Most numbers are not divisible by 13. For this problem, we say 13 divides
if tt = 13k for some integer k.
But, if we allow you to permute the digits of a number t (as written in decimal), perhaps you can get 13 to divide t.
For example, 13 does not divide 1331, but it clearly divides 1313, a permutation of 1331.
Input
An input file will contain a list of positive integers, one per line. Each integer will be no more than nine (9) decimal digits long. The list will end with the number 0, which should not be processed.
An example input file might look like this:
4
13
8220
13131
58403
120000000
0
Output
For each input value (except '0'), your program should output all permutations that are a multiple of 13, sorted smallest to largest. Output each number only once. If there are no solutions, output the string No Solutions.
on a single line by itself. After handling one line of input, output a blank line.
Here is the output that would be produced for the input file shown above:
01234567890123456789
01 No Solutions.
02
03 13
04
05 2028
06
07 33111
08
09 03458
10 30485
11 34580
12 35048
13 48035
14 48503
15 50843
16 84305
17
18 No Solutions.
19
NOTE: The lines numbers (
) and the header line (XX
) in the output file above are included for your reference only... they should not appear in the output file produced by your program. 01234567890123456789
Program Mechanics
- Your program will accept one command line argument: the name of the input file.
- The input file will have a file extension of
..dat - Your program will produce an output file that has the same name as the input file but with a file extension of
..out
Thus, if your program is passed the input file
, your program will produce the output file prob1.dat
.
prob1.out