#P1005. 高空抛物

高空抛物

当前没有测试数据。

本题征求 std、数据。

题目背景

这是一道交互题

题目描述

小猪佩奇想要测试弟弟乔治的恐龙的坚硬程度 GG。她的家是一幢 nn 层的高楼。她每次可以选择一个正整数 kk,并在第 kk 层楼扔下恐龙。如果 G<kG< k,那么恐龙会碎掉。佩奇想知道,在摔碎 WW 个恐龙以内的前提下,GG 的值,以及最少需要扔多少次才能求出 GG

但是佩奇觉得扔恐龙太麻烦了,还得自己下去捡,所以把这个任务交给了你。

格式

你需要编写一个函数 Dina(int n, int W),其中 nnWW 的含义如题目所述。该函数返回一个整数 GG,含义如题目所述。如果 GG 与答案不符,这个测试点你将「不得分」。

你可以调用 Throw(int k) 来扔恐龙。该函数返回一个布尔,表示恐龙是否碎掉。如果你已经摔碎了 WW 只恐龙,那么程序将结束,这个测试点你将「不得分」。

特别地,如果你调用函数 Throw 的次数 ww 超过答案调用的次数,但是在时间限制范围内返回了正确的 GG,这个测试点你将「获得 3030 分」。

样例数据

n = 3
W = 2
G = 1
Dina(n, W) = 1 
w = 0

样例 1 解释

在样例中,佩奇拥有心灵感应,没有扔恐龙就知道了 GG 的值。

数据规模与约定

对于 100100% 的数据,0Gn2×1060\leq G\leq n\leq 2\times 10^61Wn1\leq W\leq n