Stamps
Time limit1sMemory limit128 MB
For each set of stamp denominations, decide if every large postage is payable without the 1-lar stamp and give the largest postage that still needs it.
- Level
Medium7 of 10
- Topics
- Shortest path, Number theory
- Solved
- No attempts yet
Problem
Far away in Azeland the stamps have become a problem. Inflation has been fierce, and with the old denominations of 1, 5 and 12 lars there is no longer room on most letters to write the address once the stamps are on. A government commission now has to pick a new set of denominations.
The commission plans to keep the 1 lar stamp for historical reasons, but it turned up an obscure clause in the postal legislation: every "sufficiently large" amount of postage must be payable without the 1 lar stamp.
A mathematician at the university of Ogato told the commission that the requirement is met whenever the remaining denominations have no common factor larger than 1. He also said that in that case no simple formula is known for how large "sufficiently large" has to be.
To compare the competing proposals, the commission wants to know whether a set of denominations is acceptable at all, and if it is, the largest amount of postage that really does need the 1 lar stamp.
Denominations of 9, 12 and 15 are unacceptable, because all three are multiples of 3. Denominations of 4 and 7 are acceptable, and the largest postage that needs the 1 lar stamp is then 17 lar.
Input
The input holds several proposed sets of denominations, one set per line. The 1 lar stamp is omitted from the list. Each denomination is between 2 and 10,000 lar inclusive, and a set holds at most 10 denominations.
A line that begins with 0 ends the input.
Output
Print one line per set. If the set is not acceptable, print Unacceptable. Otherwise print a single positive integer: the largest value that cannot be made from those denominations, that is, the largest value that needs a 1 lar stamp.