Canonical Coin System Test (2) X59495
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 3 1 18 29 7 1 8 13 21 22 33 50 4 1 22 31 55 9 1 15 29 35 37 48 58 77 88 3 1 8 22 5 1 13 29 36 55 8 1 9 27 49 56 78 82 97 6 1 14 16 18 42 58 4 1 6 21 22 9 1 4 27 34 50 73 94 115 131 3 1 21 40 5 1 5 28 40 56 9 1 8 21 45 48 67 73 96 105 5 1 19 42 57 76 9 1 20 41 62 75 95 102 112 123 4 1 23 40 64 7 1 25 35 48 50 69 93 9 1 9 13 20 24 41 50 65 81 4 1 25 39 54 8 1 24 29 36 40 48 64 70 3 1 6 15 6 1 6 16 18 19 24 3 1 16 20 4 1 14 16 18 8 1 23 45 59 60 78 80 89
Output
36 proves that 1 18 29 is not canonical 16 proves that 1 8 13 21 22 33 50 is not canonical 44 proves that 1 22 31 55 is not canonical 44 proves that 1 15 29 35 37 48 58 77 88 is not canonical 1 8 22 is canonical 39 proves that 1 13 29 36 55 is not canonical 54 proves that 1 9 27 49 56 78 82 97 is not canonical 28 proves that 1 14 16 18 42 58 is not canonical 27 proves that 1 6 21 22 is not canonical 61 proves that 1 4 27 34 50 73 94 115 131 is not canonical 42 proves that 1 21 40 is not canonical 68 proves that 1 5 28 40 56 is not canonical 24 proves that 1 8 21 45 48 67 73 96 105 is not canonical 61 proves that 1 19 42 57 76 is not canonical 60 proves that 1 20 41 62 75 95 102 112 123 is not canonical 46 proves that 1 23 40 64 is not canonical 60 proves that 1 25 35 48 50 69 93 is not canonical 18 proves that 1 9 13 20 24 41 50 65 81 is not canonical 50 proves that 1 25 39 54 is not canonical 53 proves that 1 24 29 36 40 48 64 70 is not canonical 18 proves that 1 6 15 is not canonical 22 proves that 1 6 16 18 19 24 is not canonical 32 proves that 1 16 20 is not canonical 28 proves that 1 14 16 18 is not canonical 68 proves that 1 23 45 59 60 78 80 89 is not canonical
- Author
- José Luis Balcázar
- Language
- English
- Translator
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- Python
- User solutions