← 返回题目列表

AtCoder · ijpc_submission

C. 提交

中文机器翻译题面 查看原题

今年是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
    您对此子任务的得分是 如果getT(N, M) 实施 返回错误值,即使一次, 0 点,否则为每个测试用例计算的值 它是 P(N, M) 定义 的最小值。

实施细节

制限

  • 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