3783 - 【START】2015暑期训练——Piotr’s Ants
Piotr likes playing with ants. He has n of them on a horizontal pole L cm long. Each ant is facing
either left or right and walks at a constant speed of 1 cm/s. When two ants bump into each other, they
both turn around (instantaneously) and start walking in opposite directions. Piotr knows where each
of the ants starts and which direction it is facing and wants to calculate where the ants will end up T
seconds from now.
题目输入
The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line
containing 3 integers: L , T and n (0 ≤ n ≤ 10000). The next n lines give the locations of the n ants
(measured in cm from the left end of the pole) and the direction they are facing (L or R).
题目输出
For each test case, output one line containing ‘Case #x:’ followed by n lines describing the locations
and directions of the n ants in the same format and order as in the input. If two or more ants are at
the same location, print ‘Turning’ instead of ‘L’ or ‘R’ for their direction. If an ant falls off the pole
before T seconds, print ‘Fell off’ for that ant. Print an empty line after each test case.
输入/输出样例
输入格式
2 10 1 4 1 R 5 R 3 L 10 R 10 2 3 4 R 5 L 8 R
输出格式
Case#1: 2 Turning 6 R 2 Turning Fell off Case#2: 3 L 6 R 10 R
C++解答
#include<iostream> #include<cstdio> #include<cmath> using namespace std; const int maxn = 10000+10; typedef struct Ants { int site; // 蚂蚁距离木棍左端的距离 char direction; // 朝向 bool flag0; // 判断蚂蚁是否可以移动 bool flag1; // 标志变量判断是否仍在木棍上 bool flag2; // 标志变量判断是否正在相撞,true 表示不想撞，false 表示相撞 }Ants; Ants ant[maxn]; // 初始化判断蚂蚁是否可以移动的变量置true void initflag0(int n) { for(int i = 0; i < n; i++) { ant[i].flag0 = true; } } // 初始化判断蚂蚁位置是否有重复的标志变量，全赋值为true void initflag2(int n) { for(int i = 0; i < n; i++) { ant[i].flag2 = true; } } // 判断蚂蚁是否可以移动 void ablemove(int n) { initflag0(n); // 标志变量赋初值 for(int i = 0; i < n; i++) { for(int j = 0;ant[j].flag0 && j < n && j != i; j++) { // 如果两只蚂蚁面对面 // 那么他们两个不移动，只是改变方向 if(ant[i].direction == 'R' ) { if(ant[j].direction == 'L') { if(ant[j].site-ant[i].site == 1) { ant[i].flag0 = false; ant[j].flag0 = false; } } } else { if(ant[j].direction == 'R') { if(ant[i].site-ant[j].site == 1) { ant[i].flag0 = false; ant[j].flag0 = false; } } } } } } // 判断蚂蚁位置是否有重复的 void repeatPosition(int n) { initflag2(n); // 标志变量赋初值 for(int i = 0; i < n; i++) { for(int j = 0;ant[j].flag2 && j < n && j != i; j++) { // 如果两个蚂蚁在同一个位置则需要掉头 // 指两个蚂蚁面对面但是中间空着一个格情况 if(ant[i].site == ant[j].site) { ant[i].flag2 = false; ant[j].flag2 = false; } } } } // 判断蚂蚁是否在木棍上 void inWoodStick(int L,int i) { if(ant[i].site < 0 || ant[i].site > L) { ant[i].flag1 = false; } } // 位置重合的蚂蚁转向 void turing(int n) { for(int i = 0; i < n; i++) { if(ant[i].flag2 == false || ant[i].flag0 == false) { if(ant[i].flag2 == false && ant[i].flag0 == false) continue; // 双重否定，就不用改变了 if(ant[i].direction == 'R') ant[i].direction = 'L'; else ant[i].direction = 'R'; } } } int main() { //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); int M; cin >> M; int kcase = 0; // 种类 int T; // 时间 int L; // 木棍长度 int n; // 蚂蚁数量 while(M--) { cin >> L >> T >> n; // 输入位置和朝向 for(int i = 0; i < n; i++) { cin >> ant[i].site >> ant[i].direction; ant[i].flag0 = true; // 默认蚂蚁可以移动 ant[i].flag1 = true; // 默认在木棍上，之后再判断 inWoodStick(L,i); // 判断蚂蚁是否在木棍上 } // 初始化标志变量flag2，判断是否有蚂蚁在同一位置 repeatPosition(n); // 模拟移动过程 for(int t = 0; t < T; t++) { ablemove(n); // 首先判断每只蚂蚁是否可以移动 // 每个蚂蚁移动距离1 for(int i = 0; i < n; i++) { if(ant[i].flag1 == false) continue; // 如果已经不再木棍上则不用计算了 if(ant[i].flag0 == false) continue; if(ant[i].direction == 'R') ant[i].site++; else ant[i].site--; inWoodStick(L,i); // 判断蚂蚁是否在木棍上 } // 判断是否有蚂蚁在同一位置 repeatPosition(n); turing(n); // 如果在同一位置的则转向 } if(kcase++) { cout << endl; } cout << "Case#" << kcase << ":" << endl; for(int i = 0; i < n; i++) { if(!ant[i].flag1) { cout << "Fell off" << endl; continue; } cout << ant[i].site << " "; if(!ant[i].flag2) { cout << "Turning" << endl; } else { cout << ant[i].direction << endl; } } } return 0; }