Sistemes monetaris canònics (2) X64388

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
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: Catalan
Other languages: English
Official solutions: Python
User solutions