Canonical Coin System Test (2) X64388

Statement

thehtml

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.

Public test cases

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

Output

Input

25
4 1 24 35 52 
2 1 15 
4 1 8 9 31 
9 1 21 28 49 70 82 99 106 110 
8 1 16 37 50 55 58 63 72 
3 1 10 13 
2 1 5 
7 1 3 26 30 50 51 67 
9 1 7 16 19 23 31 34 58 74 
9 1 10 22 24 48 50 67 88 98 
6 1 2 19 42 56 66 
7 1 25 42 45 48 69 73 
9 1 12 36 44 49 64 73 82 86 
4 1 19 21 36 
2 1 16 
7 1 3 9 12 19 20 39 
4 1 17 34 38 
6 1 2 4 27 32 53 
2 1 19 
7 1 23 28 50 68 80 93 
9 1 3 11 15 35 57 69 79 88 
7 1 10 15 32 36 57 69 
9 1 17 34 56 66 77 96 115 131 
5 1 8 26 39 44 
8 1 13 21 25 29 37 59 77

Output

48 proves that 1 24 35 52 is not canonical
1 15 is canonical
16 proves that 1 8 9 31 is not canonical
42 proves that 1 21 28 49 70 82 99 106 110 is not canonical
48 proves that 1 16 37 50 55 58 63 72 is not canonical
20 proves that 1 10 13 is not canonical
1 5 is canonical
53 proves that 1 3 26 30 50 51 67 is not canonical
26 proves that 1 7 16 19 23 31 34 58 74 is not canonical
30 proves that 1 10 22 24 48 50 67 88 98 is not canonical
61 proves that 1 2 19 42 56 66 is not canonical
50 proves that 1 25 42 45 48 69 73 is not canonical
48 proves that 1 12 36 44 49 64 73 82 86 is not canonical
38 proves that 1 19 21 36 is not canonical
1 16 is canonical
18 proves that 1 3 9 12 19 20 39 is not canonical
51 proves that 1 17 34 38 is not canonical
59 proves that 1 2 4 27 32 53 is not canonical
1 19 is canonical
46 proves that 1 23 28 50 68 80 93 is not canonical
22 proves that 1 3 11 15 35 57 69 79 88 is not canonical
20 proves that 1 10 15 32 36 57 69 is not canonical
68 proves that 1 17 34 56 66 77 96 115 131 is not canonical
32 proves that 1 8 26 39 44 is not canonical
34 proves that 1 13 21 25 29 37 59 77 is not canonical

Input

25
4 1 24 35 52 
2 1 15 
4 1 8 9 31 
9 1 21 28 49 70 82 99 106 110 
8 1 16 37 50 55 58 63 72 
3 1 10 13 
2 1 5 
7 1 3 26 30 50 51 67 
9 1 7 16 19 23 31 34 58 74 
9 1 10 22 24 48 50 67 88 98 
6 1 2 19 42 56 66 
7 1 25 42 45 48 69 73 
9 1 12 36 44 49 64 73 82 86 
4 1 19 21 36 
2 1 16 
7 1 3 9 12 19 20 39 
4 1 17 34 38 
6 1 2 4 27 32 53 
2 1 19 
7 1 23 28 50 68 80 93 
9 1 3 11 15 35 57 69 79 88 
7 1 10 15 32 36 57 69 
9 1 17 34 56 66 77 96 115 131 
5 1 8 26 39 44 
8 1 13 21 25 29 37 59 77

Output

48 proves that 1 24 35 52 is not canonical
1 15 is canonical
16 proves that 1 8 9 31 is not canonical
42 proves that 1 21 28 49 70 82 99 106 110 is not canonical
48 proves that 1 16 37 50 55 58 63 72 is not canonical
20 proves that 1 10 13 is not canonical
1 5 is canonical
53 proves that 1 3 26 30 50 51 67 is not canonical
26 proves that 1 7 16 19 23 31 34 58 74 is not canonical
30 proves that 1 10 22 24 48 50 67 88 98 is not canonical
61 proves that 1 2 19 42 56 66 is not canonical
50 proves that 1 25 42 45 48 69 73 is not canonical
48 proves that 1 12 36 44 49 64 73 82 86 is not canonical
38 proves that 1 19 21 36 is not canonical
1 16 is canonical
18 proves that 1 3 9 12 19 20 39 is not canonical
51 proves that 1 17 34 38 is not canonical
59 proves that 1 2 4 27 32 53 is not canonical
1 19 is canonical
46 proves that 1 23 28 50 68 80 93 is not canonical
22 proves that 1 3 11 15 35 57 69 79 88 is not canonical
20 proves that 1 10 15 32 36 57 69 is not canonical
68 proves that 1 17 34 56 66 77 96 115 131 is not canonical
32 proves that 1 8 26 39 44 is not canonical
34 proves that 1 13 21 25 29 37 59 77 is not canonical

Information

Author: José Luis Balcázar
Language: English
Translator
Original language: Catalan
Other languages: Catalan
Official solutions: Python
User solutions