Source

Problem Id:2674  User Id:suibian 
Memory:8056K  Time:734MS
Language:GCC  Result:Wrong Answer

Source 

#include <stdio.h>
#include <math.h>

int n;
double x[32100], L, v;
char name[32100][260];
int start;
int d[32100];

int dblcmp(double a, double b)
{
	if(fabs(a-b)<1e-5) return 0;
	if(a>b) return 1;
	return -1;
}

int init()
{
	int i, maxi;
	double max, t;
	char str[100];

	scanf("%lf%lf", &L, &v);
	for(i=1;i<=n;i++) {
		scanf("%s%lf%s", str, &x[i], name[i]);
		if(str[0]=='p' || str[0]=='P') d[i]=1;
		else d[i]=-1;
	}

	max=-1;
	for(i=1;i<=n;i++) {
		if(d[i]==1) t=(L-x[i])/v;
		else t=x[i]/v;
		if(dblcmp(t, max)>0) {
			max=t;
			start=i;
		}
	}
max=((int)(max*100))/100.0;
	printf("%13.2lf ", max);
}

int solve()
{
	int p, q, i;
	double pos;

	p=start;
	if(d[p]==1) pos=L;
	else pos=0;
	while(1) {
		if(d[p]==1) {
			i=p;
			q=p;
			while(dblcmp(x[i], pos)<=0 && i<=n) {
				if(d[i]==-1) q=i;
				i++;
			}
		}
		else {
			i=p;
			q=p;
			while(dblcmp(x[i], pos)>=0 && i>=1) {
				if(d[i]==1) q=i;
				i--;
			}
		}

		if(p==q) break;
		pos=.5*(x[p]+x[q]);
		p=q;
	}

	printf("%s\n", name[p]);
}

int main()
{
	while(scanf("%d", &n)==1 && n) {
		init();
		solve();
	}

	return 0;
}