Background

This is a hack problem. In this type of problem, you will be given several questions and corresponding codes to solve them, but the provided code does not produce correct outputs for certain inputs. Incorrect outputs include:

1. Outputting wrong results.
2. Running out of time.
3. Producing undefined runtime behavior. Currently, detectable undefined behaviors only include array out-of-bounds.

For each question, you need to submit input data that meets the requirements, causing the given code to fail to produce correct outputs. You can use the 'Submit Answer' feature directly or submit a data generator written in any language.

Hint: If you use the Submit Answer feature, remember to switch back to your language of choice when submitting other problems.

Problem Description

Below are descriptions for three questions:

Question 1

Given $n$ integers, count the number of odd integers.

Question 2

Determine if $p$ is a prime number.

Question 3

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

Input and Output Format

Input Format

Question 1

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

Question 2

The input consists of one line containing an integer $p$.

Question 3

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

Output Format

Question 1

Output one line containing an integer as the answer.

Question 2

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

Question 3

Output one line containing an integer as the answer.

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

2

Sample Input #2

2

Sample Output #2

Yes

Sample Input #3

4
1 2 3 4

Sample Output #3

3

Notes

Sample Groups and Actual Input Notes

The three samples correspond to the sample inputs and outputs for the three questions.

If you use the 'Submit Answer' method directly, please name the three input data files as 1.in, 2.in, and 3.in, and zip them for submission.

If you use a data generator, your generator should read an integer $x$ from standard input, where $1 \leq x \leq 3$, indicating the problem number for the test point, and then output the corresponding input data.

Obviously, your program should not read any content mentioned in the 'Input Format', nor should it output any content mentioned in the 'Sample Output'. You should not use the samples to test your program; they are merely illustrative examples for the three questions.

Data Size Requirements

The data you provide must meet the following requirements:

1. Fully comply with the 'Input Format' specifications; no extra input is allowed, but trailing spaces at the end of lines and carriage returns at the end of the text are permissible.
2. All numbers in the data should be integers.
3. For Question 1, $1 \leq n \leq 1000, -2 \times 10^9 \le a_i \le 2 \times 10^9$.
4. For Question 2, $1 \le p \le 10^{12}$.
5. For Question 3, $2 \leq n \leq 100$, $1 \leq a_i \leq 2 \times 10^9$.

Target Code

You need to hack the following code:

Question 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;
}

Question 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;
}

Question 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 compilation options for the target code are -std=c++14 -fno-asm -O2. The compiler used is the g++ provided by Luogu. You can select the C++14 language in the 'Online IDE' to get the exact same compilation environment.

Scoring Explanation

This problem consists of three test points, corresponding to the three questions, with scores of $30$, $30$, and $40$ respectively.

Data Judgment

The data you provide must fully comply with the 'Data Size Requirements'; otherwise, you will receive an Unaccepted result.

Timeout Judgment

We check the program's runtime every few instructions. We guarantee that the number of instructions between two checks is a quantity unrelated to the input size, i.e., $O(1)$ instructions are checked between two checks. And the number of instructions between two checks is not too many, usually no more than $100$ C++ statements.

If the program's runtime exceeds $500 \text{ms}$, it is judged as running out of time, returning an accepted result.

Incorrect Result Judgment

If the program ends within the specified time and produces an output, we will compare this output with the completely correct output. If they differ, it is judged as a successful hack, returning an accepted result.

Undefined Behavior Judgment

We will check if the array index exceeds the array range before each explicit array element call. If it exceeds, it is judged as a successful hack, returning an accepted result.

This means that if you want to hack through undefined behavior, you can only hack explicit array element calls.

Sample Program

This is a sample program to help you understand what you need to output, but it cannot produce correct hack data. Submitting this program directly will not earn you points.

#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, ensure that opening the zip file directly shows only the three .in files. This means the file structure must be:

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

The three files should not be contained in an additional folder, i.e., the file structure should not be:

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

Explanation of Judging Information

If the hack is successful, the corresponding test point information will be accepted. If other information is returned, it indicates that there is an error with the program itself.

For example, if TLE is returned, it does not mean that the corresponding program was successfully hacked to timeout; it means that the data generator itself timed out, and the test point does not earn points.

Specifically, returning UKE results may indicate illegal data (extra content, missing content, or data out of range).

见题面 Input 部分

见题面 Output 部分