Problem G
Cafeteria
Theta likes to play Lure of the Labyrinth, which is an online game that uses a compelling graphic novel storyline to engage middle grades students in mathematical thinking and problem-solving. To find lost pets, students have to infiltrate a world of monsters and solve puzzles! Implemented by a professional game studio, these puzzles are quite engaging and challenging.
In the manager’s cafeteria, students are asked to practice proportions by serving $5$ monsters sitting at the table: Salamander, Yeti, Golem, Imp, and Kraken. Each monster wants some amount of burger, slop, sushi, and drumstick.
The amount of each item each monster wants on their plate is proportional to the amount of each of the other items that monster wants, and the proportionality ratio is the same for all monsters.
For instance, as shown in sample input $1$ and in the accompanying figure, if Golem (center) wants $6$ units of burger on his plate and $12$ units of drumstick, and Salamander (left) wants $40$ units of drumstick, then Salamander will want $20$ units of burger. Students practicing proportions will program the dispenser machine to release $20$ units of burger. Similarly, Kraken (right) wants $36$ units of drumstick because it has $81$ units of slop on its plate and Salamander has $40$ units of drumstick and $90$ units of slop. If the students compute all proportions in time, the monsters eat and a pet can be saved!
As students progress in the game and reach more difficult levels, fewer and fewer amounts are given, requiring more intuition and thinking to solve the puzzle.
Give a set of partially filled plates, write a program that computes the number of distinct solutions that are consistent with it!
Input
The input consists of $2$ lines of $10$ entries each describing the partially filled plates. The first line describes the top row (burgers and slop), the second line describes the bottom row (sushi and drumstick). On each line, the first $2$ entries describe Salamander’s plate, the next $2$ Yeti’s, then Golem’s, Imp’s, and finally Kraken’s. Each entry is either the underscore character _ describing an empty slot or a positive integer number $a$ ($0 < a \le 200$) if it is already known. Entries are separated by single spaces. You may assume that each arrangement has at least one possible solution (that is, the partial information is not inconsistent).
Output
Output the number $n$ of distinct solutions for the puzzle given in the input! If there are infinitely many solutions, output “many”! Note that although any given entries are guaranteed to be less than $200$, inferred entries must be positive integers, but they are not subject to a maximum.
| Sample Input 1 | Sample Output 1 |
|---|---|
_ 90 22 _ 6 _ _ _ _ 81 _ 40 _ _ _ 12 60 _ 90 _ |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
85 55 _ 99 51 _ _ _ _ _ _ _ _ _ _ _ _ 85 63 153 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
160 _ _ 136 _ _ _ _ _ 170 _ _ _ _ 120 _ _ 144 _ _ |
8640 |
| Sample Input 4 | Sample Output 4 |
|---|---|
36 99 _ 55 _ 99 _ 77 _ _ _ 144 _ _ 27 _ 21 112 _ _ |
many |
