首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。