Help with number problem

Primes, divisors, arithmetic, number properties, ...
Post Reply
Posts: 1
Joined: Sat Mar 15, 2014 6:27 pm

Help with number problem

Post by Koekje » Sat Mar 15, 2014 6:30 pm

So I 've recently taken interest in solving all sorts of programming problems, which also lead me to PE, among others. Currently I am also trying to solve old problems from a yearly contest, but the problem I am at now has got me pretty stumped.

The problem goes as follows:

Given a set with k digits, k element of [1,9], with each digit being unique in the set, and given an integer G, determine if it is possible to compose the given digits to create the given integer G and if so, give the minimal composing cost.

The rules for composing are:
- Only use addition and multiplication
- You can use brackets ( )
- You can concatenate digits to form new numbers, but only the same digit

The cost is equals to the amount of times you used a digit.

Some examples:

set [3] G 9 : 3 x 3 = 9 -> cost 2
set [3] G 72 : (3 + 3) x (3 + 3 x 3) = 72 -> cost 5
set [2,7] G 729 : (2 + 7) x (2 + (2 + 77)) -> cost 6

I thought of some straightforwards things, like the lower bound cost must be at least as big as the number of digits in G. And that if I'm given a single digit, G must be evenly divisibly by that digit. I could even generate all possible numbers which can be constructed as long as they are smaller than G. And of course, as soon as I find a solution, that can stand for my upper bound cost. Perhaps it is better to search top-down and try to decompose G?

But this just rounds down to trying alls sorts of combinations. Surely there must be a smarter approach? Something I'm clearly overseeing?

Any help or advice would be super great!

Post Reply