OJ Board

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

can you post the whole source of p147

try with
value = (int)(input_number*20+0.5);
If you got Accepted for 674, this should be the only mistake.

Thanks for help. I've changed it and it was accepted.

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]

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

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]

use rounding for double->int conversion:
value=(int)(d1*20+0.5);

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 )

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.

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

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

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
static String ReadLn() {
int length = 0, maxLength = 255, car = -1;
byte[] line = new byte[255];

try
{
while (length < maxLength)
{
car = System.in.read();
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]

clearify:

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