10548 - Find the Right Changes

[Revenger]

Can anybody tell me how can I improve my algo. I get AC.
I do brute froce with some improvements, but they are not enough.

My Code:
[pascal]Program p10548;

type LongInt = Int64;

Var a, b, c, n, t, beg : LongInt;
i, j : Integer;

function gcd(a, b : LongInt) : LongInt;
begin
if a = 0 then gcd := b else gcd := gcd(b mod a, a);
end;

begin
read(n);
for i := 1 to n do begin
read(a, b, c);
if a > b then begin
t := a;
a := b;
b := t;
end;
if a < 0 then begin
t := 0;
beg := c div b;
if b * beg < c then beg := beg + 1;
for j := beg to beg - a do
(* CUT CUT CUT CUT CUT CUT CUT *)
if t = 0 then Writeln('Impossible')
else Writeln('Infinitely many solutions');
end else begin
t := 0;
for j := 0 to a div gcd(a, b) do
(* CUT CUT CUT CUT CUT CUT CUT *)
if t = 0 then Writeln('Impossible')
else Writeln(t);
end;
end;
end.[/pascal]

[little joey]

1. Remove the recursion in function gcd. It's claiming and freeing stackspace with every call, so that makes it slow. There are basic iterative algos for gcd, use one of them instead.

2. Don't put a function call as the limiting case in the for statement, the function will get called every time around the loop. Change it to something like[pascal]maxj:=a div gcd(a,b);
for j:=1 to maxj do ...[/pascal]

But maybe there is more in the cutted part....?

[Revenger]

Thank you!
But my solution still is the slowest
It work 0.2 sec

[windows2k]

Thank you!
But my solution still is the slowest
It work 0.2 sec

I got many WA in the problem.
I used Extend_GCD , not only find the greatest d, but also find a
solution that make a*x+b*y = c , am I right?
here is some input,could some one tell me the right output
Thx
10
2 3 17
2 4 20
11 -3 -66
-13 66 99
141 258 1777
12345 54321 -66666
12345 54321 66666
321 179 431
222 111 666
21 -7 422

[Per]

Your output:

Code: Select all

3
6
Infinitely many solutions
Infinitely many solutions
Impossible
Impossible
1
Impossible
4
Impossible

Here are some other (interesting?) inputs:

Code: Select all

1 1 2147483647
2147483646 2147483647 2147483647
2147483647 2147483647 2147483647

Output:

Code: Select all

2147483648
1
2

[windows2k]

Your output:
Here are some other (interesting?) inputs:

Code: Select all

1 1 2147483647
2147483646 2147483647 2147483647
2147483647 2147483647 2147483647

Output:

Code: Select all

2147483648
1
2

Thanks very much
I ignore the boundary case , now i got ac

[oriol78]

hi, i have problems with my code, judge always replies me WA, can anybody helps me plz??

(sorry about my english)

first i try to solve the diophantic equation, if there are any solutions, the solution of the problem is the size of the subset of values of x and y when x and y are non_negatives, this is the code:

[cpp]
/* @JUDGE_ID: xxxxxxx 10548 C++ */
/* @BEGIN_OF_SOURCE_CODE */

#include <iostream>
#include <math.h>
using namespace std;

long int absl(long int x)
{
if(x < 0)
return -x;
return x;
}

void proces(long int a_0, long int b_0, long int c)
{
long int a, b, aux;
if(absl(a_0) < absl(b_0))
{
a = absl(b_0);
b = absl(a_0);
aux = a_0;
a_0 = b_0;
b_0 = aux;
}
else
{
a = absl(a_0);
b = absl(b_0);
}
long int X_0 = 1, X_1 = 0, Y_0 = 0, Y_1 = 1, Q_0, Q_1 = a/b, R_0 = a, R_1 = b, S_0 = a%b, S_1;
long int X_aux, Y_aux, R_aux, S_aux;
long int count = 1;
if(a%b != 0)
S_1 = b%(a%b);
else
S_1 = 0;
while(S_1 != 0)
{
X_aux = X_0-X_1*Q_1;
X_0 = X_1;
X_1 = X_aux;
Y_aux = Y_0-Y_1*Q_1;
Y_0 = Y_1;
Y_1 = Y_aux;
R_aux = S_0;
R_0 = R_1;
R_1 = R_aux;
Q_0 = Q_1;
Q_1 = R_0/R_1;
S_aux = S_1;
S_0 = S_1;
S_1 = R_1%S_aux;
}
long int x = X_0-X_1*Q_1;
long int y = Y_0-Y_1*Q_1;
long int mcd = S_0;
long int t_x, t_y;
int dir_x, dir_y;
if(a_0%b_0 == 0)
{
mcd = b;
x = 0;
y = 1;
}
if(a_0 == 1 || b_0 == 1)
mcd = 1;
if(c%mcd != 0)
cout << "Impossible" << endl;
else
{
if(b_0<0)
y = -y;
if(a_0<0)
x = -x;
t_x = (x*c/mcd)/(b_0/mcd);
t_y = -(y*c/mcd)/(a_0/mcd);
if((x*c/mcd)-(b_0/mcd*(t_x)) < 0)
{
if((x*c/mcd)-(b_0/mcd*(t_x+1)) >= 0)
{
t_x++;
dir_x = 1;
}
else
{
t_x--;
dir_x = -1;
}
}
else
{
if((x*c/mcd)-(b_0/mcd*(t_x-1)) < 0)
dir_x = 1;
else
dir_x = -1;
}
if((y*c/mcd)+(a_0/mcd*(t_y)) < 0)
{
if((y*c/mcd)+(a_0/mcd*(t_y+1)) >= 0)
{
t_y++;
dir_y = 1;
}
else
{
t_y--;
dir_y = -1;
}
}
else
{
if((y*c/mcd)+(a_0/mcd*(t_y-1)) < 0)
dir_y = 1;
else
dir_y = -1;
}
if(dir_x == dir_y)
cout << "Infinitely many solutions" << endl;
else
{
long int temp = (t_x-t_y);
if(temp < 0)
temp = -temp;
if(temp == 2147483647)// problems with the range, sorry i don't know more
cout << "2147483648" << endl;
else
{
temp++;
if(dir_x == 1)
{
if(t_x > t_y)
cout << "Impossible" << endl;
else
cout << temp << endl;
}
else
{
if(t_y > t_x)
cout << "Impossible" << endl;
else
cout << temp << endl;
}
}
}
}
}

int main()
{
int cases;
long int a, b, c;
cin >> cases;
for(cases;cases--;)
{
cin >> a >> b >> c;
proces(a,b,c);
}
return 0;
}
/* @END_OF_SOURCE_CODE */
[/cpp]

thx for advance