The Algorithm kasjera jest algorytm do dokonywania zmian w minimalnej ilości monet, który działa całkiem dobrze dla większości systemów walutowych. Jednak jak większość chciwych algorytmów nie jest pozbawiona wad. Jeśli system walutowy jest skonfigurowany właściwie (lub po prostu źle), istnieją pewne wartości, w których algorytm kasjera nie znajdzie optymalnej zmiany.

Weź następujący przykład:

Mamy monety 4 ¢, 3 ¢ i 1 ¢. Chcemy zarobić 6 centów.

Algorytm kasjera najpierw wybierze tyle monet o największej wartości (jedna 4 ¢ na początek), a następnie odejmie i powtórzy. W ten sposób powstanie jedna moneta 4 ¢ i dwie monety 1 ¢, w sumie 3 monety.

Niestety w przypadku algorytmu istnieje sposób na uzyskanie 6 centów za pomocą tylko dwóch monet (dwóch monet 3 centów).

System zmian zostanie uznany za kanoniczny iff dla wszystkich liczb całkowitych, algorytm kasjera znajdzie optymalną liczbę monet.

Zadanie

Twoim zadaniem będzie wzięcie systemu jako nieuporządkowanego kontenera lub posortowanego uporządkowanego kontenera liczb całkowitych reprezentujących wartości monet i wygenerowanie prawdziwej wartości, jeśli dane wejściowe systemu będą kanoniczne, a fałsz w przeciwnym razie.

Twój program powinien działać dla wszystkich systemów, które mogą tworzyć dowolne wartości. (tzn. wszystkie systemy będą miały monetę 1 ¢)

To kod wygrywa najmniej bajtów golfa.

Przypadki testowe

Ta lista w żadnym wypadku nie jest wyczerpująca, twój program powinien działać dla wszystkich prawidłowych danych wejściowych

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 bajtów

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]

to rozwiązanie działa poprzez zdefiniowanie funkcji, jktóra wykonuje algorytm kasjera i mówi nam, ile monet użył kasjer. następnie sprawdzamy do dwukrotności największej liczby na liście, zakładając, że system był kanoniczny dla wszystkich poprzednich liczb, że wybranie największej możliwej monety jest właściwym wyborem.

to rozwiązanie zakłada, że ​​dane wejściowe są posortowane.

wystarczy sprawdzenie dowodu do dwukrotności największej liczby: załóżmy, że dla niektórych liczb system nie jest kanoniczny ii niech kbędzie największą liczbą na liście nie większą niż i. Załóżmy, że i >= 2ki system jest kanoniczny dla wszystkich liczb mniejszych niż i.

wybierz optymalny sposób na zrobienie imonet i załóż, że nie zawiera monety k. jeśli wyrzucimy jedną z monet, nowa suma monet musi być większa ki mniejsza niż i- ale algorytm kasjera na tej liczbie użyłby kmonety - i dlatego ten zestaw monet można zastąpić takim samym zestawem monet zawierający monetę k, a zatem istnieje zestaw monet zawierających monetę kdla numeru i, a przez indukcję algorytm kasjera zwraca optymalny wybór.

ten argument naprawdę pokazuje, że musimy tylko sprawdzić sumę dwóch największych elementów - ale jest to dłuższe.

Edycja: pięć bajtów mniej dzięki Ørjan Johansen!

Pyth, 18 15 bajtów

!x#eST.gsky_S*e

Zestaw testowy

Inny rodzaj brutalnej siły. Zaczyna się to od utworzenia wszystkich kolekcji monet o wartości do k każdej z nich, gdzie k jest największą monetą, która jest uważana za ostatnią monetę. Uważam, że zawsze wystarcza to do utworzenia dwóch zestawów monet o tej samej sumie, jednego zachłannego i jednego krótszego, ilekroć taka para istnieje.

Następnie lokalizuję taką parę w następujący sposób:

