(UVA) Dollars - Solution
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=653&page=show_problem&problem=83
The solution below used the concept of Coin Change, related to Dynamic Programming, to solve this problem.
Tip: Instead of manipulating float variables, it is better to convert the entry to an integer.
import java.io.*;
import java.util.*;
class Main {
public int[] coins = {10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5};
public long[][] matrix;
public long coinChange(int money, int indexCoins) {
if (money == 0) {
return 1;
}
else if (money < 0 || indexCoins < 0) {
return 0;
}
if (matrix[money][indexCoins] != -1) {
return matrix[money][indexCoins];
}
long use = coinChange(money-coins[indexCoins], indexCoins);
long notUse = coinChange(money, indexCoins-1);
matrix[money][indexCoins] = use+notUse;
return matrix[money][indexCoins];
}
public void process() throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
matrix = new long[30001][11];
for (int i = 0; i < 30001; i++) {
for (int j = 0; j < 11; j++) {
matrix[i][j] = -1;
}
}
double entry = sc.nextDouble();
while (entry != 0.00) {
int money = (int)(entry*100+0.000000001); // better to use an int than a double
System.out.printf("%6.2f%17d\n", entry, coinChange(money, 10));
entry = sc.nextDouble();
}
bw.flush();
bw.close();
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
The solution below used the concept of Coin Change, related to Dynamic Programming, to solve this problem.
Tip: Instead of manipulating float variables, it is better to convert the entry to an integer.
import java.io.*;
import java.util.*;
class Main {
public int[] coins = {10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5};
public long[][] matrix;
public long coinChange(int money, int indexCoins) {
if (money == 0) {
return 1;
}
else if (money < 0 || indexCoins < 0) {
return 0;
}
if (matrix[money][indexCoins] != -1) {
return matrix[money][indexCoins];
}
long use = coinChange(money-coins[indexCoins], indexCoins);
long notUse = coinChange(money, indexCoins-1);
matrix[money][indexCoins] = use+notUse;
return matrix[money][indexCoins];
}
public void process() throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
matrix = new long[30001][11];
for (int i = 0; i < 30001; i++) {
for (int j = 0; j < 11; j++) {
matrix[i][j] = -1;
}
}
double entry = sc.nextDouble();
while (entry != 0.00) {
int money = (int)(entry*100+0.000000001); // better to use an int than a double
System.out.printf("%6.2f%17d\n", entry, coinChange(money, 10));
entry = sc.nextDouble();
}
bw.flush();
bw.close();
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
Comments
Post a Comment