今年是0x2012,人权意识形态正在迅速膨胀,甚至狐狸也被赋予了参加编程竞赛的权利(到目前为止,它们只有提问的权利)。嗯,这是一个关于算法狐狸二郎参加世界编程大赛的故事。
比赛开始了,二郎立即开始解决问题。尽管这是一场世界级的比赛,但现在被誉为世界上最好的算法之一的 Jiro 没有解决不了的问题。在比赛还剩大约两个小时的时候,完成所有题目后,二郎发现有一个题目的时间限制异常长,数据量也非常大。
当然,Jiro编写的程序即使对于海量数据也能在限定时间内给出答案。不过,说到这里,二郎想到了一种可能。 6199年前在泰国举行的国际信息奥林匹克竞赛,即0x7db,有一个问题:时间限制很长。事实上,这样做的目的是为了给最快回答问题的程序颁发特别奖,而这一事实一直保密到闭幕式。
Jiro 认为也许这个问题有一个特别奖励,所以他开始加速程序。然而,小的改进和削减很快就失去了动力,需要某种重大的加速。因此,Jiro 决定在程序的探索部分添加假剪枝。
这一剪枝标准由一个参数确定。 X 。X 越小,修剪越渐进,越大,修剪越严厉。当然,这种修剪是一个谎言,所以 如果 X 太大,您可能会得到错误的答案。具体来说,阈值 T 已修复,X ≧ T 当 成立时,它变成错误答案。 X<T 当 为真时,它变为已接受。二郎绝对是 我不知道 T 的价值。
顺便说一句,二郎的个人政策始终是“以更少错误答案的方式进行战斗”。因此,如果可能的话,这将是一个错误答案。 不设置 X 我想知道 T 的价值,但我只剩下 2 小时了。太多 更改 X 值时没有时间提交和检查结果。
现在,在抑制错误答案数量的同时,请尽可能少提交。 我应该使用什么策略来确定 T 的值? 有
課題
整数 T 。T 为 0 或更多 M 已知下面是一个整数,但具体值不知道。通过重复以下问题 我想找到 T 的值。
- 一些整数 X 关于 ”X ≧ T 当 成立吗? ” 问
尽可能少问问题 考虑识别 T 。但是,存在以下限制: 您不能提出答案为“是”的问题。 一旦您完成此 N 次,您就不能再提出任何问题。
具有以下参数的过程 getT(N, M) 实施 :
- N -- 可以询问答案为“是”的问题的次数。 表示
- M -- T 上限的整数。 在
getT(N, M) 实施 中 比较(X) 可以重复调用。比较(X) 的规格如下。
- X -- T 要比较的整数。0 ≤ X ≤ M 必须是 。
- 返回值表示问题的答案为“是”(即 X ≧ T 当 成立) 1 或“否”(即 X<T 当 成立) 0 为其中之一。
getT(N, M) 实施 重复问题并隐藏 确定 T 的值并 T 的值必须作为返回值返回。然而 调用 比较(X) 时的返回值为 1 如果它发生 N 次,它就不会再发生了。 请勿致电 比较(X) 。
例
例1
N = 1,M = 4 考虑 的情况。
本例中例如以下策略 可以确定 T 。比较 假设您使用以下参数调用 并得到如下所示的响应。
| 参数 | 返回值 |
|---|---|
| 比较(1) | 0 |
| 比较(2) | 0 |
| 比较(3) | 1 |
此时 2 < T 和 满足 3 ≧ T 自从 因为它是 T = 3 已了解。因此 得到T 必须返回 是 仅由 3 。
例2
N = 2,M = 8 的情况。
在这种情况下,采用以下策略 T 。比较 假设您使用以下参数调用 并得到如下所示的响应。
| 参数 | 返回值 |
|---|---|
| 比较(4) | 1 |
| 比较(1) | 0 |
| 比较(2) | 0 |
| 比较(3) | 1 |
此时 2 < T 和 满足 3 ≧ T 自从 因为它是 T = 3 已了解。因此 得到T 必须返回 是 仅由 3 。
小課題
小課題 1 (25 点)
- N = 1
- 1 ≤ M ≤ 100 000 您可以多次拨打
- getT(N, M) 实施 是 仅由 比较(X) 。
小課題 2 (25 点)
- N = 2
- 1 ≤ M ≤ 1 000 000 您拨打
- getT(N, M) 实施 是 比较(X) 的次数是 必须小于或等于 40 000 倍。
小作业3(最多50分)
- 3 ≤ N ≤ 50
- 1 ≤ M ≤ 1 000 000 000 000
- 重要: 该子任务的得分为
由调用 比较(X) 的次数决定。
此子作业的测试用例 (N、M) 对于 ,该值 P(N, M) 定义 。首先,w 它被转换为格式 wN ≧ M * N! 令 为满足 的最小正整数,W = w + N 。然而 不! 它是 是 仅由 N 的阶乘。 您拨打
- getT(N, M) 实施 是 比较(X) 的次数是 如果小于 W 次 P(N, M) = 50
- α 它被转换为格式 0 < α < 1 和 满足 getT(N, M) 实施 是 比较(X) 的次数是 如果小于 2W-αW 倍, P(N, M) = 50α
- getT(N, M) 实施 是 比较(X) 的次数是 如果小于 2W 如果超过 次 P(N, M) = 0
实施细节
制限
- CPU时间限制:5秒
- 内存限制:64 MB
注意: 堆栈的大小没有固定限制。作为堆栈使用的内存包含在总内存使用量中。
接口 (API)
- 实现文件夹:submission/(原型: 提交.zip)
- 参赛者实现的文件:submission.cpp
- 提交文件接口:submission.h
- 评分程序接口:grader.h
- 评分程序示例:grader.cpp
- 评分程序的示例输入:grader.in.1、grader.in.2、...
注意:示例评分程序按以下格式读取输入。- 1 行目: N、M、T 用空格分隔。
- 评分程序输出
注意:评分程序响应输入将以下内容输出到标准输出。 如果- getT(N, M) 实施 返回错误答案“ 输出NG“。 如果
- N = 1 有正确的实现,那么“好的 1“。 如果
- N = 2 有正确的实现,那么“好的 2“。 如果
- N≧3 有正确的实现,那么“好的 3 P 输出"。但是, P 根据输入的评分标准计算 它是 P(N, M) 定义 的值。
- 问题建议:qnighy
- 问题陈述:JAPLJ