## 10413 - Crazy Savages

Moderator: Board moderators

gebifier
New poster
Posts: 1
Joined: Fri Nov 29, 2002 12:32 pm
Location: Norway
Contact:

### 10413 - Crazy Savages

This is what I get when I try to solve the Crazy Savages problem. I use the extended euclidean algorithm to solve the linear congruence equation which corresponds to each pair of savages and an m value. If the solution is less than or equal to the life of both the involved savages, goto next m value. This is the only way I see which is fast enough. (BF would be really simple, but waaaaay too slow). The logic is simple and I can't find any errors in the solveLinEq algorithm so I ask if someone could point out any cases that I've missed.

Here is the code:

#include <iostream>
#include <cmath>

using namespace std;

struct dxy {
int d;
int x;
int y;
};

dxy egcd(int a, int b) {
dxy t1, t2;
if (b == 0) {
t1.d = a;
t1.x = 1;
t1.y = 0;
return t1;
} else {
t1 = egcd(b,a%b);
t2.d = t1.d;
t2.x = t1.y;
t2.y = t1.x - a/b*t1.y;
return t2;
}
}

int solveLinEq(int a, int b, int n) {
dxy t = egcd(a,n);
// cerr << "(" << t.d << "," << t.x << "," << t.y << ")" << endl;
if (b % t.d == 0) {
int period = n/t.d;
int x0 = t.x*(b/t.d) % n;
if (x0 < 0) {
return x0 + (int)(ceil(-x0/(double)period))*period;
//return x0 + ((-x0-1)/period+1)*period;
} else {
return x0 - (int)(floor(x0/(double)period))*period;
//return x0 - (x0/period)*period;
}
} else {
return -1;
}
}

void scenario() {
int n;
cin >> n;
int walk[n];
int cave[n];
int life[n];
for (int i = 0; i < n; ++i) {
cin >> cave >> walk >> life;
--cave;
}
int days, m;
bool crash = true;
for (m = 1; m <= 1000000 && crash; ++m) {
crash = false;
for (int from = 0; from < n && !crash; ++from) {
for (int to = from+1; to < n && !crash; ++to) {
if (walk[from] > walk[to]) {
days = solveLinEq(walk[from]-walk[to],cave[to]-cave[from],m);
} else {
days = solveLinEq(walk[to]-walk[from],cave[from]-cave[to],m);
}
if (days >= 0 && days <= life[from] && days <= life[to]) {
crash = true;
}
}
}
}
cout << m-1 << endl;
}

int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i)
scenario();
return 0;
}
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
You must start with the maximum cave number in the input for m, not with 1. I made a similar mistake during contest, I started with n for m and assumed there would be no cave number >n.
..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
I have compared my code with gebifier's one,
I find that my algorithm is the same as gebifier's one. (Except I start the trying on m from max. C)
But I get WA. I have checked that, my program output a m > 1000000 on the judge. I don't know what's wrong, can anyone give me some tricky case??
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.
..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
I got acceepted.
I find that I have overflow problem during solveing modular linear equation.
So I may wrongly reject some value of m, and output m > 1000000....
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.
camara
New poster
Posts: 6
Joined: Wed Jun 15, 2005 7:52 pm
Guys,

After a day on this problem, fighting against TLE, I finally got... Wrong Answer!! I'm pretty sure the ideas are correct (btw, it is coherent with these posts).

I tried many ideas for the extreme cases (e.g. l=0). Please, can any of the ACC blessed ones tell me the correct result for this (yes, I know that some of the inputs are illegal):
10
3
1 99 0
2 77 0
3 55 0
1
100 3 1000000
1
1 3 0
15
1 1 1000000
2 3 1000000
3 6 1000000
4 13 1000000
5 17 1000000
6 33 1000000
7 41 1000000
8 97 1000000
9 13 1000000
10 20 1000000
11 31 1000000
12 67 1000000
13 37 1000000
14 33 1000000
15 5 1000000
15
1 1 1000000
2 2 1000000
3 3 1000000
4 4 1000000
5 5 1000000
6 6 1000000
7 7 1000000
8 8 1000000
9 9 1000000
10 10 1000000
11 11 1000000
12 12 1000000
13 13 1000000
14 14 1000000
15 15 1000000
2
1 23232 1000000
2 34323 1000000
3
1 3 4
2 7 3
3 2 1
5
1 2 14
4 4 6
8 5 9
11 8 13
16 9 10
2
1 3 1000000
2 3 1000000
10
1 3 4
2 7 3
3 2 1
17 2 14
4 4 6
8 5 9
11 8 13
16 9 10
21 3 1000000
7 3 1000000

The program gives me:
0
1
0
1000001
1000001
3
6
33
2
1000001

I also had a version with
0
100
0
1000001
1000001
3
6
33
2
1000001

...and other versions, but all gives WA. Can anyone help me. Pleeeeeese!