#B3704. [语言月赛202301] HACK IT!

    ID: 253 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2023提交答案Special JudgeO2优化语言月赛

[语言月赛202301] HACK IT!

题目背景

这是一道 hack 题。在此类型的题目中,你将得到若干个问题和若干个解决对应问题的代码,但是给出的代码不能对于某些输入给出正确的输出。不能给出正确的输出的情况包括:

  1. 输出错误的结果。
  2. 运行超时。
  3. 产生一些运行时未定义行为。目前技术可检测的未定义行为仅包括数组越界。

对于每个问题,你需要提交一份符合要求的输入数据,使得给定的代码不能给出正确的输出。你可以直接使用『提交答案』功能,也可以提交一份以任何语言写成的数据生成器。

题目描述

以下给出三个问题的题目描述:

问题 1

给定两个整数 a,ba, b,请求出 a+ba + b 的值。

问题 2

给定一个仅包含小写字母的字符串 ss,求 ss 中有多少个小写 a 字母。

问题 3

给定一个长度为 nn 的数组 aa(下标从 00 开始),对所有的 ii 满足 0i<n0 \leq i < n,设 bi=ai+1modnaib_i = a_{i + 1 \bmod n} - a_i,这里 i+1modni + 1 \bmod n 表示 i+1i + 1nn 取模的结果。请求出 bb 数组。

输入格式

问题 1

输入包含一行两个整数,用单个空格隔开,依次表示 aabb

问题 2

输入包含一行一个字符串 ss

问题 3

输入包含两行。
第一行是一个整数,表示数列长度 nn
第二行有 nn 个以单个空格隔开的整数,依次表示 a1,a2,ana_1, a_2, \dots a_n

输出格式

问题 1

输出一行一个整数表示答案。

问题 2

输出一行一个整数表示答案。

问题 3

输出一行 nn 个整数,依次表示 b0,b1,bn1b_0, b_1, \dots b_{n - 1}。整数之间用单个空格隔开。

1 1
2
ahpphsomhspldaaaaaa
7
2
1 1
0 0

提示

样例组与实际输入的说明

三个样例分别对应三个问题的样例输入输出。

如果你直接采用『提交答案』的方式,请分别将三个输入数据命名为 1.in2.in3.in,并打成 zip 压缩包进行提交;

如果你采用提交数据生成器的方式,你的生成器可以从标准输入读入一个整数 xx,满足 1x31 \leq x \leq 3,表示该测试点对应的问题编号,然后输出对应的输入数据

显然,你的程序不应该读入『输入格式』里提到的任何内容(而应该构造它们),也不应该输出『样例输出』里提到的任何内容(而是只输出你构造的输入数据)。你不应该使用样例测试你的程序,这只是对三个问题的样例说明。

数据规模要求

你给出的数据必须满足如下要求:

  1. 完全符合『输入格式』的规定,不能有多余的输入,但是可以有行末空格和文末回车。
  2. 对于问题 1,1a,b2×1091 \leq a, b \leq 2 \times 10^9
  3. 对于问题 2,ss 只含小写英文字母,其对应的 ASCII 值应在 [97,122][97, 122] 范围内,ss 的长度应 1\geq 1 且不超过 10610 ^ 6
  4. 对于问题 3,1n1001 \leq n \leq 100109ai109-10^9 \leq a_i \leq 10^9

目标代码

你需要 hack 如下的代码:

问题 1

#include <iostream>

using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  cout << a + b << endl;
}

问题 2

#include <cstring>
#include <iostream>

using namespace std;

char s[1000005];

int main() {
    cin >> s;
    int ans = 0;
    for (int i = 0; i < strlen(s); ++i) {
        if (s[i] == 'a')
            ++ans;
    }
    cout << ans << endl;
    return 0;
}

问题 3

#include <iostream>

using namespace std;

const int maxn = 100;

int a[maxn], b[maxn];

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < n; ++i) {
    b[i] = a[i + 1] - a[i];
    if (i + 1 == n)
      b[i] = a[0] - a[i];
  }
  for (int i = 0; i < n; ++i) {
    cout << b[i] << " \n"[i == (n - 1)];
  }
}

目标代码的编译选项为 -std=c++14 -fno-asm -O2。编译器为洛谷提供的 g++。你可以在『在线 IDE』中选择 C++14 语言来获得完全相同的编译环境。

判分说明

本题共三个测试点,分别对应三个问题,每个测试点 10 分。

数据判定

你给出的数据必须完全符合『数据规模要求』,否则将得到 unaccepted 的结果。

超时判定

程序每执行若干条指令,我们会检测一遍程序的运行时间。我们保证两次检测之间的指令条数是一个输入规模无关的量,也即每执行 O(1)O(1) 条指令会进行一次检测。且两次检测之间的指令条数不会太多,一般不超过 100100 条 C++ 语句。

如果程序的运行时间超过 500ms500 \text{ms},则判定为程序运行超时,返回 accepted 结果。

结果错误判定

如果程序在规定的时间内结束且给出了一个输出,我们会比较这个输出和完全正确的输出,如果二者不同,则判定为 hack 成功,返回 accepted 结果。

未定义行为判定

我们会在每次显式的调用数组元素前判断数组下标是否超过数组范围,如果超过,则判定为 hack 成功,返回 accepted 结果。

这就是说,如果你希望通过未定义行为进行 hack,只能对显式的调用数组元素的行为进行 hack。

样例程序

这是一份可以帮你理解你需要输出的内容的样例程序,但它不能给出正确的 hack 数据。直接提交此程序不会得分。

#include <iostream>

using namespace std;

int main() {
  int taskId;
  cin >> taskId;
  if (taskId == 1) {
    cout << "1 1" <<endl;
  } else if (taskId == 2) {
    cout << "aba" << endl;
  } else if (taskId == 3) {
    cout << "2\n1 1" << endl;
  } else { // 这个 else 不会被执行
    cout << "OvoOvoovOovO" << endl;
  }
}

如果你使用『提交答案』功能,请务必保证打开压缩包后能且仅能直接看到三个 .in 文件。这就是说,文件结构必须是:

ans.zip
 |---1.in
 |---2.in
 |---3.in

三个文件不应该被额外的文件夹包含,即文件结构不能是:

ans.zip
 |---ans(folder)
      |---1.in
      |---2.in
      |---3.in

关于评测信息的说明

如果 hack 成功,对应测试点的信息为 accepted。如果返回其他信息,说明程序本身有误。

例如,如果返回 TLE,不代表成功的将对应程序 hack 至超时,而是表示数据生成器本身运行超时,测试点不得分。

特别的,返回 UKE 结果可能是数据不合法(有多余内容、缺少内容或数据范围不符合要求)。

关于本题的特殊说明

本题是第一道 hack 题,也是试机题。此类型题目的初衷是使得选手可以有针对性地练习代码里的易错点。在『洛谷入门赛 #8』结束后的一周内,你可以任意地尝试攻击 special judge 而不会受到处罚(恶意卡评测、重复提交除外)。被允许的攻击行为包括但不限于尝试提交各种输入数据以期让 special judge 返回错误的结果。如果攻击产生了成果,请在讨论区发帖并 at 一扶苏一。

特别提醒:恶意卡评测的行为包括多次提交导致给出程序运行超时的且无本质区别的数据

需要说明的是,在乐多赛制下,多次尝试提交会造成本题得分降低。