pku1650.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 80 行

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

int main()
{
	double A, min, tmp, mindis;
	int L, i, j, min1, min2, tI;

//	freopen("in.dat", "r", stdin);

	while (scanf("%lf %d", &A, &L) != -1)
	{
		if (fabs(A - 0.0) < 1e-8)
		{
			printf("0 1\n");
			continue;
		}

		if (A > L)
		{
			printf("%d 1\n", L);
			continue;
		}
		
		min = 1;
		if (A > 1)
		{
			min1 = (int)(A + 0.5);
			min2 = 1;
			min = fabs(min1 - A);
			for (i = 1; A * i < (double)L; i++)
			{
				tmp = fabs((int)(i * A + 0.5) / (double)i - A);
				if (tmp < min)
				{
					min1 = (int)(i * A + 0.5);
					min2 = i;
					min = tmp;
				}
			}
			printf("%d %d\n", min1, min2);
		}
		else
		{
			min1 = (int) (1.0 / A);
			
			if (1.0 / min1 - A > A - 1.0 / (min1 + 1))
			{
				min1 += 1;
			}
			min2 = 1;
			mindis = fabs(1.0 / min1 - A);

			for (i = 1; i < A * L; i++)
			{
				tI = (int)(i * 1.0 / A);
				tmp = fabs(i * 1.0 / tI - A);
//				printf("Ti = %d, tmp = %.2lf mindis = %.2lf\n", tI, tmp, mindis);
				if (tmp < mindis)
				{
					min2 = i;
					min1 = tI;
					mindis = fabs(i * 1.0 / tI - A);
				}
				tI += 1;
				if (fabs(i * 1.0 / tI  - A) < mindis)
				{
					min2 = i;
					min1 = tI;
					mindis = fabs(i * 1.0 / tI - A);
				}

			}
			printf("%d %d\n", min2, min1);
		}
	}
	
	return 0;
}