Codeforces

A. Spy Detected!

You are given an array $𝑎$ consisting of $𝑛$ $(𝑛≥3)$ positive integers. It is known that in this array, all the numbers except one are the same (for example, in the array $[4,11,4,4]$ all numbers except one are equal to $4$).

Print the index of the element that does not equal others. The numbers in the array are numbered from one.

Input

The first line contains a single integer $𝑡$ $(1≤𝑡≤100)$. Then 𝑡 test cases follow.

The first line of each test case contains a single integer $𝑛$ $(3≤𝑛≤100)$ — the length of the array $𝑎$.

The second line of each test case contains $𝑛$ integers $𝑎_1,𝑎_2,…,𝑎_𝑛$ $(1≤𝑎𝑖≤100)$.

It is guaranteed that all the numbers except one in the $𝑎$ array are the same.

Output

For each test case, output a single integer — the index of the element that is not equal to others.

풀이

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const char nl = '\n';

int A[101];

void solve() {
    int n; cin >> n;
    vector<int> v(n);
    memset(A, 0, sizeof(A));
    int k;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        A[v[i]]++;
    }
    for (int i = 1; i <= 100; i++) {
        if (A[i] > 1) k = i;
    }
    for (int i = 0; i < n; i++) {
        if (v[i] != k) {cout << i + 1 << nl; return; }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

B. Almost Rectangle

There is a square field of size $𝑛×𝑛$ in which two cells are marked. These cells can be in the same row or column.

You are to mark two more cells so that they are the corners of a rectangle with sides parallel to the coordinate axes.

For example, if $𝑛=4$ and a rectangular field looks like this (there are asterisks in the marked cells):

. . * .
. . . .
* . . .
. . . .

Then you can mark two more cells as follows

* . * .
. . . .
* . * .
. . . .

If there are several possible solutions, then print any of them.

Input

The first line contains a single integer $𝑡$ $(1≤𝑡≤400)$. Then $𝑡$ test cases follow.

The first row of each test case contains a single integer $𝑛$ $(2≤𝑛≤400)$ — the number of rows and columns in the table.

The following $𝑛$ lines each contain 𝑛 characters '.' or '*' denoting empty and marked cells, respectively.

It is guaranteed that the sums of $𝑛$ for all test cases do not exceed $400$.

It is guaranteed that there are exactly two asterisks on the field. They can be in the same row/column.

It is guaranteed that the solution exists.

Output

For each test case, output $𝑛$ rows of $𝑛$ characters — a field with four asterisks marked corresponding to the statements. If there multiple correct answers, print any of them.

풀이

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const char nl = '\n';

char A[401][401];

void solve() {
    int n; cin >> n;
    vector<int> y;
    vector<int> x;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> A[i][j];
            if (A[i][j] == '*') {
                y.push_back(i);
                x.push_back(j);
            }
        }
    }
    if (y[0] == y[1]) {
        if (y[0] == n - 1) {
            A[y[0] - 1][x[0]] = '*';
            A[y[0] - 1][x[1]] = '*';
        } else {
            A[y[0] + 1][x[0]] = '*';
            A[y[0] + 1][x[1]] = '*';
        }
    } else if (x[0] == x[1]) {
        if (x[0] == n - 1) {
            A[y[0]][x[0] - 1] = '*';
            A[y[1]][x[0] - 1] = '*';
        } else {
            A[y[0]][x[0] + 1] = '*';
            A[y[1]][x[0] + 1] = '*';
        }
    } else {
        A[y[0]][x[1]] = '*';
        A[y[1]][x[0]] = '*';
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << A[i][j];
        }
        cout << nl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

C. A-B Palindrome

You are given a string $𝑠$ consisting of the characters '0', '1', and '?'. You need to replace all the characters with '?' in the string 𝑠 by '0' or '1' so that the string becomes a palindrome and has exactly $𝑎$ characters '0' and exactly 𝑏 characters '1'. Note that each of the characters '?' is replaced independently from the others.

A string $𝑡$ of length $𝑛$ is called a palindrome if the equality $𝑡[𝑖]=𝑡[𝑛−𝑖+1]$ is true for all $𝑖$ $(1≤𝑖≤𝑛)$.

For example, if $𝑠=$"01?????0", $𝑎=4$ and $𝑏=4$, then you can replace the characters ‘?’ in the following ways:

• "01011010";
• "01100110".

For the given string $𝑠$ and the numbers $𝑎$ and $𝑏$, replace all the characters with '?' in the string $𝑠$ by '0' or '1' so that the string becomes a palindrome and has exactly $𝑎$ characters '0' and exactly $𝑏$ characters '1'.

Input

The first line contains a single integer $𝑡$ $(1≤𝑡≤10^4)$. Then $𝑡$ test cases follow.

The first line of each test case contains two integers $𝑎$ and $𝑏$ $(0≤𝑎,𝑏≤2⋅10^5, 𝑎+𝑏≥1)$.

