Der Kassiereralgorithmus ist ein Algorithmus zum Ändern der Mindestanzahl von Münzen, der für die meisten Währungssysteme recht gut geeignet ist. Wie die meisten gierigen Algorithmen ist es jedoch nicht ohne Mängel. Wenn ein Währungssystem nur richtig (oder nur falsch) eingerichtet ist, gibt es bestimmte Werte, bei denen der Algorithmus des Kassierers die optimale Änderung nicht findet.

Nehmen Sie das folgende Beispiel:

Wir haben 4, 3 und 1 Münzen. Wir wollen 6 ¢ machen.

Der Kassiereralgorithmus wählt zunächst so viele der größten Münzen aus (eine 4 ¢ zum Starten) und subtrahiert und wiederholt diese. Dies ergibt eine 4 ¢ Münze und zwei 1 ¢ Münzen für insgesamt 3 Münzen.

Leider gibt es für den Algorithmus eine Möglichkeit, mit nur zwei Münzen 6 ¢ zu machen (zwei 3 ¢ Münzen).

Ein Änderungssystem wird als kanonisch betrachtet, wenn der Algorithmus des Kassierers für alle ganzzahligen Werte die optimale Anzahl von Münzen findet.

Aufgabe

Ihre Aufgabe besteht darin, ein System als ungeordneten Container oder sortierten Container mit ganzen Zahlen zu betrachten, die Münzwerte darstellen, und einen Wahrheitswert auszugeben, wenn die Systemeingabe kanonisch und ansonsten falsch ist.

Ihr Programm sollte für alle Systeme funktionieren, die einen beliebigen Wert erzeugen können. (dh alle Systeme haben eine 1 ¢ Münze)

Das ist Code Golf Least Bytes Wins.

Testfälle

Diese Liste ist keineswegs vollständig, Ihr Programm sollte für alle gültigen Eingaben funktionieren

1, 3, 4       -> 0
1, 5, 10, 25  -> 1
1, 6, 10, 25  -> 0
1, 2, 3       -> 1
1, 8, 17, 30  -> 0
1, 3, 8, 12   -> 0
1, 2, 8, 13   -> 0
1, 2, 4, 6, 8 -> 1

Haskell, 94 87 82 Bytes

f s=and[j i-2<j(i-x)|let j i=last$0:[1+j(i-x)|x<-s,x<i],i<-[1..2*last s],x<-s,x<i]

Bei dieser Lösung wird eine Funktion definiert j, die den Algorithmus des Kassierers ausführt und angibt, wie viele Münzen der Kassierer verwendet hat. Wir überprüfen dann bis zu zweimal die größte Zahl in der Liste, vorausgesetzt, das System ist für alle vorherigen Zahlen kanonisch und es ist die richtige Wahl, die größtmögliche Münze zu nehmen.

Diese Lösung setzt voraus, dass die Eingabe sortiert ist.

Proof-Checking bis zum Doppelten der größten Zahl ist ausreichend: Nehmen Sie an, dass das System für eine bestimmte Zahl nicht kanonisch ist i, und lassen Sie kdie größte Zahl in der Liste nicht größer als sein i. davon ausgehen, i >= 2kund das System ist kanonisch für alle Zahlen kleiner als i.

Gehe idavon aus, dass die Münze keine Münze enthält k. Wenn wir eine der Münzen wegwerfen, muss die neue Münzsumme größer kund kleiner sein als i- aber der Kassiereralgorithmus für diese Zahl würde die kMünze verwenden -, und daher kann dieser Münzsatz durch einen gleichen Münzsatz ersetzt werden enthält die Münze k, und daher gibt es eine Reihe von Münzen, die die Münze kfür die Zahl enthalten i, und durch Induktion gibt der Algorithmus des Kassierers die optimale Auswahl zurück.

Dieses Argument zeigt wirklich, dass wir nur die Summe der beiden größten Elemente prüfen müssen - aber es ist länger, dies zu tun.

