10548 - Find the Right Changes

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

10548 - Find the Right Changes

Post by 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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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

Post by Revenger »

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

Post by windows2k »

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 :D
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

Post by 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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k »

Per wrote: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 :D
I ignore the boundary case , now i got ac

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm

hi

Post by 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

Post Reply

Return to “Volume 105 (10500-10599)”