Marching Ants Time Limit: 5000ms, Special Time Limit:12500ms, Memory Limit:65536KB Total submit users: 8, Accepted users: 8 Problem 11301 : No special judgement Problem description Ants! Aren’t they fascinating? Thousands of these insects are marching their paths on and on. They can build highly organized ant-hills. Sometimes, however, they act a little bit stupidly.Imagine that you have a long piece of wood and a couple of ants is walking on top of it. 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 does not suggest this). 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 ≤ 999 999), 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 the zero) or “R” for right. No two ants will start at the same position.The input will be terminated by two zeros in the place of numbers L and A. Output For each test case, you should print a single line containing the text “ The last ant will fall down in T seconds. ”, where T is the exact time when the last ant (or two) will reach the end of the wood. If possible, print the time as an integer, otherwise use exactly one digit after the decimal point. Sample Input 900000 1 0 R 10 1 0 L 14 5 3 L 6 L 13 L 8 R 1 R 0 0 Sample Output The last ant will fall down in 900000 seconds. The last ant will fall down in 0 seconds. The last ant will fall down in 13 seconds. Judge Tips The last sample input scenario corresponds to the picture. Problem Source Central Europe Regional Contest 2007 — Practice Session Submit   Discuss   Judge Status  Problems  Ranklist  果然是很巧妙的一道题! 想通了超级简单! 一开始还哈里哈气的模拟蚂蚁的走法! TL两次!不过还好,睡一觉!还想到了! 很多人都是一次AC!看来高手还多的是啊!!惭愧啊!!!!!!! #include<stdio.h>int main(){ int i; float max,x; char buf,b; int L,A; while(scanf("%d %d",&L,&A)!=EOF) {  if(L==0||A==0) break;  max=0;  for(i=0 ; i<A ; i++)  {   scanf("%f%c%c",&x,&buf,&b);   if(b == 'L')   {    if(x>max)     max=x;   }   else    {    if(L-x>max)     max=L-x;   }  }  if(max==(int)max)   printf("The last ant will fall down in %.0f seconds.\n",max);  else    printf("The last ant will fall down in %.1f seconds.\n",max); } return 0; }     

评论