Esspe-Peasee
Time limit1sMemory limit128 MB
For each triple (foom, foob, twob), find non-negative counts A and B with the fewest total coins so that A*foom + B*foob equals twob.
- Level
Medium6 of 10
- Topics
- Math, Number theory, Brute force, Implementation
- Solved
- No attempts yet
Problem
Esspe-Peasee is an ancient game played by children throughout the land of Acmania. The rules are simple.
A player quibs the yorba at the kwonk. If the yorba hurms the kwonk, the player earns a foom; if the yorba hurfs the kwonk, the player earns a foob. The objective is to assemble a twob using as few quibs as possible.
Every group of children has its own opinion about the value of a foom, the value of a foob, and the value of a twob. Everyone agrees, however, that a foob is worth more than a foom, and that a twob is worth more than a foob. A foom and a foob each fit in a 32-bit integer, and a twob fits in a 64-bit integer.
Each quib yields exactly one foom or one foob, so if you collect fooms and foobs you have spent quibs and accumulated a value of . You want this total to equal the value of a twob while using the fewest quibs, that is, while minimising .
Input
You will be given several game instances. Each instance is a single line with three non-negative integers: the value of a foom, the value of a foob, and the value of a twob, in that order. Input ends with a line containing three zeros (0 0 0), which must not be processed.
Output
For each instance, print a single line A fooms and B foobs for a twob!, where fooms plus foobs add up to exactly one twob and is as small as possible. Pluralise the words correctly: write foom / foob when the count is exactly , and fooms / foobs otherwise (including a count of ).
If no such pair of non-negative counts exists, print the age-old chant instead: Unquibable!