10542 - Hyper-drive
Moderator: Board moderators
-
- New poster
- Posts: 8
- Joined: Thu Jul 31, 2003 2:36 pm
10542 - Hyper-drive
I always got WA in this problem.can someone give me some more samples.thx.
I like AC
-
- New poster
- Posts: 24
- Joined: Mon Feb 24, 2003 5:08 pm
I also got WA many times.
My program output in the last test case "15484". I think it is right. Can anybody explain to me why the answer 15484 is incorrect.
Look at my program for my algorithm (I can't explain it using only words ):
[pascal]Program p10542;
Type Integer = Int64;
Var T, t_id : LongInt;
i, D, k : LongInt;
j, c : Integer;
a, b : Array[1..1000]of Integer;
function gcd(a, b : Integer) : Integer;
begin
if a = 0 then gcd := b else gcd := gcd(b mod a, a);
end;
function lcm(a, b : Integer) : Integer;
begin
lcm := a * b div gcd(a, b);
end;
begin
Readln(T);
for t_id := 1 to T do begin
Read(D);
Write('Case ', t_id, ': ');
for i := 1 to D do read(a);
for i := 1 to D do read(b);
j := 0;
for i := 1 to D do
if a = b then begin
writeln(0);
j := 1;
break;
end else
a := abs(a - b);
if j = 1 then continue;
j := a[1];
for i := 2 to D do begin
c := 1;
j := j + a;
for k := 1 to i - 1 do begin
c := c * gcd(a[k], a);
a := a[i] div gcd(a[k], a[i]);
end;
j := j - c;
end;
writeln(j);
end;
end.[/pascal]
My program output in the last test case "15484". I think it is right. Can anybody explain to me why the answer 15484 is incorrect.
Look at my program for my algorithm (I can't explain it using only words ):
[pascal]Program p10542;
Type Integer = Int64;
Var T, t_id : LongInt;
i, D, k : LongInt;
j, c : Integer;
a, b : Array[1..1000]of Integer;
function gcd(a, b : Integer) : Integer;
begin
if a = 0 then gcd := b else gcd := gcd(b mod a, a);
end;
function lcm(a, b : Integer) : Integer;
begin
lcm := a * b div gcd(a, b);
end;
begin
Readln(T);
for t_id := 1 to T do begin
Read(D);
Write('Case ', t_id, ': ');
for i := 1 to D do read(a);
for i := 1 to D do read(b);
j := 0;
for i := 1 to D do
if a = b then begin
writeln(0);
j := 1;
break;
end else
a := abs(a - b);
if j = 1 then continue;
j := a[1];
for i := 2 to D do begin
c := 1;
j := j + a;
for k := 1 to i - 1 do begin
c := c * gcd(a[k], a);
a := a[i] div gcd(a[k], a[i]);
end;
j := j - c;
end;
writeln(j);
end;
end.[/pascal]
-
- New poster
- Posts: 24
- Joined: Mon Feb 24, 2003 5:08 pm
I used the following algorithm:
ans(a,b)=a+b-gcd(a,b);
ans(a,b,c)=a+b+c-gcd(a,b)-gcd(a,c)-gcd(b,c)-gcd(b,c)+gcd(a,b,c)
ans(a,b,c,d)=a+b+c+d-gcd(a,b)-...-gcd(c,d)+gcd(a,b,c)+gcd(a,c,d)+gcd(a,b,d)+gcd(b,c,d)-gcd(a,b,c,d)
I cant proove it for dimension higher than 3, but for dimensions 1,2 or 3 a proof is very easy.
ans(a,b)=a+b-gcd(a,b);
ans(a,b,c)=a+b+c-gcd(a,b)-gcd(a,c)-gcd(b,c)-gcd(b,c)+gcd(a,b,c)
ans(a,b,c,d)=a+b+c+d-gcd(a,b)-...-gcd(c,d)+gcd(a,b,c)+gcd(a,c,d)+gcd(a,b,d)+gcd(b,c,d)-gcd(a,b,c,d)
I cant proove it for dimension higher than 3, but for dimensions 1,2 or 3 a proof is very easy.
Need help
I write a program using PIE but it get WA. Please, help me!
[pascal]Program p10542;
Var T, t_id : Integer;
i, D : Integer;
j : Int64;
a, b : Array[1..10]of Int64;
function gcd(a, b : Int64) : Int64;
begin
if a = 0 then gcd := b else gcd := gcd(b mod a, a);
end;
procedure rec(id, v : integer; g : Int64);
begin
if id > D then begin
if v = 0 then exit;
if v mod 2 = 0 then j := j - g else j := j + g;
exit;
end;
rec(id + 1, v, g);
if v > 0 then rec(id + 1, v + 1, gcd(g, a[id]))
else rec(id + 1, v + 1, a[id]);
end;
begin
Readln(T);
for t_id := 1 to T do begin
Read(D);
Write('Case ', t_id, ': ');
for i := 1 to D do read(a);
for i := 1 to D do read(b);
j := 0;
for i := 1 to D do
if a = b then begin
writeln(0);
j := 1;
break;
end else
a := abs(a - b);
if j = 1 then continue;
j := 0;
rec(1, 0, 1);
writeln(j);
end;
end.[/pascal]
[pascal]Program p10542;
Var T, t_id : Integer;
i, D : Integer;
j : Int64;
a, b : Array[1..10]of Int64;
function gcd(a, b : Int64) : Int64;
begin
if a = 0 then gcd := b else gcd := gcd(b mod a, a);
end;
procedure rec(id, v : integer; g : Int64);
begin
if id > D then begin
if v = 0 then exit;
if v mod 2 = 0 then j := j - g else j := j + g;
exit;
end;
rec(id + 1, v, g);
if v > 0 then rec(id + 1, v + 1, gcd(g, a[id]))
else rec(id + 1, v + 1, a[id]);
end;
begin
Readln(T);
for t_id := 1 to T do begin
Read(D);
Write('Case ', t_id, ': ');
for i := 1 to D do read(a);
for i := 1 to D do read(b);
j := 0;
for i := 1 to D do
if a = b then begin
writeln(0);
j := 1;
break;
end else
a := abs(a - b);
if j = 1 then continue;
j := 0;
rec(1, 0, 1);
writeln(j);
end;
end.[/pascal]
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Hmm. There's a very strange bug in FPC: you can't read array-elements of type Int64 (well, you can, but you get rubbish...).
Use a normal var of type Int64 to read and then copy it to a and b resp.
[pascal]var temp:int64;
...
for i := 1 to D do begin read(temp);a:=temp;end;
for i := 1 to D do begin read(temp);a:=abs(a-temp);end;
...[/pascal]
This does away with b[] as a bonus, but it is very strange.
What I heard was that reading long long in C isn't quite bugfree either, so that's a consolation...
Use a normal var of type Int64 to read and then copy it to a and b resp.
[pascal]var temp:int64;
...
for i := 1 to D do begin read(temp);a:=temp;end;
for i := 1 to D do begin read(temp);a:=abs(a-temp);end;
...[/pascal]
This does away with b[] as a bonus, but it is very strange.
What I heard was that reading long long in C isn't quite bugfree either, so that's a consolation...
Well, this is not the only one,Per wrote:Yeah, I used the principle of inclusion/exclusion as well.
I think this is a very nice problem! And off the top of my head it's the only one I remember which can be solved with PIE.
10497 Sweet Child Makes Trouble, ( which is similar to the classical hatcheck problem), also uses the concept of PIE.
Re: 10542 - Hyper-drive
Here is Pupirev Sergei's tests corrected and all bunched into a single input:
And here's the AC output:
Code: Select all
4
3
3 6 2
0 0 0
5
1 2 3 4 5
0 0 0 0 0
4
10 13 11 5
-4 -2 4 8
10
452 467 18 454 28 70 43 152 56 24
345 544 5645 78 455 5666 789 764 53 3
Code: Select all
Case 1: 6
Case 2: 10
Case 3: 28
Case 4: 13544