a.cpp
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <list>
#define SIZEOF(a) (sizeof(a)/sizeof(a[0]))
#define FILL(a,b) fill(a,a+SIZEOF(a),b)
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define FORARR(i,a) for(unsigned i=0; i<SIZEOF(a); i++)
#define FOREACH(a,b) for(__typeof((b).begin()) a = (b).begin(); a!=(b).end(); a++)
#define GETI(a) scanf("%d ", &a);
#define SWAP(a,b) { __typeof(a) t = a; a = t; b = t; }
using namespace std;
struct ant {
int id;
int pos;
int dir; // 1 for right, -1 for left
ant(int id, int pos, int dir) : id(id), pos(pos), dir(dir) {}
};
bool operator<(const ant& a, const ant& b) {
return a.pos < b.pos;
}
void answer(int id, int time)
{
cout << "The last ant will fall down in " << time << " seconds - started at " << id << "." << endl;
}
void answer(int id, int id2, int time)
{
cout << "The last ant will fall down in " << time << " seconds - started at " << id << " and " << id2 << "." << endl;
}
void print_ants(deque<ant> ants)
{
FOREACH(a,ants) {
cerr << a->id << "(pos " << a->pos << ", dir " << a->dir << "), ";
}
}
int main(void)
{
int L, A;
cin >> L >> A;
while (!feof(stdin)) {
L *= 2;
// cerr << "read " << L << " " << A << endl;
deque<ant> ants;
vector<ant> antsv;
FOR(i,1,A) {
int pos;
char dir;
cin >> pos >> dir;
antsv.push_back(ant(pos, pos*2, (dir == 'L' ? -1 : 1)));
}
// sort by pos
sort(antsv.begin(), antsv.end());
FOREACH(a, antsv) {
ants.push_back(*a);
}
// print_ants(ants);
// cerr << endl;
FOR(time,0,L+3) {
// cerr << "AT " << time << ": ";
// print_ants(ants);
// cerr << endl;
// let them walk
FOREACH(i,ants) {
// collsions?
deque<ant>::iterator nb = i+1;
if (nb != ants.end() && nb->pos == i->pos) {
i->dir *= -1;
nb->dir *= -1;
if (i->pos == nb->pos) {
i->pos += i->dir;
nb->pos += nb->dir;
}
i++;
}
else {
i->pos += i->dir;
}
}
// let them fall
int fallenId = -1;
if (ants.front().pos == -1) {
fallenId = ants.front().id;
if (ants.size() == 1) {
answer(fallenId, time/2);
break;
}
ants.pop_front();
}
if (ants.back().pos == L+1) {
if (ants.size() == 1) {
// the last ant!
int id = ants.back().id;
if (fallenId == -1) {
// id is the only one
answer(id, time/2);
}
else {
// they both fell down now
answer(min(fallenId, id), max(fallenId, id), time/2);
}
break; // we won!
}
ants.pop_back();
}
}
cin >> L >> A;
}
return 0;
}