## 10548 - Find the Right Changes

Moderator: Board moderators

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### 10548 - Find the Right Changes

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
for i := 1 to n do begin
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
Thank you!
But my solution still is the slowest It work 0.2 sec

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
Revenger wrote: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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
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
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm

### hi

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

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]