Page 4 of 16
Posted: Thu Dec 18, 2003 2:45 pm
Could anyone help me and tell me , if my output for 300.00 is correct ?
300.00 ==> 5807703564435680
??
I tested actual solutions with Accepted solution (mine, counting to 50.00) and got no errors ...
I anyone want, could send me output for your accepted solution, or I send to this person my output and compare it ... maybe I have any mistake

Best regards
DM

Posted: Thu Dec 18, 2003 4:59 pm
hai dominik...

300.00 181490736388615

good luck

Posted: Fri Dec 19, 2003 3:41 am
It's also worth noting that with the new and (un?)-improved version of the problem, there is now a \$100 "coin". I'm not sure if that is new as well, or if I just ignored it earlier since the \$50 upperbound on the input made it extraneous.

Bugs, again bugs...

Posted: Fri Dec 19, 2003 3:26 pm
Hello!
Can anybody help why I get WA again and again?
Here my code:
[pascal]{\$N+}
program acm147 (input, output); {Coin change}
type T = longint;
var s: string;
n: T;
y: integer;
r: double;
a2, a4, a10, a20, a40, a100, a200, a400: array [0..1010] of T;

procedure make;
var i, j, sum, v, vs: T;
begin
a2[0]:=1;a4[0]:=1;a10[0]:=1;a20[0]:=1;a40[0]:=1;a100[0]:=1;a200[0]:=1;a400[0]:=1;
for i:=1 to n do begin
v:=i;
sum:=0;
while v>=0 do begin
sum:=sum+1;
dec(v, 2);
end;
a2:=sum;
end;
for i:=1 to n do begin
v:=i;
sum:=0;
while v>=0 do begin
sum:=sum+a2[v];
dec(v, 4);
end;
a4:=sum;
end;
for i:=1 to n do begin
v:=i;
sum:=0;
while v>=0 do begin
sum:=sum+a4[v];
dec(v, 10);
end;
a10:=sum;
end;
for i:=1 to n do begin
v:=i;
sum:=0;
while v>=0 do begin
sum:=sum+a10[v];
dec(v, 20);
end;
a20:=sum;
end;
for i:=1 to n do begin
v:=i;
sum:=0;
while v>=0 do begin
sum:=sum+a20[v];
dec(v, 40);
end;
a40:=sum;
end;
for i:=1 to n do begin
v:=i;
sum:=0;
while v>=0 do begin
sum:=sum+a40[v];
dec(v, 100);
end;
a100:=sum;
end;
for i:=1 to n do begin
v:=i;
sum:=0;
while v>=0 do begin
sum:=sum+a100[v];
dec(v, 200);
end;
a200:=sum;
end;
for i:=1 to n do begin
v:=i;
sum:=0;
while v>=0 do begin
sum:=sum+a200[v];
dec(v, 400);
end;
a400:=sum;
end;
end;

begin
assign(input, 'input.txt');
reset(input);
assign(output, 'output.txt');
rewrite(output);
n:=1000;
make;
while not eof do begin
if r=0 then exit;
write(r:5:2);
n:=trunc(r*20+0.5);
if r<50 then writeln(a400[n]:12) else writeln((a400[n]+1):12);
end;
end.[/pascal]
And output for 49<=r<=50:
OUTPUT

Code: Select all

``````49.00   453276316
49.05   453276316
49.10   458987794
49.15   458987794
49.20   464764106
49.25   464764106
49.30   470599554
49.35   470599554
49.40   476499836
49.45   476499836
49.50   482464952
49.55   482464952
49.60   488494902
49.65   488494902
49.70   494589686
49.75   494589686
49.80   500749304
49.85   500749304
49.90   506973756
49.95   506973756
50.00   513269191``````

Posted: Sat Dec 20, 2003 3:16 pm
What changed? I changed the type to long long, and added the 100\$ coin, and made the array bigger.. anything else?

Code: Select all

``````  0.20                4
2.00              293
50.00        513269191
100.00      47580509178
150.00     855199081968
200.00    7402472263151
250.00   42082966861176
300.00  181490736388615``````

Posted: Sat Dec 20, 2003 3:59 pm
Sorry, I can`t understand why you solve answer for N>50.
Please, help me why my code get WA.

Posted: Sat Dec 20, 2003 4:33 pm
Because the problem was changed. Read the new version.

help

Posted: Sat Dec 20, 2003 7:19 pm

Code: Select all

``````  0.20                4
2.00              293
20.00          2886726
50.00        513269191
100.00      47580509178
120.00     170631714918
150.00     855199081968
200.00    7402472263151
220.00   15443740016191
250.00   42082966861176
300.00  181490736388615``````

AM I RIGHT???
but I still got WA

ACed

Posted: Sat Dec 20, 2003 8:57 pm
At last I have ACed the problem

Thank you, paulhryu!

Posted: Sun Dec 21, 2003 9:31 pm
Thanks, I realy didn`t knew that this problem has new limit. Now I have Accepted

Big bumbers? (147 and 357)

Posted: Fri Dec 26, 2003 12:41 am
I've solved these problems, but the range of answers is larger than the suportted by long long in C++.

It's necessary to use big numbers in these problems?

Someone have solved these problems without the use of big numbers?

Posted: Fri Dec 26, 2003 1:27 am
The signed 64-bit integer is enough.

Posted: Fri Dec 26, 2003 2:32 pm
I have also used signed long long and it was AC.

How are you so sure that the answer does not fit it.
Your algorithm is supposed to be ok as you got AC before.
You just have to change the range & variable type.

Posted: Sat Dec 27, 2003 4:01 am
Then, what's wrong with my algo?

Slight Mistake.

Posted: Sat Dec 27, 2003 6:35 am
HI GCP,
Nothing is wrong with your algorithm. But your terminating condition is not quite correct. You should read till the EOF. But you are terminating when input is zero.
Hope it helps.