## 147 - Dollars

Moderator: Board moderators

nayaya
New poster
Posts: 9
Joined: Sat Jun 08, 2002 1:57 pm
Thank you. Now I know what was the problem. And I've got AC.

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

### 147 - Comparison with 674

I get wrong answer. I have tried to solve it using Dynamic Programming (the same as in problem 674 - Coin Change). I would appreciate if anyone would tell me why this won't work.
Here is part of code I submited:

[c]cut out [/c]

Marko Dimjasevic
Last edited by Maxim on Sat Feb 14, 2004 1:26 am, edited 1 time in total.

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
can you post the whole source of p147

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
try with
value = (int)(input_number*20+0.5);
If you got Accepted for 674, this should be the only mistake.

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:
Thanks for help. I've changed it and it was accepted.

ywliu
New poster
Posts: 9
Joined: Thu Aug 22, 2002 7:32 am
Location: Taiwan

### prob 147 help!!

I use Dynamic Programming.....and sample test is all right.
0.20 4
2.00 293
50.00 513269191

but i got WA from beginning to end.

someone can tell me why i got WA.

[cpp]
#include<iostream>
#include<string>
using namespace std;

long value,count;
long m[10][1001];
long v[10]={1,2,4,10,20,40,100,200,400,1000};

void run(long d1);
void main(){
double d1;
cout.setf(ios::fixed,ios::floatfield);
while( (cin >> d1)!=NULL ){
if(d1==0) break;
value=d1*20;
count=0;
run(value);
cout.width(5);
cout.precision(2);
cout << d1 ;
cout.width(12);
cout << count << endl;
}
}
void run(long d1){
int i,j,k1;
for(i=0;i<10;i++)
for(j=0;j<=d1;j++){
if(v==1 || j==0) m[j]=1;
else if(j<v) m[j]=m[i-1][j];
else{
m[j]=m[i-1][j];
for(k1=j-v;k1>=0;k1-=v)
m[j]+=m[i-1][k1];
}
}
count=m[i-1][j-1];
}
[/cpp]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
try to generate by brute force all posibilities (it's not quite big number - 1000?) and cmpare this output with output produced by your DP solution. BF generation take a time ca. 1 hour or less ) maybe it help you...

from code
try to change if(d == 0) ... to if(d == 0.0) ... because it may to be error on OJ

best regards
Dominik Michniewski

ywliu
New poster
Posts: 9
Joined: Thu Aug 22, 2002 7:32 am
Location: Taiwan
i already tried to BF solution before DP solution.
and sample test is all right.
0.20 4
2.00 293
50.00 513269191

but it also got WA.

so......I really don't know where the problem.

it's my code using BF solution.

[cpp]
#include<iostream>
#include<string>
using namespace std;

long value;
long count;
void run(long d1);
void main(){
double d1;
cout.setf(ios::fixed,ios::floatfield);
while( (cin >> d1)!=NULL ){
if(d1==0) break;
value=d1*20;
count=0;
run(value);
cout.width(5);
cout.precision(2);
cout << d1 ;
cout.width(12);
cout << count << endl;
}
}
void run(long d1){
int k1,k2,k3,k4,k5,k6,k7,k8,k9;
for(k1=0;k1<=d1/1000;k1++){ d1-=k1*1000;
for(k2=0;k2<=d1/400;k2++){ d1-=k2*400;
for(k3=0;k3<=d1/200;k3++){ d1-=k3*200;
for(k4=0;k4<=d1/100;k4++){ d1-=k4*100;
for(k5=0;k5<=d1/40;k5++){ d1-=k5*40;
for(k6=0;k6<=d1/20;k6++){ d1-=k6*20;
for(k7=0;k7<=d1/10;k7++){ d1-=k7*10;
for(k8=0;k8<=d1/4;k8++){ d1-=k8*4;
for(k9=0;k9<=d1/2;k9++) count++;
d1+=k8*4; }
d1+=k7*10; }
d1+=k6*20; }
d1+=k5*40; }
d1+=k4*100; }
d1+=k3*200; }
d1+=k2*400; }
d1+=k1*1000; }
}

[/cpp]

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:
use rounding for double->int conversion:
value=(int)(d1*20+0.5);

zbogi
New poster
Posts: 15
Joined: Thu Aug 29, 2002 11:00 pm
Location: Bulgaria

### that is senseless

I used [cpp]i=(int)(n*20); [/cpp]and got accepted. Just a hint I used float for n, not double. (Any way I hope that this isn`t your error - it is STUPID )
Tsvetan Bogdanov.
from Brain Explorer - Sofia University - FMI 2
e-mail: zbogi@yahoo.com

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:
try this:
double d = 4.10;
int i=(int)(d*100);

result i=409. it's because of the limited range (storage capacity) of float values. it stores the closest possible value (in form of integer mantissa*2^exponent)which may be less or greater as the desired real value.
Last edited by Picard on Mon Sep 16, 2002 10:20 pm, edited 1 time in total.

zbogi
New poster
Posts: 15
Joined: Thu Aug 29, 2002 11:00 pm
Location: Bulgaria

### I said I got Accepted

Yes ,you are right that computing (int) 4.10*100 is 409, but it is ok with 20. By the way the same problem exists with double and long double, but with other values.
Any way that is not the problem
Tsvetan Bogdanov.
from Brain Explorer - Sofia University - FMI 2
e-mail: zbogi@yahoo.com

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:
what do you mean "that is not the problem"? if i correct ywliu's first source (with the +0.5 rounding), it gets accepted.

btw:
double v=2.05;
int i=(int)(v*20);
i=40
(same for "float v=2.05;")

Aesthiri
New poster
Posts: 3
Joined: Sun Dec 01, 2002 5:02 am
Location: Sydney

### p 147 Dollars - Why WA?

My answer to 147 seems to get the correct answers for the sample questions and other small tests of mine.... I keep getting WA though. Can someone please help me?
[java]
/* @JUDGE_ID: 26309AF 147 Java */

import java.io.*;
import java.util.*;

class Main {

// code to read string from stdin without BufferedInputStream, copied from ACM website example
int length = 0, maxLength = 255, car = -1;
byte[] line = new byte[255];

try
{
while (length < maxLength)
{
if ((car < 0) || (car == '\n')) break;
line [length++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (length == 0)) return (null); // eof
return (new String (line, 0, length));
}

static void main(String args[]) {

Main dollar = new Main();
dollar.execute();
return;
}

void execute() {

// this array contains the denomination values as multiples of 5c.
int[] denominations = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000};
/* this array contains the number of combinations each value
(as a multiple of 5c) has, given the maximum denomination used. */
int[][] combinations = new int[1000][denominations.length];

String input;
StringTokenizer input_tokens;
int dollars, cents;
int five_c_amt;

/* Generate the solutions using dynamic programming.
For each value, given the largest denomination used in the ordering,
the total number of combinations =
the number of combinations for that value with the next smallest denomination as the maximum +
the number of combinations that use that denomination at least once
(+1 if the value is equal to the maximum denomination) */

for (int j = 0; j < denominations.length; j++) {

/* if j == 0 then the denomination is the smallest, hence there is only 1 combination
for each value with that denomination as the maximum */
if (j == 0) {
for (int i = 0; i < combinations.length; i++) {
combinations[j] = 1;
}
}
else {
for (int i = 0; i < combinations.length; i++) {
/* no. combinations for that value using only smallest denominations */
combinations[j] = combinations[j-1];

if (i+1 < denominations[j]) {
}
else if (i+1 == denominations[j]) {
/* +1 if value is equal to the maximum denomination */
combinations[j]++;
}
else if (i+1 > denominations[j]) {
/* no. combinations using that denomination at least once */
combinations[j] += combinations[i-denominations[j]][j];
}
}
}
}

while ((input = Main.ReadLn()) != null) {
input = input.trim();
if (input.equals("")) {
continue;
}
input_tokens = new StringTokenizer(input, ".");
dollars = Integer.parseInt(input_tokens.nextToken());
cents = Integer.parseInt(input_tokens.nextToken());

/* work out the input value as a multiple of 5c */
if (dollars == 0 && cents == 0) {
break;
}

five_c_amt = dollars * 100 + cents;
five_c_amt /= 5;

/* Print the input value, right justified in a field of length 5 */
if (input.length() < 5) {
for (int i=0; i< 5-input.length(); i++) {
System.out.print(" ");
}
}
System.out.print(input);

/* Print the answer for that input, right justified in a field of length 12 */
input = Integer.toString(combinations[five_c_amt-1][denominations.length-1]);
if (input.length() < 12) {
for (int i=0; i< 12-input.length(); i++) {
System.out.print(" ");
}
}
System.out.println(input);

}

return;
}

}
[/java][/java]

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

### clearify

clearify:

what's the definition for each M[j] in your matrix?