Time Limit: 4000msMemory Limit: 65536KB 64-bit integer IO format: %lld Java class name: Main Prev Submit Status Statistics Discuss Next Font Size: Type: Andrew the Ant is fascinated by the behavior of his friends. Thousands of them are marching their paths on and on. They can build highly organized ant-hills. Sometimes, however, they act a little bit stupidly. Recently, Andrew watched his fellow ants marching on top of a long piece of wood. He noticed their behavioral pattern is very simple: Each ant walks slowly forward with a constant speed of 1 cm per second. Whenever it meets another ant, both of them only touch with their antennae and immediately turn around and walk the opposite direction. If an ant comes to the end of the wood, it falls down and does not affect other ants anymore. The picture above shows an example of moving ants in time 0 s. In one second, the ants E and A meet at position 2 and change their directions. The ant A then meets B in the next 1.5 seconds. At the same time (2.5 seconds after the start), the ants C and D will meet too. All four of them change their directions. In the next 0.5 second (time 3 s), the first ant (E) falls down off the left end, etc. Your task is to simulate the movement of ants. For simplicity, suppose that the ants have zero size (although the picture could suggest something else). Input The input consists of several scenarios. Each scenario starts with a line containing two integer numbers L and A, separated by a space. L is the length of the wood in cms (1 ≤ L ≤ 99 999), and A is the number of ants at the beginning of the simulation (1 ≤ A ≤ L + 1). Then there are A lines, each containing a positive integer Xi, one space, and an uppercase letter. The number (0 ≤ Xi ≤ L) specifies the position of the i-th ant and the letter its initial direction: either “L” for left (towards zero) or “R” for right. No two ants will start at the same position. Output For each scenario, you should print a single line containing the text “The last ant will fall down in T seconds - started at P.”, where T is the exact time when the last ant (or two) reaches the end of the wood, and P is the position where that particular ant has originally started in time 0. If two last ants fall down at the same time, print “started at P and Q”, indicating both of their positions, P <Q. Sample Input 90000 1 0 R 10 1 0 L 14 5 3 L 6 L 13 L 8 R 1 R Sample Output The last ant will fall down in 90000 seconds - started at 0. The last ant will fall down in 0 seconds - started at 0. The last ant will fall down in 13 seconds - started at 6 and 8. Hint (The last sample input scenario corresponds to the picture.) Source CTU Open Contest 2012 題意：給出a個螞蟻的位置和其正在行走的方向，若相碰則都轉向，若到邊緣則掉下去，每秒鐘走一格， 問最後一只（或兩只）螞蟻是什麼時候掉下去的，其初始位置在什麼地方； 思路：(參考同學的 ) （以劉汝佳的某題的解題思路為背景） 螞蟻看作質點，如圖，Ａ左走，Ｅ右走，顯然Ａ和Ｅ碰後Ｅ左走，而Ｅ的左走就相當於Ａ向左走的一個延續，同理Ａ相當於Ｅ的延續，這樣，n秒後各個螞蟻的位置就相當於每個螞蟻不轉向走n秒後的位置，但這時僅僅只是所有位置確定了，但該位置我螞蟻並不確定；又由於相碰後轉向，實際上每個螞蟻的相對順序沒變，如圖，五只螞蟻，初始位置分別為１ ３ ６ ８ １３，則３秒後五只螞蟻的位置為４ ０ ３ ５ １０（即 ０ ３ ４ ５ １０），最後要確定這五個位置分別是哪幾個螞蟻時，就根據原來的相對順序就知道Ｅ在０，Ａ在３，Ｂ在４，Ｄ在５，Ｃ在１０；若要找最後一個掉下去的時間，則要找到最右邊那個向左走的螞蟻和最左邊那個向右走的螞蟻，比較一下就行了； 代碼是我的 [cpp] #include<stdio.h> #include<algorithm> using namespace std; struct haha { int s; char flag; }ant[100000]; int aa[100000]; int cmp(struct haha a,struct haha b) { return a.s>b.s; } int main() { int i,len,n,time,left,right,cnt,n1,n2; while(scanf("%d %d",&len,&n)!=EOF) { right=len; left=0; for(i=0;i<n;i++) { scanf("%d %c",&ant[i].s,&ant[i].flag); } sort(ant,ant+n,cmp); for(i=n-1;i>=0;i--) if(ant[i].flag=='R')//向右跑 { right=ant[i].s; break; } for(i=0;i<n;i++) if(ant[i].flag=='L')//向左跑 { left=ant[i].s; break; } time=len-right>left?len-right:left; for(i=0;i<n;i++) if(ant[i].flag=='R') aa[i]=ant[i].s+time; else aa[i]=ant[i].s-time; sort(aa,aa+n); cnt=0; for(i=0;i<n;i++) { if(aa[i]==0||aa[i]==len) { cnt++; if(cnt==1) n1=ant[n-1-i].s; if(cnt==2) n2=ant[n-1-i].s; } } if(cnt==1) printf("The last ant will fall down in %d seconds - started at %d.\n",time,n1); else printf("The last ant will fall down in %d seconds - started at %d and %d.\n",time,n1,n2); } return 0; }
