길이가 L인 줄이있고 그 위에 개미들이 있다. 개미들의 방향은 오른쪽 또는 왼쪽이며
1mm/s의 속도로 가다가 줄의 끝이나 다른 개미들을 만나면 방향을 바꾼다.
T초 후에 개미들의 좌표를 구하는것이 문제이다.
줄위에 두마리의 개미가 서로 마주보는 방향으로 가고 있다고 생각해보자.
이 개미들이 만나기 전까지는 평범하게 이동할것이다. 과연 만난 후에는 어떻게 될까?
사실상 만난후에도 개미들의 좌표는 똑같은 이동좌표일 것이다. 다만 각각의 개미들의 방향이 반대가 될뿐이다.
방향이 반대가 되는데 T초후에 1번부터 N번까지의 각각의 좌표는 어떻게 따져야하는 의문이 생길 수 있다. 하지만 생각해보면 개미들은 무한대의 시간이 지나도 초기 순서대로 위치함을 알 수 있다. (어느 범위내에서 계속 왔다 갔다 하는 것이다.)
따라서 T초후의 개미들의 좌표들을 구한 후에 정렬하면 1번부터 N번개미들의 좌표가 나온다.
#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct Ant{
int pos;
char dir;
}Ant;
bool cmp(Ant a, Ant b){return a.pos < b.pos;}
Ant ant[70001];
int main(){
int L, T, N;
scanf("%d%d%d", &L, &T, &N);
for (int n = 0; n < N;n++)
scanf("%d %c", &ant[n].pos, &ant[n].dir);
for (int n = 0; n < N; n++){
int p, q;
int t;
if (ant[n].dir == 'L'){
t = T - ant[n].pos;
if (t < 0)
ant[n].pos -= T;
else{
p = t / L;
q = t % L;
ant[n].pos = p & 1 ? L-q : q;
}
}
else{
t = T - (L - ant[n].pos);
if (t < 0)
ant[n].pos += T;
else{
p = t / L;
q = t % L;
ant[n].pos = p & 1 ? q : L - q;
}
}
}
sort(ant, ant + N, cmp);
for (int n = 0; n < N; n++)
printf("%d ", ant[n].pos);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기