#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
int dis[5005][5005], opt[5005];
void findLocation(int n, int first, int location[], int stype[])
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(i<j) dis[i][j]=getDistance(i, j);
else dis[i][j]=dis[j][i];
}
}
opt[0]=1;
location[0]=first;
stype[0]=1;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(i!=j and dis[i][j]<dis[i][opt[i]])
opt[i]=j;
}
}
stype[opt[0]]=2;
location[opt[0]]=first+dis[0][opt[0]];
for(int i=1; i<n; i++)
{
if(i==opt[0]) continue;
if(opt[i]==0)
{
stype[i]=2;
location[i]=first+dis[0][i];
}
else if(opt[i]==opt[0])
{
stype[i]=1;
location[i]=location[opt[0]]-dis[opt[0]][i];
}
else if(dis[0][i]<dis[opt[0]][i])
{
if(dis[0][i]<dis[0][opt[i]])
{
stype[i]=2;
location[i]=first+dis[0][i];
}
else
{
stype[i]=1;
location[i]=first+dis[0][opt[i]]-dis[i][opt[i]];
}
}
else
{
if(dis[opt[0]][i]<dis[opt[0]][opt[i]])
{
stype[i]=1;
location[i]=location[opt[0]]-dis[opt[0]][i];
}
else
{
stype[i]=2;
location[i]=location[opt[0]]-dis[opt[0]][opt[i]]+dis[opt[i]][i];
}
}
}
}