Edit: fünf Bytes weniger dank Ørjan Johansen!

Pyth, 18 15 Bytes

!x#eST.gsky_S*e

Testsuite

Eine andere Art von roher Gewalt. Dies beginnt mit der Bildung aller Münzsammlungen mit jeweils bis zu k, wobei k die größte Münze ist, die als letzte Münze angenommen wird. Ich glaube, dies reicht immer aus, um zwei Sätze Münzen mit der gleichen Summe zu bilden, einen gierigen und einen kürzeren, wenn ein solches Paar existiert.

Ich finde dann so ein Paar wie folgt:

Die Teilmengen werden in aufsteigender Reihenfolge und lexikografisch nach sekundärer Position in der Eingabe generiert. Gruppieren Sie die Münzsammlungen stabil nach ihren Summen. Jede Münzsammlung wird in absteigender Reihenfolge generiert, sodass die gierige Lösung genau dann das erste Element der Gruppe ist, wenn die gierige Lösung optimal ist, und lexikografisch das letzte Element der Gruppe. So finden wir die gierige Lösung und filtern nach einem Index ungleich Null in der Gruppe. Wenn der Münzsatz kanonisch ist, wird dadurch alles herausgefiltert, sodass wir das Ergebnis und die Ausgabe einfach logisch negieren.

Erläuterung:

!x#eST.gsky_S*e
!x#eST.gsky_S*eQQ   Variable introduction.
                    Q = eval(input()) - sorted list of coins.
              eQ    Greatest coin in the list
             *  Q   Repeat that many times.
            S       Sort the coins
           _        Reverse, so we have the coins in descending order.
          y         Form all subsets, in increasing size then
                    decreasing lexicographic order.
      .gsk          Group by sum
 x#                 Filter by the index in the group of
   eST              The last element lexicographically (greedy solution).
!                   Logically negate.

PHP, 323 Bytes

Wie die anderen zählen auch Sie die Münzen bis zur Summe der beiden letzten Elemente im Array

<?function t($g){rsort($g);$m=array_slice($g,1);for($y=1,$i=$g[0];$i<$g[0]+$m[0];$i++){$a=$b=$i;$p=0;$r=$s=[];while($a||$b){$o=$n=0;$g[$p]<=$a?$a-=$r[]=$g[$p]:$o=1;($m[$p]??1)<=$b?$b-=$s[]=$m[$p]:$n=1;$p+=$o*$n;}$y*=count($r)<=count($s);}return$y;}for($i=0,$t=1;++$i<count($a=$_GET[a]);)$t*=t(array_slice($a,0,$i+1));echo$t;

Meine beste und längste Antwort glaube ich> 370 Bytes

Ich gebe nur eine erweiterte Version an, da diese länger ist als meine Antwort zuvor

for($x=1,$n=0,$f=[];++$n<count($a)-1;){
$z=array_slice($a,0,$n+1);
$q=$a[$n]-$a[$n-1];
$i=array_fill(1,$c=max($a[$n+1]??1,11),"X");#$q*$a[$n]
$f=range($a[$n],$c,$q);

$f[]=2*$a[$n];
for($d=[$z[$n]],$j=0;$j<$n;){
   $f[]=$a[$n]+$d[]=$z[$n]-$z[$j++]; 
}

while($f){
    $i[$t=array_pop($f)]="T";
    foreach($d as $g)
    if(($l=$t+$g)<=$c)$f[]=$l;
}

foreach($i as$k=>$v){
    if(in_array($k,$z))$i[$k]="S";
}
#var_dump($i);
if($i[$a[$n+1]]=="X")$x*=0;
}
echo$x;

Erklärung für diese Antwort

Online Version

1. Setzen Sie all im Array auf false == X

2. Stellen Sie alle Zahlen in dem Array, das Sie steuern, auf S ein

3. Gefundene Unterschiede zwischen dem letzten S und dem anderen S oder 0

