Sistemes monetaris canònics (1) X24976

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ó

La solució de referència d’aquest problema no és massa sofisticada. Programes no massa eficients poden resultar potser acceptats. A l’exercici "germà" X88410, que demana resoldre el mateix poblema, cal una solució prou eficient per poder resultar acceptada.