10542 - Hyper-drive

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
newtype feng
New poster
Posts: 8
Joined: Thu Jul 31, 2003 2:36 pm

10542 - Hyper-drive

Post by newtype feng » Tue Sep 02, 2003 8:32 am

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

Post by Pupirev Sergei » Tue Sep 02, 2003 6:53 pm

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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » Tue Sep 02, 2003 9:32 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]

Pupirev Sergei
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm

Post by Pupirev Sergei » Wed Sep 03, 2003 5:05 am

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

Post by Per » Wed Sep 03, 2003 7:54 am

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

Post by Revenger » Wed Sep 03, 2003 3:23 pm

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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Strange..

Post by Revenger » Wed Sep 03, 2003 7:04 pm

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Sep 03, 2003 9:33 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... :-?

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Wed Aug 11, 2004 12:58 pm

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

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10542 - Hyper-drive

Post by uDebug » Fri Feb 06, 2015 8:56 am

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!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 105 (10500-10599)”