Dropping water balloons

2024-03-29 02:58
文章标签 water balloons dropping

本文主要是介绍Dropping water balloons,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

It’s frosh week, and this year your friends have decided that they would initiate the new computer science students by dropping water balloons on them. They’ve filled up a large crate of identical water balloons, ready for the event. But as fate would have it, the balloons turned out to be rather tough, and can be dropped from a height of several stories without bursting!


So your friends have sought you out for help. They plan to drop the balloons from a tall building on campus, but would like to spend as little effort as possible hauling their balloons up the stairs, so they would like to know the lowest floor from which they can drop the balloons so that they do burst.


You know the building has n floors, and your friends have given you k identical balloons which you may use (and break) during your trials to find their answer. Since you are also lazy, you would like to determine the minimum number of trials you must conduct in order to determine with absolute certainty the lowest floor from which you can drop a balloon so that it bursts (or in the worst case, that the balloons will not burst even when dropped from the top floor). A trial consists of dropping a balloon from a certain floor. If a balloon fails to burst for a trial, you can fetch it and use it again for another trial.


Input
The input consists of a number of test cases, one case per line. The data for one test case consists of two numbers k and n, 1 ≤ k ≤ 100 and a positive n that fits into a 64 bit integer (yes, it’s a very tall building). The last case has k = 0 and should not be processed.


Output
For each case of the input, print one line of output giving the minimum number of trials needed to solve the problem. If more than 63 trials are needed then print ‘More than 63 trials needed.’ instead of the number.


Sample Input
2 100
10 786599
4 786599
60 1844674407370955161
63 9223372036854775807
0 0
Sample Output
14
21
More than 63 trials needed.
61
63

思路:

动态规划。

转移方程确定了一切就迎刃而解了。

设d(i,j)是i个球j次实验下所能测试的最高层数。

设测试层数为k。

  1. 若在k层气球破了,前k-1层必须能用i-1个球做j-1个实验。则k=d(i-1,j-1)+1最优。
  2. 若没破,则之后的楼层必须得用i个球全做。则d(i,j)-k=d(i,j-1)。

则d(i,j)=k+d(i,j-1)=d(i-1,j-1)+d(i,j-1)+1。即为转换方程。

之后就是根据条件确定最终答案了。

#include<iostream> 
#include<string.h>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
const int K=100;
const int A=63;
ll d[K+1][A+1];
int main()
{	//打表 for(int i=1;i<=K;i++)for(int j=1;j<=A;j++){d[i][j]=d[i-1][j-1]+1+d[i][j-1];//printf("%lld\n",d[i][j]);}int k;ll n;while(scanf("%d %lld",&k,&n)!=EOF&&k){int ans=-1;for(int i=1;i<=A;i++){if(d[k][i]>=n){ans=i;break;}}if(ans<0)printf("More than 63 trials needed.\n");else printf("%d\n",ans);}return 0;
}

这篇关于Dropping water balloons的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/857416

相关文章

LeetCode - 11. Container With Most Water

11. Container With Most Water  Problem's Link  ---------------------------------------------------------------------------- Mean:  给你一个N条垂直于x轴的直线,从中找两条直线和x轴组成一个桶状容器,使得这个容器的容量最大. analyse:

LeetCode - 42. Trapping Rain Water

42. Trapping Rain Water  Problem's Link  ---------------------------------------------------------------------------- Mean:  在坐标上给你一些竖直放置的条形积木,问你这个积木能够容纳多少液体. analyse: 首先找出最高的积木,然后从前往后一直

【POJ】2976 Dropping tests 01分数规划

传送门:【POJ】2976 Dropping tests 题目大意:给你长度为n的一对整数a[],b[](注意是一对的),根据式子可以得到:∑a[ i ] / ∑b[ i ],现在给你整数k,你可以从n个中剔除k对,问剩下的根据式子能得到的最大值是多少,答案*100并且四舍五入精确到个位。 题目分析: 很清晰的01分数规划,设Q(L) = ∑a[ i ] - L * ∑b[ i

Container With Most Water (Java实现)

当看见这道题时想到的一个答案就是暴力破解,附上代码 <span style="font-size:18px;"><span style="font-size:18px;">package com.alibaba;import java.util.Scanner;public class Solution{public int maxArea(int[] height){int maxCapac

POJ 2976 Dropping tests (最大化平均值)

题目链接:click here~~ 【题目大意】给你n个分数的值,要求最小不选k个,使得最后分数相加结果平均值最大 【解题思路】:最大化平均值:参见:click here~~ 代码: #include <stdio.h>#include <math.h>#include <string.h>#include <iostream>#include <algorithm>usi

Container With Most Water问题及解法

问题描述: Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Fi

【LeetCode最详尽解答】42-接雨水 Trapping-Rain-Water

欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家! 链接: 42-接雨水 直觉 通过可视化图形来解决这个问题会更容易理解和解决。 给定输入: height = [0,1,0,2,1,0,1,3,2,1

TOJ 4369 ZOJ 3632 Watermelon Full of Water / 线段树优化DP

Watermelon Full of Water 时间限制(普通/Java):3000MS/9000MS     运行内存限制:65536KByte 描述 Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very much and they

Oceanis URP Pro Water Framework(海洋水面特效插件)

Oceanis URP Pro是ARTnGame生产的URP新供水系统。该系统由URP从头开始制作,以获得最大的视觉质量。 重要: 请注意,这是Oceanis URP Pro的第一个版本,因此将根据用户反馈进行额外开发以达到完美,并将是第一个测试版,如有任何问题和建议,请在ARTnGAME Discord频道留言。 该系统将处于测试阶段一段时间,直到所有功能都投入使用并经过更广泛的测试。 重要

leetcode-42. Trapping Rain Water

leetcode-42. Trapping Rain Water 题目: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For examp