Podzbiory są generowane w kolejności rosnącego rozmiaru i leksykograficznie według pozycji na wejściu wtórnie. Stabilnie pogrupuj kolekcje monet według ich sum. Każda kolekcja monet jest generowana w kolejności malejącej, więc zachłanne rozwiązanie będzie pierwszym elementem grupy tylko wtedy, gdy zachłanne rozwiązanie jest optymalne i będzie ostatnim elementem grupy leksykograficznie. Tak więc znajdujemy chciwe rozwiązanie i filtrujemy według niezerowego indeksu w grupie. Jeśli zestaw monet jest kanoniczny, wszystko zostanie odfiltrowane, więc logicznie negujemy wynik i wynik.

Wyjaśnienie:

!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 bajtów

Tak samo jak inne liczą monety, aż suma dwóch ostatnich elementów w tablicy

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

Moja najlepsza i najdłuższa odpowiedź wierzę> 370 bajtów

Daję tylko wersję rozszerzoną, ponieważ jest ona dłuższa niż moja wcześniejsza odpowiedź

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;

Wyjaśnienie tej odpowiedzi

Wersja online

1. Ustaw wszystko w tablicy na false == X

2. Ustaw wszystkie cyfry w kontrolowanej tablicy na S.

3. Znaleziono różnice między ostatnim S a drugim S lub 0

4. Zacznij od ostatniej litery S w tablicy

5. Ustaw wszystkie cyfry na D Where Last S + jedna ze wszystkich różnic

6. Rozpocznij w ogóle D

7. Ustaw „T” na wartości D w tablicy

8. GOTO 5 Powtórz to z wszystkich znalezionych DI, tak naprawdę tak naprawdę nie było w kodzie

9. Jeśli następny element w tablicy ma X, jest to fałszywy przypadek, inaczej Prawda

Dodatkowe kroki Różnica polega na tym, że we fragmencie 3 Pomiędzy 1 a 4 są 2 X Oznacza to, że potrzebujesz drugiego D w kroku 5. Po tej wartości w tym przypadku 10 to wszystkie przypadki prawdziwe Widziałem do tej pory, że istnieje związek między różnicą a liczbą w tablicy, którą kontrolujesz, aby obliczyć, ile D (krok 5) musisz zdobyć punkt, zanim znajdziesz ostatni fałszywy przypadek.

Ustawiasz wiele wartości z ostatniego elementu bezpośrednio na true. Punkty te mogą mieć wpływ na decyzję, czy chciwa liczba monet o następnej wartości jest taka sama, jak wielokrotność ostatniej w tablicy. Z drugiej strony możesz ustawić wroga

1. Ustaw pierwszego wroga na 1 + Ostatnie S.

2. Od tego punktu dodaj każdą wartość do tablicy, aby ustawić kolejnych wrogów

3. Zacznij od ostatniego wroga Goto 2

Jeśli masz teraz wrogów i prawdziwe przypadki, rośnie prawdopodobieństwo, że liczba może być taka sama. Im więcej D, tym prawdopodobieństwo maleje.

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 ? Bajty, dziękuję @JonathanAllan, aby dać mi złe przypadki testowe
262 Bajty Prawie, ale nie wystarczająco dobre 4 złe testy w tej chwili

przypadki testowe [1, 16 256] wcześniej powinny być prawdziwe po false

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

Rosnąca kolejność tablic

Wyjaśnienie

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

Wygląda na to, że to, co widziałem w tabeli, zawiera wartości z [1,2,3,4,5,6] i zmieniam tylko ostatni element do 9. dla 2to3 i 4to5 tworzymy wartość niższej wartości w obliczanie modulo

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

To wymaga tablicy wejściowej posortowanej w kolejności malejącej. Dla każdej wartości od 2N downto 2 (N jest maksymalną wartością monety), znajduje liczbę monet z chciwego algorytmu i próbuje znaleźć mniejszy zestaw monet.

Mniej golfa

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
}

Test

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 bajtów

