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:

Post by Dominik Michniewski » 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
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

Post by Hisoka » Thu Dec 18, 2003 4:59 pm

hai dominik...

300.00 181490736388615

good luck

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » 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.

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

Bugs, again bugs...

Post by pavelph » 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
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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » 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

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

Post by pavelph » 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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sat Dec 20, 2003 4:33 pm

Because the problem was changed. Read the new version.

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

help

Post by sjn » 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 :cry:

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

ACed

Post by sjn » Sat Dec 20, 2003 8:57 pm

At last I have ACed the problem :wink:

Thank you, paulhryu!

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

Post by pavelph » Sun Dec 21, 2003 9:31 pm

Thanks, I realy didn`t knew that this problem has new limit. Now I have Accepted :D

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

Big bumbers? (147 and 357)

Post by gcp » 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?

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

Post by Aleksandrs Saveljevs » Fri Dec 26, 2003 1:27 am

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.

Tahseen Mohammad
Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Location: Bangladesh

Post by Tahseen Mohammad » 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.

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

Post by gcp » Sat Dec 27, 2003 4:01 am

Then, what's wrong with my algo?
Last edited by gcp on Sat Dec 27, 2003 7:13 am, edited 1 time in total.

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

Slight Mistake.

Post by sohel » 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.
:wink:

Post Reply

Return to “Volume 1 (100-199)”