同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21240_GeorgeLucasand1138

2022-5-16 18:19| 发布者: Hocassian| 查看: 36| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-8950550909999-Problem List-采集的数据-后羿采集器.html

Pro.ID

21240

Title

George Lucas and 1138

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21240

AC

Submit

Ratio

时间&空间限制

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

描述

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)/4is, 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.

输出

Description

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)/4is, 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).

Input

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.

Output

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.

Sample Input

Sample Output

Source

Pacific NW 2009

样例输入

样例输出

提示