My solution is like this:
We find the paths of A && B. Definitely A && B will enter some circular path eventually. We assign to every junction(for A && B separately):
1. "pos" if this junction is traversed only once(before A || B enters his circular path)
2. "(pos,period)" if it appears in the circular path, where pos is the first occurrence of the junction,and period is the length of the circular path
3. "-1" if it is never visited
Then for every junction we check whether its position(s) for A will meet B's. We may need to solve the equation:
pos_A + period_A * x == pos_B + period_B * y
where x,y >= 0 && the value on each side is minimum
This can be done with euclid's method.

However I am stuck on test#55. I have disposed all of my energy to find the tricky case but ended up with no result.
Please help!

Edited by author 23.04.2005 22:04

I solved this problem in the same way and get AC
link: http://acm.timus.ru/status.aspx?space=1&pos=811782

Have you used int64 for the intermediate result?
I suspect I've got some kind of overflow
Thx

Of course, there are may be very big numbers!
if period_A = 99999, period_B = 99998 and pos_B - pos_A = 99997, we have almost 100000^2.
Good luck!

I still can't pass #55
Now I suspect I made something wrong when solving
pos_A + period_A * x == pos_B + period_B * y using euclid's method
My method goes like this
(short hands: pos_A: n1, pos_B: n2, period_A: a, period_B: b)
So we want to solve n1 + ax == n2 + by, such that x, y >= 0 && n1 + ax is minimized
if n1 >= n2, we just solve
   by - ax == n1 - n2, such that x, y >= 0 && x is minimum
else
   ax - by == n2 - n1, such that x, y >= 0 && y is minimum
Here's my code for solving
ax - by == n, such that x, y >= 0 && y is minimum
( which equals to solve:
  by == a - n mod a (mod a) )

!! I am sorry for the readablility of the code since I don't know how to make the code look like indented. You can use my account 36057RJ to edit this msg and get indented code
################################
typedef typedef __int64 LL;
LL
Gcd(LL a, LL b, LL *x, LL *y)
{
    if ( b == 0 ) {
        *x = 1;
        *y = 0;
        return a;
    } else {
        LL xx, yy;
        LL gcd = Gcd(b, a % b, &xx, &yy);
        *x = yy;
        *y = xx - (a / b) * yy;
        return gcd;
    }
}
LL
SolveLinear(LL a, LL b, LL n)
{
    LL result;
    LL x, y;
    LL q;
    LL d = Gcd(b, a, &x, &y);
    n = (a - n % a) % a;
    if ( n % d != 0 )
        return -1;
    x *= n / d;
    q = a / d;
    result = x % q;
    if ( result < 0 )
        result += q;
    return result;
}
####################################
Is this the right thing to do ?
Thanks in advance for taking your time to
check this

Edited by author 26.04.2005 19:31