The second line of each test case contains the string $𝑠$ of length $𝑎+𝑏$, consisting of the characters '0', '1', and '?'.

It is guaranteed that the sum of the string lengths of $𝑠$ over all test cases does not exceed $2⋅10^5$.

Output

For each test case, output:

• "-1", if you can’t replace all the characters '?' in the string $𝑠$ by '0' or '1' so that the string becomes a palindrome and that it contains exactly 𝑎 characters '0' and exactly $𝑏$ characters '1';
• the string that is obtained as a result of the replacement, otherwise.

If there are several suitable ways to replace characters, you can output any.

풀이

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const char nl = '\n';

char A[200001];

void solve() {
    int a, b; cin >> a >> b;
    int na = 0, nb = 0;
    for (int i = 0; i < a + b; i++) cin >> A[i];
    for (int i = 0; i < a + b; i++) {
        if (A[i] == '?' && A[a + b - 1 - i] != '?') A[i] = A[a + b - 1 - i];
    }
    for (int i = 0; i < a + b; i++) {
        if (A[i] == '0') na++;
        else if (A[i] == '1') nb++;
        if (A[i] != A[a + b - 1 - i]) {
            cout << "-1\n";
            return;
        }
    }
    if ((a + b) % 2 == 1) {
        if (A[(a + b) / 2] == '?') {
            if (a % 2 == 1) { A[(a + b) / 2] = '0'; na++; }
            else { A[(a + b) / 2] = '1'; nb++; }
        }

    }
    for (int i = 0; i < a + b; i++) {
        if (A[i] == '?') {
            if (na < a) {
                A[i] = '0';
                A[a + b - 1 - i] = '0';
                na += 2;
            } else {
                A[i] = '1';
                A[a + b - 1 - i] = '1';
                nb += 2;
            }
        }
    }
    if (na != a || nb != b) cout << "-1\n";
    else {
        for (int i = 0; i < a + b; i++) {
            cout << A[i] << " \n" [i == a + b - 1];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

D. Corrupted Array

You are given a number $𝑛$ and an array $𝑏_1,𝑏_2,…,𝑏_{𝑛+2}$, obtained according to the following algorithm:

• some array $𝑎_1,𝑎_2,…,𝑎_𝑛$ was guessed;
• array $𝑎$ was written to array $𝑏$, i.e. $𝑏𝑖=𝑎𝑖$ $(1≤𝑖≤𝑛)$;
• The $(𝑛+1)$-th element of the array $𝑏$ is the sum of the numbers in the array $𝑎$, i.e. $𝑏_{𝑛+1}=𝑎_1+𝑎_2+…+𝑎_𝑛$;
• The $(𝑛+2)$-th element of the array 𝑏 was written some number $𝑥$ $(1≤𝑥≤10^9)$, i.e. $𝑏_{𝑛+2}=𝑥$;
• The array $𝑏$ was shuffled.

For example, the array $𝑏=[2,3,7,12,2]$ it could be obtained in the following ways:

• $𝑎=[2,2,3]$ and $𝑥=12$;
• $𝑎=[3,2,7]$ and $𝑥=2$.

For the given array $𝑏$, find any array $𝑎$ that could have been guessed initially.

Input

The first line contains a single integer $𝑡$ $(1≤𝑡≤10^4)$. Then $𝑡$ test cases follow.

The first line of each test case contains a single integer $𝑛$ $(1≤𝑛≤2⋅10^5)$.

The second row of each test case contains $𝑛+2$ integers $𝑏_1,𝑏_2,…,𝑏_{𝑛+2}$ $(1≤𝑏_𝑖≤10^9)$.

It is guaranteed that the sum of $𝑛$ over all test cases does not exceed $2⋅10^5$.

Output

For each test case, output:

• "-1", if the array $𝑏$ could not be obtained from any array $𝑎$;
• $𝑛$ integers $𝑎_1,𝑎_2,…,𝑎_𝑛$, otherwise.

If there are several arrays of $𝑎$, you can output any.

풀이

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const char nl = '\n';

void solve() {
    int n; cin >> n;
    vector<ll> B(n + 2);
    for (int i = 0; i < n + 2; i++) cin >> B[i];
    sort(B.begin(), B.end());
    if (n == 1) {
        if( B[0] == B[1] || B[0] == B[2]) cout << B[0] << nl;
        else if (B[1] == B[2]) cout << B[1] << nl;
        else cout << "-1" << nl;
        return;
    }
    ll sum = 0;
    for (int i = 0; i < n + 1; i++) sum += B[i];
    int idx = -1;
    for (int i = 0; i < n + 1; i++) {
        if (sum - B[i] == B[n] || sum - B[i] == B[n + 1]) { idx = i; break; }
    }
    if (idx == -1) { cout << "-1" << nl; return; }
    for (int i = 0; i < n + 1; i++) {
        if (i == idx) continue;
        cout << B[i] << " ";
    }
    cout << nl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

https://codeforces.com/contest/1512