Sistemes monetaris canònics (2) X47908

Statement

thehtml

Gairebé tots els sistemes de monedes que es fan servir són canònics: això vol dir que l’algoritme greedy per assolir una quantitat, és a dir, fer servir cada vegada la més alta denominació possible, proporciona sempre el mínim nombre de monedes.

Dòlars, euros, i els sistemes europeus abans de l’euro com ara pessetes o gulden holandesos, tenen aquesta propietat. Tanmateix, no sempre és així. Les lliures esterlines d’UK, abans del canvi fet el 15 de febrer de 1971, estaven molt lluny de ser un sistema canònic (veure https://en.wikipedia.org/wiki/Decimal_Day). Com a exemple senzill, amb monedes d’1 unitat, 5 unitats i 8 unitats, l’estratègia greedy no condueix a una configuració òptima per sumar 15 unitats: hi tria primer 8, llavors 5, i li calen dos 1’s, quan amb tres 5’s hi ha prou; diem que aquest valor 15 és un contraexemple a la canonicitat del sistema.

El 1993, Dexter Kozen and Shmuel Zaks van provar matemàticament que, si un sistema no és canònic, aleshores hi ha un contraexemple per sota de la suma de les dues denominacions més altes del sistema. Amb això, podràs distingir sistemes canònics (encara que posteriorment s’han trobat algoritmes més eficients).

Entrada

El programa rebrà primer un enter no negatiu n indicant quants casos hi ha. Desprès hi haurà n casos. Cada cas comença amb m, un enter positiu que diu quantes denominacions diferentes de monedes té el sistema, seguit de les denominacions: m enters positius ordenats ascendentment i on la denominació més petita sempre serà 1 (altrament, la quantitat 1 no es pot assolir).

Sortida

Per cada cas, el programa ha d’escriure una línia. Si el cas és un sistema canònic, escriu les denominacions del cas en ordre ascendent seguides de les paraules "is canonical". Si no ho és, escriu el contraexemple més petit, les paraules "proves that", les denominacions del cas en ordre ascendent, i les paraules "is not canonical".

Observació

Solucions poc eficients tindran poques possibilitats de ser acceptades ací. A l’exercici "germà" X24976, que demana resoldre el mateix poblema, la solució de referència és més lenta i solucions relativament lentes poden resultar acceptades enllà.

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
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

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

Information

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