Canonical Coin System Test (2) X96809
Most coin systems currently or recently in use are canonical. This means that the greedy algorithm to reach a quantity always gives an optimal number of coins. Different systems such as dollars, euros, and also XX century pre-euro coins such as pesetas and Dutch Gulden, all have this property. However, not all coin systems have this property. The UK pound sterling system prior to Monday 15 February 1971 (see https://en.wikipedia.org/wiki/Decimal_Day) was a far cry from canonical. As a simpler example, with coins of 1, 5, and 8 units the greedy strategy fails to produce an optimal configuration to add up to 15; we say that this value is a counterexample to the canonicity of the system.
In 1993, Dexter Kozen and Shmuel Zaks proved mathematically that, if a system is not canonical, then a counterexample exists that is less than the sum of the two largest values in the system. This fact will allow you to distinguish canonical systems (but note that in later years more efficient algorithms were found).
Input
The input contains several cases of coin systems to test for canonicity. First, the input indicates the total number of cases, a non-negative integer n. Then, n cases follow: each case starts with m, a positive integer indicating the number of denominations, with m positive integers ordered increasingly corresponding to the denominations. The smallest denomination will always be 1 (coin systems lacking a 1-unit coin are never considered in the general literature, as they don’t allow one to pay a quantity of 1 unit).
Output
For each case, print a line. If the case is a canonical coin system, print the denominations of the case in ascending order followed by the words "is canonical" . If it is not, print the smallest counterexample, then the words "proves that", then the denominations of the case in ascending order, then the words "is not canonical".
Observation
Slow solutions are unlikely to get accepted here. The companion problem X24976 asks for a solution of the same problem; the reference solution there, though, is somewhat "sluggish", so relatively slower solutions that fail here may get accepted in that alternative problem.
Input
7 4 1 5 10 25 8 1 2 5 10 20 50 100 200 3 1 5 8 6 1 5 10 25 50 100 1 1 7 1 2 4 5 10 40 42 3 1 29 493
Output
1 5 10 25 is canonical 1 2 5 10 20 50 100 200 is canonical 10 proves that 1 5 8 is not canonical 1 5 10 25 50 100 is canonical 1 is canonical 8 proves that 1 2 4 5 10 40 42 is not canonical 1 29 493 is canonical
Input
2 7 1 2 5 10 20 50 100 6 1 2 5 10 25 50
Output
1 2 5 10 20 50 100 is canonical 1 2 5 10 25 50 is canonical
Input
0
Output
Input
25 7 1 11 30 34 46 56 78 4 1 23 26 41 4 1 12 31 50 9 1 6 18 32 55 63 87 97 121 6 1 22 29 53 65 71 2 1 2 8 1 5 8 26 35 45 59 63 6 1 18 41 50 69 84 4 1 22 44 64 2 1 17 5 1 13 36 45 52 8 1 5 12 29 43 46 69 84 7 1 15 17 39 56 60 84 5 1 5 9 20 29 6 1 18 25 48 64 85 5 1 7 23 33 37 2 1 10 4 1 5 29 41 5 1 3 4 5 27 7 1 19 32 36 49 58 66 8 1 14 32 48 60 82 104 117 4 1 9 24 40 9 1 17 40 50 66 71 90 102 109 8 1 9 18 20 29 45 68 76 9 1 20 44 54 77 93 113 120 131
Output
33 proves that 1 11 30 34 46 56 78 is not canonical 46 proves that 1 23 26 41 is not canonical 36 proves that 1 12 31 50 is not canonical 36 proves that 1 6 18 32 55 63 87 97 121 is not canonical 44 proves that 1 22 29 53 65 71 is not canonical 1 2 is canonical 10 proves that 1 5 8 26 35 45 59 63 is not canonical 54 proves that 1 18 41 50 69 84 is not canonical 66 proves that 1 22 44 64 is not canonical 1 17 is canonical 39 proves that 1 13 36 45 52 is not canonical 15 proves that 1 5 12 29 43 46 69 84 is not canonical 30 proves that 1 15 17 39 56 60 84 is not canonical 23 proves that 1 5 9 20 29 is not canonical 36 proves that 1 18 25 48 64 85 is not canonical 28 proves that 1 7 23 33 37 is not canonical 1 10 is canonical 58 proves that 1 5 29 41 is not canonical 7 proves that 1 3 4 5 27 is not canonical 38 proves that 1 19 32 36 49 58 66 is not canonical 42 proves that 1 14 32 48 60 82 104 117 is not canonical 27 proves that 1 9 24 40 is not canonical 57 proves that 1 17 40 50 66 71 90 102 109 is not canonical 27 proves that 1 9 18 20 29 45 68 76 is not canonical 60 proves that 1 20 44 54 77 93 113 120 131 is not canonical
- Author
- José Luis Balcázar
- Language
- English
- Translator
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- Python
- User solutions