## 10542 - Hyper-drive

Moderator: Board moderators

newtype feng
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

Pupirev Sergei
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm
Some tests:
1
3
3 6 2
0 0 0

1
5
1 2 3 4 5
0 0 0 0 0

1
4
10 13 11 5
-4 -2 4 8

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

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
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
for t_id := 1 to T do begin
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;
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
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.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### 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
for t_id := 1 to T do begin
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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### Strange..

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

little joey
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... shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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.
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
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 10542 - Hyper-drive

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
``````
Check input and AC output for over 7,500 problems on uDebug!