4. Beginnen Sie zuletzt mit S im Array

5. Setze alle Zahlen auf D Where Last S + einer aller Unterschiede

6. Beginnen Sie überhaupt D

7. Setzen Sie "T" auf D-Werte im Array

8. GOTO 5 Wiederhole es mit allen gefundenen DI hab es nicht wirklich im Code

9. Wenn das nächste Element im Array X enthält, ist dies ein falscher Fall, ansonsten True

Zusätzliche Schritte Unterschied ist in dem Fall in dem Snippet 3 Zwischen 1 und 4 sind 2 X Dies bedeutet, dass Sie das zweite D von Schritt 5 benötigen. Nachdem dieser Wert in diesem Fall 10 alle Fälle wahr sind, konnte ich soweit sehen, dass es eine Beziehung gibt zwischen der Differenz und der Anzahl in dem Array, das Sie steuern, um zu berechnen, wie viel D (Schritt 5) Sie benötigen, um den Punkt zu erhalten, bevor Sie den letzten falschen Fall finden.

Sie setzen mehrere Werte vom letzten Element direkt auf true. Diese Punkte können einen Unterschied machen, um zu entscheiden, ob die Anzahl der gierigen Münzen mit dem nächsten Wert gleich dem Vielfachen des letzten im Array ist. Auf dem anderen Weg können Sie den Feind setzen

1. Setze den ersten Gegner auf 1 + Last S

2. Fügen Sie von diesem Punkt an jeden Wert im Array hinzu, um die nächsten Feinde festzulegen

3. Beginne mit dem letzten Feind Springe zu 2

Wenn Sie jetzt Feinde und wahre Fälle haben, steigt die Wahrscheinlichkeit, dass die Zählungen gleich sein können. Mit mehr D sinkt die Wahrscheinlichkeit.

table{width:80%}
td,th{width:45%;border:1px solid blue;}

<table>
  <caption>Working [1,4]</caption>
<tr><th>Number</th><th>Status</th></tr>
<tr><td>1</td><td>S</td></tr>
<tr><td>2</td><td>X</td></tr>
<tr><td>3</td><td>X</td></tr>
<tr><td>4</td><td>S</td></tr>
<tr><td>5</td><td>X</td></tr>
<tr><td>6</td><td>X</td></tr>
<tr><td>7</td><td>D3</td></tr>
<tr><td>8</td><td>D4</td></tr>
<tr><td>9</td><td>X</td></tr>
<tr><td>10</td><td>D3D3</td></tr>
<tr><td>11</td><td>D4D3</td></tr>
<tr><td>12</td><td>D4D4</td></tr>
<tr><td>13</td><td>D3D3D3</td></tr>
<tr><td>14</td><td>D4D3D3</td></tr>
<tr><td>15</td><td>D4D4D4</td></tr>
<tr><td>16</td><td>D4D4D3</td></tr>
</table>
<ul>
  <li>S Number in Array</li>
  <li>D Start|End point TRUE sum Differences from last S</li>
  <li>X False</li>
  </ul>

Plus ? Bytes Vielen Dank an JonathanAllan, der mir falsche Testfälle gegeben hat.
262 Bytes Fast, aber nicht gut genug. 4 falsche Testfälle im Moment

Testfälle [1,16,256] zuvor sollten wahr nach falsch sein

<?for($q=[1],$i=0,$t=1,$w=[0,1];++$i<count($a=$_GET[v]);$w[]=$a[$i],$q[]=$m)($x=$a[$i]-$a[$i-1])>=($y=$a[$i-1]-$a[$i-2])&&((($x)%2)==(($m=(($a[$i]+$x)*$a[$i-1])%$a[$i])%2)&&$m>array_sum($q)||(($x)%2)==0&&(($a[$i]-$a[$i-2])*2%$y)==0||in_array($m,$w))?:$t=0;echo$t;

Aufsteigende Reihenfolge des Arrays

Erläuterung

