10542 - Hyper-drive

[newtype feng]

I always got WA in this problem.can someone give me some more samples.thx.

[Pupirev Sergei]

Some tests:
1
3
3 6 2
0 0 0
answer is: 6

1
5
1 2 3 4 5
0 0 0 0 0
answer is: 10

1
4
10 13 11 5
-4 -2 4 8
answer is: 28

1
452 467 18 454 28 70 43 152 56 24
345 544 5645 78 455 5666 789 764 53 3
answer is: 13544

[Revenger]

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]

[Pupirev Sergei]

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.

[Per]

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.

[Revenger]

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]

[Revenger]

It is really very strange, because the same code in C++ get Accepted. Why it happened?

[little joey]

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

[shamim]

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.

Well, this is not the only one,

10497 Sweet Child Makes Trouble, ( which is similar to the classical hatcheck problem), also uses the concept of PIE.

[uDebug]

Here is Pupirev Sergei's tests corrected and all bunched into a single input:

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

And here's the AC output:

Code: Select all

Case 1: 6
Case 2: 10
Case 3: 28
Case 4: 13544