4477번 - George Lucas and 1138 다국어

It’s well known in Star Wars culture that George Lucas was preoccupied with the number 1138. THX 1138 is the title of his first movie, and—according to Wookieepedia: The Star Wars Wiki—George Lucas liked to reuse key words and numbers in later films as a way of unifying all of his works.

If you’re up on your Star Wars trivia, then you know that in Episode V a prisoner was transferred from cell block 1138. In Episode II, all clone troopers have the number 1138 prominently displayed on the back of their helmets. And if you type in 1138 while viewing the Episode III DVD, you immediately advance to the scene where Yoda does some break dancing.

Less well known is the unpublished Episode Zero: The Birth of Death Kleene Star. The story begins with C3PO as a tween droid in school on his home planet of Tatooine, where he’s been instructed to determine all of the ways one can combine the numbers 1, 1, 3, and 8 using traditional +, -, *, /, and () to generate other positive numbers. He’s quick to observe that 8 / 3 / 1 – 1 generates 1, 3 / 8 + 1 + 1 generates 2,and that ( 8 / 3 + 1 ) * 1 generates 3. Within seconds, C3PO states that the smallest positive integer that can’t be generated is 29. But is C3PO correct?

Given an n digit string (1 ≤ n ≤ 7), compute all of the ways that those n digits can be combined using +, -, *, /, and parentheses, and print out the smallest positive integer that can't be generated.

For the string "12345", the numbers 1 through 75 can be generated, but the number 76 can't be. For the string "13555", the numbers 1 through 55 can be generated, but 56 can't be.

Additional Details

• You must use all of the digits, including duplicates.
• You can't combine digits using concatenation, so that 12 + 345 would *not* be relevant to the generation of all possibilities on behalf of "12345".
• Division is integer division, complete with the truncation you expect from integer division. That means that 4 * ( 5 / 4 ) is 4, not 5 (although ( 4 * 5 ) / 4 is, of course, the 5 you'd expect.)
• You must avoid division by zero and disallow it from contributing to the set of generated numbers.
• The test inputs will be such that all intermediate and final results can fit into a 32-bit integer (long).

Expect a series of digit strings, one per line. End of input will be signaled by a 0 on its very own line. Do not process this case.

You should produce one line of output to standard out for every line of input. Each line of output should be the smallest positive integer that *cannot* be generated by some arithmetic expression involving all of the digits.