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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
hai dominik...

300.00 181490736388615

good luck

Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States
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.

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

### Bugs, again bugs...

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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``````

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg
Sorry, I can`t understand why you solve answer for N>50.
Please, help me why my code get WA.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Because the problem was changed. Read the new version.

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

### help

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

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

### ACed

At last I have ACed the problem

Thank you, paulhryu!

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg
Thanks, I realy didn`t knew that this problem has new limit. Now I have Accepted

gcp
New poster
Posts: 6
Joined: Sat Nov 22, 2003 5:38 am
Location: Brazil
Contact:

### Big bumbers? (147 and 357)

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?

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:
The signed 64-bit integer is enough.
Last edited by Aleksandrs Saveljevs on Sat Dec 27, 2003 4:36 am, edited 1 time in total.

Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
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.

gcp
New poster
Posts: 6
Joined: Sat Nov 22, 2003 5:38 am
Location: Brazil
Contact:
Then, what's wrong with my algo?
Last edited by gcp on Sat Dec 27, 2003 7:13 am, edited 1 time in total.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Slight Mistake.

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.