Zadanie jest proste. Daj mi trochę 1000, 500i 100notatki.

W jaki sposób ? możesz zapytać. Nie martw się, nie musisz okradać banku, ponieważ w pobliżu znajduje się bankomat, który akceptuje Twoją kartę kredytową. Ale twój limit kredytowy wystarczy do wykonania zadania, więc musisz uważać na wypłaty.

Wyzwanie

Biorąc pod uwagę liczbę 1000, 500a 100wymagane notatki, obliczenia wypłat konkretne potrzebne, aby uzyskać przynajmniej te kilka nut. Przy każdej wypłacie bankomat może wypluć każdą notatkę na podstawie następujących zasad:

• Kwota wycofana ( A) jest mniejsza niż5000
  • Jeśli A%1000 == 0, po czym wypluwa 1 ATM 500uwaga, 5 100notatki i odpoczynku 1000notatki
  • W przeciwnym razie A%500 == 0bankomat wypluwa 5 100banknotów, 1000banknoty pozostałych
  • W przeciwnym razie A%1000 < 500bankomat wypluwa floor(A/1000) 1000notatki i 100notatki odpoczynku
  • W przeciwnym razie A%1000 > 500bankomat wypluwa floor(A/1000) 1000banknoty, 1 500i 100banknoty spoczynkowe
• Kwota wypłacona jest większa niż równa 5000
  • Jeśli A%1000 == 0, to bankomat wypluwa 2 500banknoty i 1000banknoty pozostałe
  • Else if, A%500 == 0, bankomat wypluwa 1 500notatkę i odpoczynku 1000notatki
  • W przeciwnym razie A%1000 < 500bankomat wypluwa floor(A/1000) 1000notatki i 100notatki odpoczynku
  • W przeciwnym razie A%1000 > 500bankomat wypluwa floor(A/1000) 1000banknoty, 1 500i 100banknoty spoczynkowe

Dla wyjaśnienia, oto pełna tabela wycofanych notatek dla wszystkich możliwych kwot do 7000(możesz wypłacić więcej, ale wzór nie zmienia się później). Kolejność jest następująca <1000> <500> <100>:

 100 => 0 0 1                  2500 => 2 0 5                   4800 => 4 1 3
 200 => 0 0 2                  2600 => 2 1 1                   4900 => 4 1 4
 300 => 0 0 3                  2700 => 2 1 2                   5000 => 4 2 0
 400 => 0 0 4                  2800 => 2 1 3                   5100 => 5 0 1
 500 => 0 0 5                  2900 => 2 1 4                   5200 => 5 0 2
 600 => 0 1 1                  3000 => 2 1 5                   5300 => 5 0 3
 700 => 0 1 2                  3100 => 3 0 1                   5400 => 5 0 4
 800 => 0 1 3                  3200 => 3 0 2                   5500 => 5 1 0
 900 => 0 1 4                  3300 => 3 0 3                   5600 => 5 1 1
1000 => 0 1 5                  3400 => 3 0 4                   5700 => 5 1 2
1100 => 1 0 1                  3500 => 3 0 5                   5800 => 5 1 3
1200 => 1 0 2                  3600 => 3 1 1                   5900 => 5 1 4
1300 => 1 0 3                  3700 => 3 1 2                   6000 => 5 2 0
1400 => 1 0 4                  3800 => 3 1 3                   6100 => 6 0 1
1500 => 1 0 5                  3900 => 3 1 4                   6200 => 6 0 2
1600 => 1 1 1                  4000 => 3 1 5                   6300 => 6 0 3
1700 => 1 1 2                  4100 => 4 0 1                   6400 => 6 0 4
1800 => 1 1 3                  4200 => 4 0 2                   6500 => 6 1 0
1900 => 1 1 4                  4300 => 4 0 3                   6600 => 6 1 1
2000 => 1 1 5                  4400 => 4 0 4                   6700 => 6 1 2
2100 => 2 0 1                  4500 => 4 0 5                   6800 => 6 1 3
2200 => 2 0 2                  4600 => 4 1 1                   6900 => 6 1 4
2300 => 2 0 3                  4700 => 4 1 2                   7000 => 6 2 0
2400 => 2 0 4

Lista dostarczona przez Martina

The Catch

