题目类型

这是一道提交函数题 / 交互式库函数题。

题目描述

在这道题中，你需要与评测程序进行交互，找出一个由评测程序构造的数组 A 的全局最小值。数组共有 N 个元素，元素均为整数，并满足以下两个性质：

1. 相邻两个元素之差的绝对值恰好为 1，也就是说，对任意 0 <= i < N-1，都有：

   • A[i] - A[i+1] = 1，或
   • A[i] - A[i+1] = -1

2. 恰好存在 K 个下标 i1, i2, ..., iK，使得下面这 K+1 个子数组中，每一个都是严格单调的，并且相邻子数组的单调方向交替：

   • A[0..i1]
   • A[i1..i2]
   • ...
   • A[iK..N-1]

   也就是说，这些子数组要么呈现“严格递增、严格递减、严格递增、...”的交替形式，要么呈现“严格递减、严格递增、严格递减、...”的交替形式。

显然，这样的单调段一共有 K+1 段。

例如，数组：

{4, 5, 6, 7, 6, 5, 6, 7, 8, 9, 10}

满足条件，其中恰有两个拐点，对应的三个单调段为：

{4, 5, 6, 7}
{7, 6, 5}
{5, 6, 7, 8, 9, 10}

你的程序每次可以提出一个问题：

下标 j 处元素的值是多少？

评测程序会返回 A[j] 的值。

你的目标是在查询次数尽量少的前提下，找出数组中的最小元素值。

你需要实现的函数

你需要实现如下函数：

long long play(long long N, int K);

该函数会被评测程序调用一次。
它需要通过多次调用评测程序提供的函数与之交互，最终返回数组中的最小值。

评测程序提供的查询函数为：

long long query(long long index);

调用 query(index) 后，评测程序返回 A[index] 的值。

当你认为已经找到答案时，play() 应返回该最小值。

提交要求

你需要提交文件 findminimum.cpp。
该文件中必须包含函数 play() 的实现。

它可以包含实现 play() 所需的其他辅助代码，但不能包含 main()。

并且文件开头必须包含：

#include "findminimum.h"

样例交互说明

假设隐藏数组为：

{6, 5, 4, 3, 4}

当然，参赛者本身并不能直接看到这个数组。

评测程序调用：

play(5, 1)

下面是一种最朴素的交互过程：

play 查询的下标	评测程序返回值	说明
0	6	当前最小值为 6
1	5	当前最小值更新为 5
2	4	当前最小值更新为 4
3		当前最小值更新为 3
4		当前最小值仍为 3

最后，play() 返回 3。

显然，这样一定能找到正确答案，但查询次数太多了。

数据范围

• 3 <= N <= 10^18
• 1 <= K <= 30

数组元素类型为 long long。

评分与子任务

每个测试文件会包含若干组样例，它们具有相同的 N、K 以及同一个允许的最大 query() 调用次数。

也就是说，在同一个测试中，函数 play() 会被调用多次。
如果你使用了全局变量或全局结构，请注意它们在多次调用之间的影响。

要获得某个子任务的全部分数，你的程序在该子任务的每个测试样例上：

• 都必须返回正确答案；
• 并且 query() 的调用次数不能超过该子任务允许的上限。

子任务	分值	N 范围	query() 最大调用次数
1	5	N <= 1000	1000
2	30	N <= 10^9
3	35	N <= 10^18	70
4	30		35

本地测试

为了方便你在本地测试 play()，题目提供了文件：

• Lgrader.cpp
• findminimum.h

将它们与你的 findminimum.cpp 一起编译后，就可以在本地测试。

本地评测程序的输入格式如下：

第一行输入四个正整数：

N K T QL

其中：

• N：数组长度
• K：拐点个数
• T：该测试中包含的样例数
• QL：每个样例允许的最大 query() 调用次数

之后对于每个样例，会给出 K+2 行，每行两个整数，表示数组在“改变方向”的关键点：

• 第一行一定对应下标 0 及 A[0]
• 最后一行一定对应下标 N-1 及 A[N-1]

本地评测输出

本地评测程序对每个样例输出一行，包含两个整数：

• 你的 play() 返回的全局最小值
• 你的程序调用 query() 的次数

发送自定义测试到系统

你也可以向评测系统提交自定义测试。
其输入格式与本地测试时 Lgrader 所使用的输入格式完全相同，返回结果也相同。