Page 4 of 16

Posted: Thu Dec 18, 2003 2:45 pm
by Dominik Michniewski
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
by Hisoka
hai dominik...

300.00 181490736388615

good luck

Posted: Fri Dec 19, 2003 3:41 am
by rjhadley
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
by pavelph
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
readln(r);
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
by Larry
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
by pavelph
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
by Krzysztof Duleba
Because the problem was changed. Read the new version.

help

Posted: Sat Dec 20, 2003 7:19 pm
by sjn

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 :cry:

ACed

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

Thank you, paulhryu!

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

Big bumbers? (147 and 357)

Posted: Fri Dec 26, 2003 12:41 am
by gcp
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
by Aleksandrs Saveljevs
The signed 64-bit integer is enough.

Posted: Fri Dec 26, 2003 2:32 pm
by Tahseen Mohammad
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
by gcp
Then, what's wrong with my algo?

Slight Mistake.

Posted: Sat Dec 27, 2003 6:35 am
by sohel
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.
:wink: