Background

This is a hack problem. In this type of problem, you will be given several tasks and some code that claims to solve the corresponding tasks, but the provided code cannot produce the correct output for some inputs. Cases where it fails include:

1. Outputting a wrong result.
2. Timing out.
3. Causing some runtime undefined behavior. Currently, the only undefined behavior that can be detected by our system is out-of-bounds array access.

For each task, you need to submit an input that meets the requirements such that the given code cannot produce the correct output. You may directly use the “Submit Answer” feature, or submit a data generator written in any language.

---

Hint: If you use the “Submit Answer” feature, remember to change the language back to the one you use when submitting other problems.

Problem Description

The following are the statements for three tasks:

Task 1

Given $n$ integers, find the number of odd integers among them.

Task 2

Determine whether $p$ is a prime number.

Task 3

Given $n$ integers where the $i$-th one is $a_i$. Find the largest number $p$ such that the number of indices $i$ satisfying $a_i \ge p$ is at least $\left\lfloor \dfrac{n}{2} \right\rfloor$.

Input Format

Task 1

The input contains two lines.
The first line is an integer representing the length of the sequence $n$.
The second line contains $n$ integers separated by single spaces, representing $a_1, a_2, \dots, a_n$ in order.

Task 2

The input contains one line with one integer $p$.

Task 3

The input contains two lines.
The first line is an integer representing the length of the sequence $n$.
The second line contains $n$ integers separated by single spaces, representing $a_1, a_2, \dots, a_n$ in order.

Output Format

Task 1

Output one line with one integer representing the answer.

Task 2

Output one line. If $p$ is prime, output Yes; otherwise output No.

Task 3

Output one line with one integer representing the answer.

3
1 2 3

2

2

Yes

4
1 2 3 4

3

Hint

Notes on samples and actual input

The three samples correspond to the sample input and output of the three tasks respectively.

If you use the “Submit Answer” method, please name the three input files 1.in, 2.in, and 3.in, and submit them as a zip archive.

If you use the data generator method, your generator may read an integer $x$ from standard input, where $1 \leq x \leq 3$, indicating the task ID of the test point, and then output the corresponding input data.

Obviously, your program should not read anything mentioned in the “Input Format” (instead, it should construct them), and it should not output anything mentioned in the “Sample Output” (it should output only the input data you constructed). You should not use the samples to test your program; they are only explanations of the samples for the three tasks.

Constraints requirements

The data you provide must satisfy the following requirements:

1. It must fully follow the “Input Format”. There must be no extra input, but trailing spaces at line ends and a final newline are allowed.
2. All numbers in the data must be integers.
3. For Task 1, $1 \leq n \leq 1000, -2 \times 10^9 \le a_i \le 2 \times 10^9$.
4. For Task 2, $1 \le p \le 10^{12}$.
5. For Task 3, $2 \leq n \leq 100$, $1 \leq a_i \leq 2 \times 10^9$.

Target code

You need to hack the following code:

Task 1

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, ans = 0;
  cin >> n;
  for(int i = 1, x; i <= n; i++) {
    cin >> x;
    if(x % 2 == 1) ++ans;
  }
  cout << ans << endl;
}

Task 2

#include<bits/stdc++.h>
using namespace std;

bool isprime(long long x) {
    if(x == 1) return false;
    for(int i = 2; i * i <= x; i++) {
        if(x % i == 0) return false;
    }
    return true;
}

int main() {
    long long p;
    cin >> p;
    if(isprime(p)) cout << "Yes" << endl;
    else cout << "No";
    return 0;
}

Task 3

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1000 + 7;

int n, a[MAXN];

bool check(int x) {
    int tot = 0;
    for(int i = 1; i <= n; i++) {
        if(a[i] >= x) ++tot;
    }
    return (tot >= (n / 2));
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int L = 1, R = 2000000000, ans;
    while(L <= R) {
        int mid = (L + R) / 2;
        if(check(mid)) ans = mid, L = mid + 1;
        else R = mid - 1;
    }
    cout << ans << endl;
    return 0;
}

The target code is compiled with options -std=c++14 -fno-asm -O2. The compiler is the g++ provided by Luogu. You can select the C++14 language in the “Online IDE” to get exactly the same compilation environment.

Scoring rules

This problem has three test points, corresponding to the three tasks. The scores are $30$ points, $30$ points, and $40$ points respectively.

Data validation

Your data must fully satisfy the “Constraints requirements”, otherwise you will get an Unaccepted result.

Time limit decision

After the program executes a certain number of instructions, we will check its running time once. We guarantee that the number of instructions between two checks is independent of the input size, i.e., a check is performed after every $O(1)$ instructions. Also, the number of instructions between two checks will not be too large, usually no more than $100$ C++ statements.

If the program’s running time exceeds $500 \text{ms}$, it will be judged as time limit exceeded, and an accepted result will be returned.

Wrong answer decision

If the program finishes within the given time and produces an output, we will compare it with the completely correct output. If they differ, the hack is considered successful, and an accepted result will be returned.

Undefined behavior decision

Before every explicit array element access, we will check whether the index goes out of the array bounds. If it does, the hack is considered successful, and an accepted result will be returned.

That is, if you want to hack via undefined behavior, you can only target explicit array element accesses.

Sample program

This is a sample program to help you understand what you need to output, but it cannot generate correct hack data. Submitting this program directly will not get any score.

#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 { // This else will not be executed.
    cout << "QiHai Nanami" << endl;
  }
}

If you use the “Submit Answer” feature, make sure that after opening the zip archive you can directly see three .in files, and only these three files. That is, the file structure must be:

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

The three files should not be placed inside an extra folder, i.e., the file structure must not be:

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

Notes on judging information

If the hack succeeds, the information for the corresponding test point will be accepted. If it returns other information, it means the generator program itself is incorrect.

For example, if it returns TLE, it does not mean you successfully made the target program time out. Instead, it means the data generator itself timed out, and that test point will score zero.

In particular, getting UKE may mean the data is invalid (extra content, missing content, or constraints not satisfied).

Translated by ChatGPT 5