首页 > 代码库 > UVa 10889 - The Lost Gift

UVa 10889 - The Lost Gift

题目:给你R个红球和B个黑球,从这些球中取出相同颜色的概率是50%;

            然后丢了一些黑球,剩下的黑球不少于原来的70%;

            现在给你红球和剩下的黑球个数,求可能丢了几个黑球。

分析:数学题。

            首先,根据组合数学列出等式2*[C(n,2)+C(m,2)] = C(m+n,2):

                        解得 m = 0.5*(2*n+1±sqrt(8*n+1));

            然后,进行判断:

                        1.m不是整数,则红球非法;

                        2.m是整数,丢的球不在0-30%之间,黑球非法;

                        3.都合法的情况下,输出丢失的黑球个数即可。

            方法2:通项公式法(前n项和),通过观察数据可知红球和黑球个数满足如下条件:

                         (a【k】,a【k-1】)或者(a【k】,a【k+1】)

                         a【k】= sum(1,k)= k*(k+1)/ 2

                         可知 C(a【k】+a【k-1】,2)= 2 *(C(a【k】,2)+C(a【k-1】,2))

                         给据通项公式,找到前面和后面的项即为解。(可打表计算,略)

说明:有可能有2个解,判断时直接用<=0.3不要加精度控制。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;

int ans[5];

int main()
{
	int R,B;
	while ( cin >> R >> B && R+B ) {
		int r = (int)sqrt(8*R+1.0);
		if ( r*r == 8*R+1 && r%2 ) {
			int b1 = (2*R+1-r)/2;
			int b2 = (2*R+1+r)/2;
			int count = 0;
			if ( b1 >= B && (b1-B+0.0)/b1 <= 0.3 )
				ans[count ++] = b1-B;
			if ( b2 >= B && (b2-B+0.0)/b2 <= 0.3 )
			if ( !count || ans[0] != b2-B )
				ans[count ++] = b2-B;
			if ( count ) {
				for ( int i = 0 ; i < count ; ++ i ) {
					if ( i ) printf(" ");
					printf("%d",ans[i]);
				}printf("\n");
			}else cout << "No. of black balls invalid" << endl;
		}else cout << "No. of red balls invalid" << endl;
	}
	return 0;
}