|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||128 MB||16||4||2||100.000%|
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.
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.
1138 12345 13555 167283 123458 4321678 0
29 76 56 524 347 1774