Imgcity

Appearance

1694A - Creep ​

題目 ​

Codeforces: 1694A: Creep

Define the score of some binary string 𝑇 as the absolute difference between the number of zeroes and ones in it. (for example, 𝑇= 010001 contains 4 zeroes and 2 ones, so the score of 𝑇 is |4−2|=2).

Define the creepiness of some binary string 𝑆 as the maximum score among all of its prefixes (for example, the creepiness of 𝑆 = 01001 is equal to 2 because the score of the prefix 𝑆[1…4] is 2 and the rest of the prefixes have a score of 2 or less).

Given two integers 𝑎 and 𝑏, construct a binary string consisting of 𝑎 zeroes and 𝑏 ones with the minimum possible creepiness.

Input ​

The first line contains a single integer 𝑡 (1≤𝑡≤1000)  — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers 𝑎 and 𝑏 (1≤𝑎,𝑏≤100)  — the numbers of zeroes and ones correspondingly.

說明 ​

這題可以直接把數學式列出來。

  • 最小值會至少(直接看整個字串)是 |a−b|，所以就設法構造出這樣的情況。
  • 可以直接構造 min(a, b)*"01" + |a - b|*(a > b?'0':'1')

Code ​

cpp
#include <iostream>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for (int lt = 0; lt < T; ++lt) {
        int zeros, ones;
        cin >> zeros >> ones;
        for (int lx = 0; lx < min(zeros, ones); ++lx) {
            cout << "01";
        }
        if (zeros < ones) {
            cout << string(ones - zeros, '1');
        } else { // if (zeros > ones) {
            cout << string(zeros - ones, '0');
        }
        cout << "\n";
    }
    return 0;
}

Changelog

Just observe 👀