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
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.
說明
這題可以直接把數學式列出來。
- 最小值會至少(直接看整個字串)是
，所以就設法構造出這樣的情況。 - 可以直接構造 min(a, b)*"01" + |a - b|*(a > b?'0':'1')
Code
#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;
}