147 - Dollars

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

nayaya
New poster
Posts: 9
Joined: Sat Jun 08, 2002 1:57 pm

Post by nayaya » Thu Jul 25, 2002 3:14 am

Thank you. Now I know what was the problem. And I've got AC.

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

147 - Comparison with 674

Post by Maxim » Tue Aug 27, 2002 12:59 am

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 8) [/c]

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

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Wed Aug 28, 2002 4:46 am

can you post the whole source of p147

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Aug 28, 2002 7:47 am

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

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

Post by Maxim » Wed Aug 28, 2002 12:54 pm

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!!

Post by ywliu » Fri Sep 13, 2002 6:37 am

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:

Post by Dominik Michniewski » Fri Sep 13, 2002 8:03 am

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

Post by ywliu » Fri Sep 13, 2002 2:39 pm

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:

Post by Picard » Sat Sep 14, 2002 12:06 pm

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

Post by zbogi » Sun Sep 15, 2002 7:05 pm

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:

Post by Picard » Sun Sep 15, 2002 8:23 pm

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

Post by zbogi » Mon Sep 16, 2002 8:56 pm

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:

Post by Picard » Mon Sep 16, 2002 10:19 pm

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?

Post by Aesthiri » Sun Dec 01, 2002 5:07 am

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]

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

clearify

Post by yiuyuho » Thu Dec 05, 2002 5:56 am

clearify:

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

Post Reply

Return to “Volume 1 (100-199)”