for($q=[1],$i=0,$t=1,$w=[0,1] # $t true case $q array for modulos $w checke values in the array
;++$i<count($a=$_GET[v])   #before loop
;$w[]=$a[$i],$q[]=$m) # after loop $q get the modulo from the result and fill $w with the checked value

($x=$a[$i]-$a[$i-1])>=($y=$a[$i-1]-$a[$i-2]) 
# First condition difference between $a[i] and $a[$i-1] is greater or equal $a[$i-1] and $a[$i-2]
# if $a[$-1] == 1 $a[$i-2] will be interpreted as 0
&&  ## AND Operator with the second condition
(
(($x)%2)==   # See if the difference is even or odd
(($m=(($a[$i]+$x)*$a[$i-1])%$a[$i])%2)&&$m>array_sum($q)
# After that we multiply the result with the lower value *$a[$i-1]
    # for this result we calculate the modulo of the result with the greater value %$a[$i]
    # if the difference and the modulo are both even or odd this belongs to true
# and the modulo of the result must be greater as the sum of these before
    # Ask me not why I have make try and error in an excel sheet till I see this relation
||
(($x)%2)==0&&(($a[$i]-$a[$i-2])*2%$y)==0 # or differce modulator is even and difference $a[$i],$a[$i-1] is a multiple of half difference $a[$i-1],$a[$i-2] 
||
in_array($m,$w) # if the modulo result is equal to the values that we have check till this moment in the array we can also neglect the comparison
)
?:$t=0; # other cases belongs to false
echo$t; #Output

Es sieht so aus, als ob das, was ich in der Tabelle gesehen habe, Werte von [1,2,3,4,5,6] enthält und ich ändere nur das letzte Element bis 9. Für 2to3 und 4to5 erstellen wir den Wert des niedrigeren Werts in der Tabelle Modulo-Berechnung

table{width:95%;}th,td{border:1px solid}

<table><tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>35</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><th></th><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>2</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>7</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>45</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>3</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><th></th><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>3</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>8</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>55</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>7</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><th></th><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>4</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>9</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>65</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>2</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td></tr></table>

JavaScript (ES6), 116 125 130

l=>eval("r=(d,k)=>d?--k&&l.map(v=>v>d||r(d-v,k)):x=1;for(x=l[0]*2;--x>1;r(x,g))g=0,h=x,l.map(v=>(g+=h/v|0,h%=v));x")

Hierfür muss das Eingabearray in absteigender Reihenfolge sortiert sein. Für jeden Wert von 2N bis 2 (N ist der maximale Münzwert) wird die Anzahl der Münzen aus dem Greedy-Algorithmus ermittelt, und es wird versucht, einen kleineren Satz von Münzen zu finden.

Weniger golfen

l=>{
  // recursive function to to find a smaller set of coins
  // parameter k is the max coin limit
  r = (d,k) => d // check if difference is not 0
     ? --k // if not, and if the number of coins used will be less than limit
      && l.map(v => v>d || r(d-v, k))  // proceed with the recursive search
     : x=1 // if diff is 0, value found, set x to 1 to stop the loop
  for( x=l[0]*2; --x > 1; )  
    g=0, h=x, l.map(v=>(g += h/v|0, h %= v)), // find g with the greedy algorithm
    r(x,g) // call with initial difference equal to target value
  return x
}

Prüfung

f=
l=>eval("r=(d,k)=>d?--k&&l.map(v=>v>d||r(d-v,k)):x=1;for(x=l[0]*2;--x>1;r(x,g))g=0,h=x,l.map(v=>(g+=h/v|0,h%=v));x")

/* No eval
f=l=>{
  r=(d,k)=>d?--k&&l.map(v=>v>d||r(d-v,k)):x=1;
  for(x=l[0]*2;--x>1;r(x,g))
    g=0,h=x,l.map(v=>(g+=h/v|0,h%=v));
  return x;
}*/

