Sistemes monetaris canònics (2) X59495
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à.
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
- Catalan
- Other languages
- English
- Official solutions
- Python
- User solutions