#include "rail.h"
// #include <iostream>
const int N = 5005;
int dp[N][N];
int dist(int i, int j) {
if (i == j) return 0;
if (i > j) {
int t = i;
i = j;
j = t;
}
if (!dp[i][j]) {
dp[i][j] = getDistance(i, j);
// std::cerr << "dp[" << i << "][" << j << "] = " << dp[i][j] << std::endl;
}
return dp[i][j];
}
void findLocation(int n, int first, int location[], int stype[]) {
location[0] = first;
stype[0] = 1;
int cr = 1;
for (int i = 2; i < n; i++) if (dist(0, cr) > dist(0, i)) cr = i;
location[cr] = dist(0, cr) + first;
stype[cr] = 2;
for (int i = 1; i < n; i++) {
if (i == cr) continue;
if (dist(0, i) > dist(cr, i)) {
stype[i] = 1;
location[i] = first - dist(cr, i) + dist(cr, 0);
}
else {
stype[i] = 2;
location[i] = first + dist(0, i);
}
}
}