;[
 [[100,50,20,10,5,2,1],1], [[4,3,1],0],
 [[25,10,5,1],1], [[25,10,6,1],0],
 [[3,2,1],1], [[30,17,8,1], 0], 
 [[12,8,3,1],0], [[13,8,2,1], 0]
].forEach(t=>{
  var i=t[0],k=t[1],r=f(i),
      msg=((r==k)?'OK ':'KO ')+i+' -> '+r
      + (r==k?'':' (should be '+k+')')
  O.textContent += msg+'\n'
})

function test()
{
  var i=I.value.match(/\d+/g).map(x=>+x).sort((a,b)=>b-a)
  O.textContent = i+' -> '+f(i)+'\n'+O.textContent
 }

#I { width:50% }

<input id=I value='1 4 9'><button onclick='test()'>test</button>
<pre id=O></pre>

Python, 218 211 205 Bytes

-1 Byte dank @TuukkaX (ein Leerzeichen könnte zwischen <3und gelöscht werden or)

from itertools import*
g=lambda x,c,n=0:x and g(x-[v for v in c if v<=x][0],c,n+1)or n
lambda c:len(c)<3or 1-any(any(any(x==sum(p)for p in combinations(c*i,i))for i in range(g(x,c)))for x in range(c[0]*2))

repl.it

Eingabe in absteigender Reihenfolge.

Schrecklich rohe Gewalt. Jeder Satz einer Münzeinheit und einer anderen Münze ist kanonisch. Bei größeren Sätzen ist der kleinste Fehlerfall, wenn einer existiert, größer oder gleich der drittkleinsten Münze (ich weiß nicht, wie er gleich sein könnte!) Und kleiner als die Summe der beiden größten Münzen - siehe dieses Papier (welches tatsächlich existiert) verweist auf eine andere, gibt aber auch eine O (n ^ 3) -Methode an.

g zählt die Münzen, die von der gierigen Methode verwendet werden, und die unbenannte Funktion durchläuft die möglichen Kandidaten (tatsächlich von 0 auf eins weniger als das Doppelte der größten Münze, um Bytes zu sparen) und sucht nach einer Sammlung von weniger Münzen, die ebenfalls diesen Betrag ergeben.

garbeitet mit dem, was ein Kassierer tun würde, nimmt er rekursiv die größte Münze, die kleiner oder gleich dem Betrag ist, der noch aufzufüllen ist, [v for v in c if v<=x][0]weg und zählt die Anzahl der verwendeten Münzen auf n.

Die unbenannte Funktion gibt 1 zurück, wenn len(c)kleiner als 3 ist, und prüft ansonsten, ob dies nicht der Fall ist 1-...und ob Werte im Bereich der Möglichkeiten range(c[0]*2)))mit weniger Münzen möglich sind i in range(g(x,c)), indem von jeder Münze eine Sammlung von so vielen Münzen erstellt wird. c*iund Untersuchen aller Münzkombinationen, um ifestzustellen, combinations(c*i,i)ob eine Summe denselben Wert aufweist.

Jelly ( Gabel ), 15 bis 14 Bytes

SRæFµS€Ṃ=$Ṫµ€Ȧ

Diese Lösung verwendet die Grenzen für Gegenbeispiele aus diesem Artikel . Dort verwendet der Autor eine enge Grenze für das Gegenbeispiel, aber im Interesse des Golfspiels wird der Bereich der Summe der Münzwerte verwendet, der größer ist und diese Grenze enthält.

Dieses Programm berechnet alle Testfälle in weniger als einer Sekunde auf meinem Computer.

Leider basiert dies auf einem Zweig von Jelly, in dem ich an der Implementierung eines Frobenius-Lösungsatoms gearbeitet habe, sodass Sie es nicht online ausprobieren können.

Verwendungszweck

$ ./jelly eun 'SRæFµS€Ṃ=$Ṫµ€Ȧ' '1,2,4,6,8'
1

