luogu#P10735. [NOISG2019 Prelim] Square or Rectangle?

    ID: 14672 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>数学2019二分交互题Special JudgeNOISG(新加坡)

[NOISG2019 Prelim] Square or Rectangle?

题目背景

翻译自 NOISG2019 Prelim D.Square or Rectangle?

请注意,本题为交互题,请尽量使用 C++ 进行作答。同时,你只需要实现题目中要求的函数不要将答案输出在标准输出。

题目描述

现在有一个 N×NN\times N 的网格,网格内有一个至少占网格总大小 4%4\% 的矩形。但是,你现在不知道这个矩形是长方形还是正方形,你需要定义一个函数来完成这个问题。

【实现细节】

你需要定义以下函数:

bool am_i_square(int N, int Q)

  • NN:网格的大小
  • QQ:能询问评测机的次数。

为了确定形状,你可以向评测机至多调用 QQbool inside_shape(int X, int Y) 函数。调用这个来询问评测机方格 (X,Y)(X,Y) 是否在这个矩形中。

一旦你确定了形状,你就可以返回一个 bool 类型的量,代表这个矩形是否为正方形

评测机会调用你的函数 TT 次。TT 的大小见【数据范围与评测方法】。

输入格式

见【实现细节】。

输出格式

见【实现细节】。

提示

【样例】

考虑以下调用:

am_i_square(5, 25)

这表示这是一个 5×55 \times 5 大小的网格,你可以调用至多 2525 次。

inside_shape(3, 3) = true

这询问了方格 (3,3)(3,3) 是否在矩形内,它在正方形的正中间,所以返回 true

inside_shape(5, 4) = false

这询问了方格 (5,4)(5,4) 是否在矩形内,它不在正方形内,所以返回 false

inside_shape(1, 1) = false

这询问了方格 (1,1)(1,1) 是否在矩形内,它不在正方形内,所以返回 false

inside_shape(2, 4) = true

这询问了方格 (2,4)(2,4) 是否在矩形内,它在正方形的左下角,所以返回 true

综上,我们可以确定这是一个正方形,所以该函数返回 true

【数据范围与评测方法】

对于 100%100\% 的测试点:N=100,1T1000N=100,1\leq T \leq 1000。 | Subtask\text{Subtask} | 分值 | 附加条件 | | :----------: | :----------: | :----------: | | 00 | 1414 | Q=104Q=10^4 | | 11 | 1919 | Q=100Q=100 | | 22 | 1818 | Q=40Q=40,图形至少占网格总大小的 25%25\% | | 33 | 4949 | Q=50Q=50,得分见下文 |

【Subtask 3 的计分方法】

记你在所有调用中最大使用了 qq 次询问。

  • q>50q >50,你得到 00 分。
  • 34q5034 \leq q \leq 50,你得到 4030×q341740-30\times \frac{q-34}{17} 的分数。
  • q33q \leq 33,你得到满分。

【提示】

请在你的函数前加上以下内容:

#include <bits/stdc++.h>
using namespace std;
extern "C" bool inside_shape(int x,int y);

同时,请在你的 bool am_i_square(int N, int Q) 前加上extern "C"