At first, let's solve the easier input. We need to find an arithmetical expression compound only from symbols '+', '*', '!', '(', ')', and '1' that matches the given input number, such that the number of used symbols '1' is as low as possible. Let's name p[i] the minimal number of '1's for expression matching the number i. Obviously p[1] = 1, because 1 = 1 :-) Now, for a certain K > 1, let's assume that we know all the p[i] for all i less than K, and all the corresponding expressions. We'll try to find out p[K] and its corresponding expression. It is certain that p[K] is the minimum of all p[a] + p[b], where 1 <= a,b < K, a + b = K (those are at most K/2), all p[c] + p[d], where 1 <= c,d < K, c * d = K (those are at most square root of K) and all p[e], where 1 <= e < K, e! = K (that is at most one.). Its corresponding expression is combined from corresponding expressions of all operands joined by the operator of the minimum of all p[a] + p[b], all p[c] + p[d] and all p[e]. We can in successive steps count p[2], p[3], p[4], ..., p[input number] and their corresponding expressions by the described procedure.
As the given numbers in the easy input are rather small, this algorithm will count the final arithmetical expression pretty soon, but what to do with the difficult input, where the given number has couple thousand digits. One can easily realize that the number in the hard input is sum of one big and one small factorial, because there are too many zeros at the end of the input aborted with short sector with other digits. Good solution is to write a short program that computes big factorials and try to compute some and compare them with the input. After few experiments one will find out that the input number is a sum of 247! and 2249!. Arithmetical expressions corresponding to the numbers 247 and 2249 may be simply found by the program written for the easy input. Thus the answer will be something of the form ( expression for 247 )! + ( expression for 2249 )!