Ponieważ limit kredytowy na karcie kredytowej jest wystarczający, musisz upewnić się, że całkowita kwota wypłacona w ramach wypłat jest minimalnym możliwym dla danego wkładu / wymogu dotyczącego banknotów.

Wkład

Dane wejściowe mogą być w dowolnym korzystnym formacie dla trzech liczb odpowiadających liczbie wymaganych nut wartości 1000, 500oraz 100. Niekoniecznie w tej kolejności.

Wydajność

Produkcja globalna to kwota do wycofania w każdej transakcji oddzielona nową linią.

Przykłady

Dane wejściowe (format <1000> <500> <100>):

3 4 1

Wydajność:

600
600
600
3600

trochę więcej:

7 2 5
5000
3500

1 2 3
600
1700

21 14 2
600
600
600
1600
5000
5000
5000
5000
5000

Założenia

• Możesz założyć, że bankomat ma nieskończoną liczbę banknotów każdej kwoty.
• Możesz również założyć, że możesz dokonywać dowolnej liczby transakcji.
• Co więcej, rozwiązanie niektórych wartości wejściowych może nie być unikalne, więc możesz wypisać dowolne 1 rozwiązanie, które spełnia minimalną możliwą ilość i wymagane minimum notatek.

Jak zwykle, możesz napisać pełny program czytający dane wejściowe przez STDIN / ARGV i wypisujący dane wyjściowe do STDOUT lub funkcję przyjmującą dane wejściowe za pomocą argumentów i zwracającą albo listę liczb całkowitych odpowiadających kwotom, albo ciąg znaków z kwotami oddzielonymi nowym wierszem.

To jest golf golfowy, więc wygrywa najkrótszy kod w bajtach.

JavaScript, 184 148

function g(a,b,c){x=[];while(a>0||b>0||c>0){i=b<3||a<4?a:4;a-=i;if(i>3&&b>1){b-=2;i++}else{i+=(c--<b&&i>4?0:.1)+(b-->0?.5:0)}x.push(i*1e3)}return x}

http://jsfiddle.net/vuyv4r0p/2/

zwraca listę liczb całkowitych odpowiadających kwotom wypłaty

Perl 5: 223

Edytować

To rozwiązanie zostało wykonane przy błędnym założeniu, że 7K to limit bankomatu. To faktycznie uczyniło to zadanie bardziej interesującym, ponieważ wymagało dynamicznego programowania (wzorzec ruchu był dość regularny, ale kodowanie na stałe byłoby prawdopodobnie dłuższe niż obliczanie na żywo tak jak ja). Przy każdej możliwej ilości wzorzec ruchu jest tak regularny, że kodowanie go jest trywialne. Nie wiem, czy rozwiązanie @hoffmale jest teraz poprawne, ale znajdzie się wśród tych linii. Tak więc niestety będzie to kolejne zadanie, w którym najpierw ktoś znajdzie rozwiązanie, a następnie zostanie przeniesiony do gry w golfa, aby wygrać.

Trochę wolniej niż oryginalne rozwiązanie (ale wciąż poniżej sekundy dla parametrów poniżej 100).

#!perl -pa
$c{0,0}=$f=($a,$b,$c)=@F;for$i(0..$b){for$j(0..$a){
/.(?=.$)/>($n=$c{$i-$`,$j-$'})||${$r=\$c{$i,$j}}<($x=$n+$&)&&$$r
or$f=$$r="$x $n".($'.$&+5*$`)."00
"for 204..206,105,106,11..15,110..114}}$_=$f."100
"x($c-$f+3);s/.*\b3//

Szybsze rozwiązanie 259.

#!perl -pa
$c{0,0}=($a,$b,$c)=@F;for$i(0..$b){for$j(0..$a){
/\B./<($%=$c{$i-$&,$j-$'}+$`)&&(!${$r=\$c{$i,$j}}||$$r>$%)and$d{$i,$j}=$_,$$r=$%for
qw/024 025 026 015 016/,101..105,110..114}}
$d{$b,$a}=~/\B./,$c-=$`,$b-=$&,$a-=$',print$'.$`+5*$&,"00
"while$a+$b;$_="100
"x$c

Wykorzystuje STDIN:

$perl atm.pl <<<"21 14 2"
5000
5000
5000
5000
5000
600
600
600
1600