Last active
June 7, 2022 16:14
-
-
Save zoeisnowooze/a15af326ab0eda197ed5c93e93d90926 to your computer and use it in GitHub Desktop.
C Coin Combo
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <limits.h> | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#define DEBUG 0 | |
#define IMPOSSIBLE (INT_MAX >> 1) | |
int main(int argc, char **argv) { | |
int num_coins, amount; | |
int *coins; | |
int *m; | |
if (argc < 2) { | |
fprintf(stderr, "Usage: %s NUM_COINS [COINS ...]\n", argv[0]); | |
return 1; | |
} | |
amount = atoi(argv[1]); | |
num_coins = argc - 2; | |
coins = malloc(num_coins * sizeof(int)); | |
for (int i = 0; i < num_coins; i++) { | |
coins[i] = atoi(argv[i + 2]); | |
} | |
m = calloc((num_coins + 1) * (amount + 1), sizeof(int)); | |
for (int j = 1; j < amount + 1; j++) { | |
m[j * (num_coins + 1)] = IMPOSSIBLE; | |
} | |
for (int i = 1; i < num_coins + 1; i++) { | |
int coin = coins[i - 1]; | |
for (int r = 1; r < amount + 1; r++) { | |
if (coin == r) { | |
m[r * (num_coins + 1) + i] = 1; | |
} else if (coin > r) { | |
m[r * (num_coins + 1) + i] = m[r * (num_coins + 1) + i - 1]; | |
} else { | |
int solution_a = m[r * (num_coins + 1) + i - 1]; | |
int solution_b = 1 + m[(r - coin) * (num_coins + 1) + i]; | |
if (solution_a < solution_b) { | |
m[r * (num_coins + 1) + i] = solution_a; | |
} else { | |
m[r * (num_coins + 1) + i] = solution_b; | |
} | |
} | |
} | |
} | |
if (DEBUG) { | |
for (int i = 1; i < num_coins + 1; i++) { | |
for (int j = 0; j < amount + 1; j++) { | |
if (m[j * (num_coins + 1) + i] == IMPOSSIBLE) { | |
printf("---- "); | |
} else { | |
printf("%4d ", m[j * (num_coins + 1) + i]); | |
} | |
} | |
printf("\n"); | |
} | |
} | |
int i = num_coins; | |
int j = amount; | |
char output[256] = ""; | |
char *cur = output, *const end = output + sizeof(output); | |
while (j != 0) { | |
int coin = coins[i - 1]; | |
if (j >= coin && m[(j - coin) * (num_coins + 1) + i] == m[j * (num_coins + 1) + i] - 1) { | |
if (j == coin) { | |
printf("%s%d\n", output, coin); | |
} else { | |
cur += snprintf(cur, end - cur, "%d, ", coin); | |
} | |
j -= coin; | |
} else if (i > 0) { | |
i--; | |
} else { | |
break; | |
} | |
} | |
free(m); | |
free(coins); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
PROGRAM coin_combo | |
IMPLICIT NONE | |
CHARACTER(len=10) :: arg | |
INTEGER :: i, j, num_coins, amount, coin, r | |
INTEGER, DIMENSION (:), ALLOCATABLE :: coins | |
INTEGER, DIMENSION (:,:), ALLOCATABLE :: m | |
num_coins = command_argument_count() - 1 | |
ALLOCATE (coins(num_coins)) | |
CALL get_command_argument(1, arg) | |
READ (arg, '(I10)') amount | |
ALLOCATE (m(num_coins + 1, amount + 1)) | |
m(:,:) = 0 | |
m(1, 2:) = 999 | |
DO i = 2, num_coins + 1 | |
CALL get_command_argument(i, arg) | |
READ (arg, '(I10)') coins(i - 1) | |
END DO | |
DO i = 2, num_coins + 1 | |
coin = coins(i - 1) | |
DO j = 2, amount + 1 | |
r = j - 1 | |
IF (coin == r) THEN | |
m(i, j) = 1 | |
ELSE IF (coin > r) THEN | |
m(i, j) = m(i - 1, j) | |
ELSE | |
m(i, j) = MIN(m(i - 1, j), 1 + m(i, j - coin)) | |
END IF | |
END DO | |
END DO | |
i = num_coins + 1 | |
r = amount | |
DO WHILE (r /= 0) | |
coin = coins(i - 1) | |
j = r + 1 | |
IF (r >= coin .AND. m(i, j - coin) == m(i, j) - 1) THEN | |
IF (r == coin) THEN | |
WRITE (*, '(i3)') coin | |
ELSE | |
WRITE (*, '(i3)', advance='no') coin | |
END IF | |
r = r - coin | |
ELSE IF (i > 2) THEN | |
i = i - 1 | |
ELSE | |
EXIT | |
END IF | |
END DO | |
DEALLOCATE(coins) | |
DEALLOCATE(m) | |
END PROGRAM coin_combo |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment