[入门赛 #10] Hack Problem P

题目背景

这是一道 **hack 题**。在此类型的题目中,你将得到若干个问题和若干个解决对应问题的代码,但是给出的代码不能对于某些输入给出正确的输出。不能给出正确的输出的情况包括: 1. 输出错误的结果。 2. 运行超时。 3. 产生一些运行时未定义行为。目前技术可检测的未定义行为仅包括数组越界。 对于每个问题,你需要提交一份符合要求的输入数据,使得给定的代码不能给出正确的输出。你可以直接使用『提交答案』功能,也可以提交一份以任何语言写成的数据生成器。 --- **提示:如果你使用提交答案功能,请在提交其他题目时记得将语言改回你所使用的语言**

题目描述

以下给出三个问题的题目描述: #### 问题 1 给出两个正整数 $x, y$,保证它们的最小公倍数($\mathrm{lcm}$)不大于 $10^9$。求它们的最小公倍数。 #### 问题 2 **多组数据**,给定一个长度为 $n$ 的数组 $[a_1, a_2, \dots a_n]$,保证数组单调递增。有 $q$ 次询问,每次给出一个整数 $x$,求数组中有多少数小于等于 $x$。 #### 问题 3 **多组数据**,给定一个长度为 $n$ 的数组 $[a_1, a_2, \dots a_n]$,有 $q$ 次询问,每次给出一个整数 $x$,求数组中有多少数小于等于 $x$。 注:问题 $2$ 和问题 $3$ 除了在是否保证数组递增上有差异外,在数据范围上也有区别,见下。

输入输出格式

输入格式


#### 问题 1 输入只有一行两个整数,依次表示 $x$ 和 $y$。 #### 问题 2 第一行是一个整数 $T$,表示测试数据组数。 接下来按顺序给出每组数据的输入。 每组数据第一行是两个整数,依次表示数组 $a$ 的长度 $n$ 和询问次数 $q$。 每组数据第二行有 $n$ 个整数,依次表示 $a_1, a_2, \dots a_n$。 每组数据第三行有 $q$ 个整数,依次表示 $q$ 次询问给出的 $x$。 #### 问题 3 第一行是一个整数 $T$,表示测试数据组数。 接下来按顺序给出每组数据的输入。 每组数据第一行是两个整数,依次表示数组 $a$ 的长度 $n$ 和询问次数 $q$。 每组数据第二行有 $n$ 个整数,依次表示 $a_1, a_2, \dots a_n$。 每组数据第三行有 $q$ 个整数,依次表示 $q$ 次询问给出的 $x$。

输出格式


#### 问题 1 输出只有一行一个整数,表示两数的最小公倍数。 #### 问题 2 对每组数据,输出一行 $q$ 个整数,依次表示每次询问的答案。 #### 问题 3 对每组数据,输出一行 $q$ 个整数,依次表示每次询问的答案。

输入输出样例

输入样例 #1

3 4

输出样例 #1

12

输入样例 #2

2
3 3
5 7 9
7 7 7
3 3
1 2 3
2 2 2

输出样例 #2

2 2 2 
2 2 2 

输入样例 #3

2
3 3
4 4 5
4 5 6
3 3
1 1 3
1 2 3

输出样例 #3

2 3 3
2 2 3

说明

### 样例组与实际输入的说明 三个样例分别对应三个问题的样例输入输出。 如果你直接采用『提交答案』的方式,请分别将三个输入数据命名为 `1.in`、`2.in`、`3.in`,并打成 zip 压缩包进行提交; 如果你采用提交数据生成器的方式,你的生成器可以从标准输入读入一个整数 $x$,满足 $1 \leq x \leq 3$,表示该测试点对应的问题编号,然后**输出对应的输入数据**。 显然,你的程序不应该读入『输入格式』里提到的任何内容(而应该构造它们),也不应该输出『样例输出』里提到的任何内容(而是只输出你构造的输入数据)。你不应该使用样例测试你的程序,这只是对三个问题的样例说明。 ### 数据规模要求 你给出的数据必须满足如下要求: 1. 完全符合『输入格式』的规定,不能有多余的输入,但是可以有行末空格和文末回车。 2. 数据中所有的数字都应为整数。 3. 对于问题 1,$1 \leq x, y \leq 10^9$,且你**必须保证**两数的最小公倍数也不超过 $10^9$。 4. 对于问题 2,$1 \leq T \leq 3$,$1 \leq n,q \leq 10^5$,$1 \leq a_i, x \leq 10^9$。 5. 对于问题 3,$1 \leq T \leq 3$,$1 \leq n, q, a_i, x \leq 10^6$。 ### 目标代码 你需要 hack 如下的代码: #### 问题 1 ```cpp #include <iostream> #include <algorithm> int main() { int x, y; std::cin >> x >> y; int ans = x * y / std::__gcd(x, y); std::cout << ans << std::endl; } ``` #### 问题 2 ```cpp #include <iostream> #include <algorithm> const int maxn = 1000003; int T; int n, q; int a[maxn], b[maxn]; int find(int x) { int l = 1, r = n; int ans = 0; while (l < r) { int mid = (l + r) >> 1; if (a[mid] <= x) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); for (std::cin >> T; T; --T) { std::cin >> n >> q; for (int i = 1; i <= n; ++i) { std::cin >> a[i]; } for (int x; q; --q) { std::cin >> x; std::cout << find(x) << " "; } std::cout << std::endl; } } ``` #### 问题 3 ```cpp #include <iostream> const int maxn = 1000003; int T; int n, q; int a[maxn], b[maxn]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); for (std::cin >> T; T; --T) { std::cin >> n >> q; for (int i = 1; i <= n; ++i) { std::cin >> a[i]; } for (int i = 1; i <= n; ++i) { b[a[i]]++; } for (int i = 1; i < maxn; ++i) b[i] += b[i - 1]; for (int x; q; --q) { std::cin >> x; std::cout << b[x] << " \n"[q == 1]; } } } ``` 目标代码的编译选项为 `-std=c++14 -fno-asm -O2`。编译器为洛谷提供的 g++。你可以在『在线 IDE』中选择 C++14 语言来获得完全相同的编译环境。 ### 判分说明 本题共三个测试点,分别对应三个问题,每个问题 hack 成功则对应测试点返回 accepted。 #### 数据判定 你给出的数据必须完全符合『数据规模要求』,否则将得到 Unaccepted 的结果。 #### 超时判定 程序每执行若干条指令,我们会检测一遍程序的运行时间。我们保证两次检测之间的指令条数是一个输入规模无关的量,也即每执行 $O(1)$ 条指令会进行一次检测。且两次检测之间的指令条数不会太多,一般不超过 $100$ 条 C++ 语句。 如果程序的运行时间超过 $500 \text{ms}$,则判定为程序运行超时,返回 accepted 结果。 #### 结果错误判定 如果程序在规定的时间内结束且给出了一个输出,我们会比较这个输出和**完全正确的输出**,如果二者不同,则判定为 hack 成功,返回 accepted 结果。 #### 未定义行为判定 我们会在每次**显式**的调用数组元素前判断数组下标是否超过数组范围,如果超过,则判定为 hack 成功,返回 accepted 结果。 这就是说,如果你希望通过未定义行为进行 hack,只能对显式的调用数组元素的行为进行 hack。 ### 样例程序 这是一份可以帮你理解你需要输出的内容的样例程序,**但它不能给出正确的 hack 数据**。直接提交此程序不会得分。 ```cpp #include <iostream> using namespace std; int main() { int taskId; cin >> taskId; if (taskId == 1) { cout << "" <<endl; } else if (taskId == 2) { cout << "" << endl; } else if (taskId == 3) { cout << "" << endl; } else { // 这个 else 不会被执行 cout << "QiHai Nanami" << endl; } } ``` 如果你使用『提交答案』功能,请务必保证打开压缩包后能且仅能**直接**看到三个 `.in` 文件。这就是说,文件结构必须是: ```plain ans.zip |---1.in |---2.in |---3.in ``` 三个文件不应该被额外的文件夹包含,即文件结构不能是: ```plain ans.zip |---ans(folder) |---1.in |---2.in |---3.in ``` ### 关于评测信息的说明 如果 hack 成功,对应测试点的信息为 accepted。如果返回其他信息,说明程序本身有误。 例如,如果返回 TLE,不代表成功的将对应程序 hack 至超时,而是表示数据生成器本身运行超时,测试点不得分。 特别的,返回 UKE 结果可能是数据不合法(有多余内容、缺少内容或数据范围不符合要求)。