Uva10934 Dropping Water balloons 【Dp】

tonyfang posted @ 2016年7月29日 08:17 in uvaoj with tags c++ OI , 525 阅读



转化模型,猜$[1, n]$内的数$Y$,每次猜一个$X$,你会得到回答$X>Y$或$X=Y$或$X>Y$。在最多猜k次$X>Y$的情况下,最少猜多少次才能猜对。

设f[i, j]表示用了i次询问,得到了j次$X>Y$的回答后游戏就会结束的情况下,最多测出多长。

$f[i,j] = f[i-1, j-1] + f[i-1, j] + 1$


后面的答案就是找到最小的$ans$使得$f[ans][k] >= N$


// Uva Online Judge 10934
# include <stdio.h>
# include <algorithm>

using namespace std;

long long f[101][101];
int k;
long long n;

int main() {
	for (int i=1; i<=63; ++i)
		for (int j=1; j<=63; ++j)
			f[i][j] = f[i-1][j] + f[i-1][j-1] + 1;
	while(~scanf("%d%lld", &k, &n) && k) {
		int ans;
		k = min(63, k);
		bool ok=1;
		for (int i=0; i<=63; ++i)
			if(f[i][k] >= n) {
				ans = i;
				ok = 0;
		if(ok) {
			puts("More than 63 trials needed.");
		} else {
			printf("%d\n", ans);
	return 0;

RNFI Login 说:
2022年11月09日 19:22

Online money transactions offer security and ease of transfer, reducing the fear of theft. The tech industry has developed significant platforms to help in digital financial transactions. RNFI Login RNFI is an exclusive digital transfer service designed to help retailers, distributors, and users send and receive money online. The RNFI offers several rewards to users (B2B) for conducting financial transactions using the platform.

Khajane 2 Login 说:
2023年1月23日 14:50

K2 challan also referred to as Khajane 2, an integrated financial management system from the Government of Karnataka. The K2 has been brought into working with an aim to manage the financial business of the government. Khajane 2 Login It works to simplify the process of remittance of departments under government by bringing an option of anywhere-anytime payment options. Firstly every department under the government of Karnataka will have access to Khajane 2 which allows their customers to remit to the government through the easy payment links provided.

登录 *

loading captcha image...
or Ctrl+Enter