Die Leistung ist gut und kann alle Testfälle auf einmal in weniger als einer Sekunde lösen.

$ time ./jelly eun 'SRæFµS€Ṃ=$Ṫµ€Ȧ¶Ç€' '[[1,3,4],[1,5,10,25],[1,6,10,25],[1,2,3],[1,8,17,30],[1,3,8,12],[1,2,8,13],[1,2,4,6,8]]'
[0, 1, 0, 1, 0, 0, 0, 1]

real    0m0.793s
user    0m0.748s
sys     0m0.045s

Erläuterung

SRæFµS€Ṃ=$Ṫµ€Ȧ  Input: list of integers C
    µ           Start a new monadic chain
S                 Sum
 R                Range, [1, 2, ..., sum(C)]
  æF              Frobenius solve for each X in the range using coefficients from C
                  This generates all vectors where the dot product of a
                  vector with C equals X, ordered by using values from the
                  start to end of C
           µ€   Start a new monadic chain that operates on each list of vectors
     S€           Sum each vector
         $        Monadic hook on the sums
       Ṃ            Minimum (This is the optimal solution)
        =           Vectorized equals, 1 if true else 0
          Ṫ       Tail (This is at the index of the greedy solution)
             Ȧ  All, returns 0 if it contains a falsey value, else 1

JavaScript (ES6), 144 132 124 122 110 Byte

a=>![...Array(a[0]*2)].some((_,i)=>(g=(a,l=0,n=i)=>[a.filter(c=>c>n||(l+=n/c|0,n%=c,0)),-l*!n])(...g(a))[1]>0)

Erfordert, dass das Array in absteigender Reihenfolge sortiert wird. Verwendet die Beobachtung in dem verlinkten Artikel, dass es, wenn das System nicht kanonisch ist, mindestens einen Wert unter 2a [0] gibt, der weniger Münzen benötigt, wenn er unter Verwendung der nicht verwendeten Münzen aus dem anfänglichen gierigen Algorithmus zerlegt wird.

Bearbeiten: 12 Bytes gespart, indem erkannt wurde, dass ich alle Münzen überprüfen konnte, obwohl ich den Zielwert bereits erreicht hatte. 8 Bytes gespart durch Umschalten der Zwischenausgabe von [l,b]auf [b,-l]; Dies erlaubte mir, das erste Ergebnis direkt als Parameter des zweiten Aufrufs zu übergeben, sowie eine kleine Speicherung, die feststellte, ob der zweite Aufruf erfolgreich war. Durch Verschieben der Definition von gin den someRückruf wurden 2 Bytes gespart , sodass ich die Schleifenvariable nicht unnötig zweimal übergeben musste. 12 Bytes gespart, indem ich von meiner rekursiven Hilfsfunktion auf einen Aufruf von umgeschaltet habe filter(möglich durch meine Zwischenausgangsumschaltung).

Perl, 69 Bytes

Beinhaltet +2 für -pa

Geben Sie die Münzen in absteigender Reihenfolge auf STDIN. Optional können Sie die 1Münze weglassen.

coins.pl <<< "4 3 1"

coins.pl:

#!/usr/bin/perl -pa
$_=!map{grep$`>=$_&&($n=$G[$`-$_]+1)<($G[$`]||=$n),@F,/$/}1..2*"@F"

Bildet die Anzahl der vom Kassierer-Algorithmus verwendeten Münzen in @GBeträgen von 1 bis zum Zweifachen der größten Münze. Für jeden Betrag wird geprüft, ob der Kassenalgorithmus höchstens 1 Münze weniger benötigt, wenn dieser Betrag um 1 Münze verringert wird. Wenn nicht, ist dies ein Gegenbeispiel (oder es gab ein früheres Gegenbeispiel). Ich könnte beim ersten Gegenbeispiel aufhören, aber das braucht mehr Bytes. So ist die zeitliche Komplexität O(max_coin * coins)und die räumliche KomplexitätO(max_coin)