3061574_wa.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

char tmp[100];
struct node
{
	int x, y, z;
}itv[1000000];

int n;
int l, r, mid;


int num(int x,int y,int z)
{
	int k;

	if((y-x)%z==0)
		return y;
	else
	{
		k = (y-x)/z;
		return x+k*y;
	}
}

int input()
{
	n = 0;

	while(1)
	{
		if(gets(tmp)==NULL)
			return 0;
		if(tmp[0]>='0'&&tmp[0]<='9')
			break;
	}
	sscanf(tmp,"%d%d%d",&itv[0].x,&itv[0].y,&itv[0].z);
	l = itv[0].x;r = itv[0].y;
	itv[0].y = num(itv[0].x,itv[0].y,itv[0].z);
	n++;
	while(1)
	{
		if(gets(tmp)==NULL||tmp[0]<'0'||tmp[0]>'9')
			break;
		sscanf(tmp,"%d%d%d",&itv[n].x,&itv[n].y,&itv[n].z);
		itv[n].y = num(itv[n].x,itv[n].y,itv[n].z);
		if(itv[n].x<l)	l = itv[n].x;
		if(itv[n].y>r)	r = itv[n].y;
		n++;
	}
	return n;
}

int solve(int left,int right)
{
	int i, k, ret;
	int ll, rr;

	ret = 0;
	for(i = 0; i < n; i++)
	{
		if(left > itv[i].y || right < itv[i].x)
			continue;
		ll = left;
		if(ll < itv[i].x)
			ll = itv[i].x;
		else
		{
			if((ll-itv[i].x)%itv[i].z!=0)
			{
				k = (ll-itv[i].x)/itv[i].z;
				ll = itv[i].x+(k+1)*itv[i].z;
			}
		}
		rr = right;
		if(rr > itv[i].y)
			rr = itv[i].y;
		else
			rr = num(itv[i].x,right,itv[i].z);
		ret += (rr-ll)/itv[i].z+1;
	}
	return ret;
}

int main()
{
	int cnt;

	while(input())
	{
		cnt = solve(l,r);
		if(cnt%2==0)
		{
			puts("no corruption");
			continue;
		}
		while(l<r)
		{
			mid = l/2+r/2+(l%2==1&&r%2==1);
			cnt = solve(l,mid);
			if(cnt%2==0)
			{
				l = mid+(l==mid);
			}
			else
			{
				r = mid;
			}
		}
		printf("%d %d\n",l,solve(l,l));
	}
	return 0;
}