-1 bajt dzięki @TuukkaX (spacja może zostać usunięta między <3a 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

Wprowadzaj w kolejności malejącej.

Okropnie brutalna siła. Każdy zestaw jednej jednostki monety i innej monety jest kanoniczny. W przypadku większych zestawów najmniejszy przypadek niepowodzenia, jeśli taki istnieje, będzie większy lub równy 3 najmniejszej monecie (nie jestem pewien, jak może być równy!) I mniejszy niż suma dwóch największych monet - zobacz ten artykuł (który w rzeczywistości odwołuje się do innej, ale daje także metodę O (n ^ 3)).

g zlicza monety użyte w chciwej metodzie, a funkcja bez nazwy przemierza możliwych kandydatów (w rzeczywistości od 0 do jednej mniej niż dwa razy więcej niż największa moneta, aby zaoszczędzić bajty) i szuka dowolnej kolekcji mniejszej sumy, która również sumuje się do tej kwoty.

gdziała wykonując co kasjer będzie, to rekurencyjnie zajmuje największą monetę mniejsza lub równa kwocie jeszcze nadrobić, [v for v in c if v<=x][0]z dala, i zlicza liczbę monet użytych n.

Funkcja bez nazwy zwraca 1, jeśli len(c)jest mniejsza niż 3, a poza tym sprawdza, czy nie jest tak, 1-...że dowolne wartości w zakresie możliwości range(c[0]*2)))są możliwe przy mniejszej i in range(g(x,c))liczbie monet, tworząc kolekcję tylu każdej monety, c*ii sprawdzanie wszystkich kombinacji imonet, combinations(c*i,i)aby sprawdzić, czy jest to jakaś suma o tej samej wartości.

Galaretka ( widelec ), 15 14 bajtów

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

To rozwiązanie wykorzystuje granice dla kontrprzykładów z tego artykułu . Tam autor stosuje ścisłe ograniczenie dla przykładu, ale w interesie golfa stosuje się zakres sumy nominałów monet, który jest większy i zawiera tę granicę.

Ten program oblicza wszystkie przypadki testowe na moim komputerze w mniej niż sekundę.

Niestety, zależy to od gałęzi Jelly, w której pracowałem nad wdrożeniem atomu Frobenius, więc nie możesz wypróbować go online.

Stosowanie

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

Wydajność jest dobra i może rozwiązać wszystkie przypadki testowe jednocześnie w mniej niż sekundę.

$ 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

Wyjaśnienie

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 bajtów

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)

Wymaga sortowania tablicy w porządku malejącym. Wykorzystuje obserwację w powiązanym dokumencie, że jeśli system nie jest kanoniczny, wówczas istnieje co najmniej jedna wartość mniejsza niż 2a [0], która pobiera mniej monet po rozłożeniu przy użyciu nieużywanych monet z początkowego algorytmu chciwości.

Edycja: Zapisałem 12 bajtów, zdając sobie sprawę, że mogę sprawdzić wszystkie monety, nawet jeśli osiągnąłem już wartość docelową. Zaoszczędziłem 8 bajtów, zmieniając moje pośrednie wyjście z [l,b]na [b,-l]; pozwoliło mi to przekazać pierwszy wynik bezpośrednio jako parametr drugiego połączenia, a także niewielką oszczędność wykrywającą, czy drugie połączenie zakończyło się powodzeniem. Zaoszczędziłem 2 bajty, przenosząc definicję gdo somewywołania zwrotnego, co pozwala mi uniknąć niepotrzebnego dwukrotnego przekazywania zmiennej pętli. Zaoszczędziłem 12 bajtów, przełączając się z mojej rekurencyjnej funkcji pomocniczej na wywołanie do filter(możliwe dzięki mojemu pośredniczemu przełącznikowi wyjścia).

Perl, 69 bajtów

Obejmuje +2 za -pa

Daj monety w porządku malejącym na STDIN. Opcjonalnie możesz pominąć 1monetę.

coins.pl <<< "4 3 1"

coins.pl:

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

Zwiększa liczbę monet używanych przez algorytm kasjera @Gdla kwot od 1 do dwukrotności największej monety. Dla każdej kwoty sprawdza, czy jeśli kwota ta zostanie zmniejszona o 1 wartość monety, algorytm kasjera potrzebuje najwyżej 1 monety mniej. Jeśli nie, jest to kontrprzykład (lub wcześniejszy kontrprzykład). Mógłbym zatrzymać się przy pierwszym kontrprzykładzie, ale zajmuje to więcej bajtów. Złożoność czasu jest więc złożonością O(max_coin * coins)przestrzeniO(max_coin)