#include<bits/stdc++.h>
using namespace std;
int main() {
puts("Good code is its own best documentation.");
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int a, b;
int main() {
cin >> a >> b, a += b;
cout << a - 16 << endl << a - 3 << endl << a - 1 << endl << a;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n, m, k;
string x;
int main() {
cin >> n >> x >> m >> k;
if(k == n) cout << "mei you mai " << x << " de";
else if(k == m) cout << "kan dao le mai " << x << " de";
else cout << "wang le zhao mai " << x << " de";
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n, a, b, c;
int main() {
cin >> n;
while(n--) {
cin >> a >> b >> c;
if(c == a * b) puts("Lv Yan");
else if (c == a + b) puts("Tu Dou");
else puts("zhe du shi sha ya!");
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n, k, x;
int main() {
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i) {
cin >> a[i];
}
cin >> k;
while(k--) {
int cnt = 0, wa = 0;
for(int i = 0; i < n; ++i) {
cin >> x;
if(!x) continue;
++cnt;
if(x != a[i]) ++wa;
}
if(cnt && !wa) puts("Da Jiang!!!");
else puts("Ai Ya");
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
string s, s1, s2, s3;
int n, a, b;
int main() {
cin >> s >> n;
while(n--) {
cin >> a >> b >> s1 >> s2;
s3 = s.substr(a - 1, b - a + 1);
s.erase(s.begin() + a - 1, s.begin() + b);
int len = s1.length();
s1 += s2;
int pos = s.find(s1);
if(pos != s.npos) s.insert(pos + len, s3);
else s.insert(s.length(), s3);
}
cout << s;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n0, n1, n, flag0, flag1, res = INT_MAX;
vector<int> N0, N1;
int main() {
cin >> n0 >> n1 >> n;
for(int i = 2; i <= min(n0, n1); ++i) {
if(!(n0 % i)) N0.emplace_back(i);
if(!(n1 % i)) N1.emplace_back(i);
}
for(int i = 0; i < N0.size(); ++i) {
for(int j = 0; j < N1.size(); ++j) {
if(n0 / N0[i] + n1 / N1[j] == n && fabs(N0[i] - N1[j]) < res) {
res = fabs(N0[i] - N1[j]), flag0 = n0 / N0[i], flag1 = n1 / N1[j];
}
}
}
if(res == INT_MAX) puts("No Solution");
else cout << flag0 << " " << flag1;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
long long n, na, nb, sa, sb;
long long sum(long long x) {
long long cnt = 0;
while(x) {
cnt += (x % 10), x /= 10;
}
return cnt;
}
int main() {
cin >> n;
while(n--) {
cin >> na >> nb, sa = sum(na), sb = sum(nb);
if(!(na % sb) && !(nb % sa) || na % sb && nb % sa) cout << (na < nb ? "B\n" : "A\n");
else if(!(na % sb)) cout << "A\n";
else cout << "B\n";
}
return 0;
}
L2-045 堆宝塔
堆宝塔游戏是让小朋友根据抓到的彩虹圈的直径大小，按照从大到小的顺序堆起宝塔。但彩虹圈不一定是按照直径的大小顺序抓到的。聪明宝宝采取的策略如下：
首先准备两根柱子，一根 A 柱串宝塔，一根 B 柱用于临时叠放。
把第 1 块彩虹圈作为第 1 座宝塔的基座，在 A 柱放好。
将抓到的下一块彩虹圈 C 跟当前 A 柱宝塔最上面的彩虹圈比一下，如果比最上面的小，就直接放上去；否则把 C 跟 B 柱最上面的彩虹圈比一下：
如果 B 柱是空的、或者 C 大，就在 B 柱上放好；
否则把 A 柱上串好的宝塔取下来作为一件成品；然后把 B 柱上所有比 C 大的彩虹圈逐一取下放到 A 柱上，最后把 C 也放到 A 柱上。
重复此步骤，直到所有的彩虹圈都被抓完。最后 A 柱上剩下的宝塔作为一件成品，B 柱上剩下的彩虹圈被逐一取下，堆成另一座宝塔。问：宝宝一共堆出了几个宝塔？最高的宝塔有多少层？
输入格式：
输入第一行给出一个正整数 N（≤103），为彩虹圈的个数。第二行按照宝宝抓取的顺序给出 N 个不超过 100 的正整数，对应每个彩虹圈的直径。
输出格式：
在一行中输出宝宝堆出的宝塔个数，和最高的宝塔的层数。数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
11
10 8 9 5 12 11 4 3 1 9 15
输出样例：
4 5
样例解释：
宝宝堆成的宝塔顺次为：
10、8、5
12、11、4、3、1
9
15、9
#include<bits/stdc++.h>
using namespace std;
int n, c, cnt, maxx;
stack<int> a, b;
int main() {
cin >> n >> c;
a.emplace(c);
for(int i = 1; i < n; ++i) {
cin >> c;
if(c < a.top()) a.emplace(c);
else if(b.empty() || c > b.top()) b.emplace(c);
else {
++cnt, maxx = max(maxx, (int)a.size());
while(!a.empty()) a.pop();
while(!b.empty() && b.top() > c) a.emplace(b.top()), b.pop();
a.emplace(c);
}
}
++cnt, maxx = max(maxx, (int)a.size());
if(!b.empty()) ++cnt, maxx = max(maxx, (int)b.size());
cout << cnt << " " << maxx;
return 0;
}
L2-046 天梯赛的赛场安排
天梯赛使用 OMS 监考系统，需要将参赛队员安排到系统中的虚拟赛场里，并为每个赛场分配一位监考老师。每位监考老师需要联系自己赛场内队员对应的教练们，以便发放比赛账号。为了尽可能减少教练和监考的沟通负担，我们要求赛场的安排满足以下条件：
每位监考老师负责的赛场里，队员人数不得超过赛场规定容量 C；
每位教练需要联系的监考人数尽可能少 —— 这里假设每所参赛学校只有一位负责联系的教练，且每个赛场的监考老师都不相同。
为此我们设计了多轮次排座算法，按照尚未安排赛场的队员人数从大到小的顺序，每一轮对当前未安排的人数最多的学校进行处理。记当前待处理的学校未安排人数为 n：
如果 n≥C，则新开一个赛场，将 C 位队员安排进去。剩下的人继续按人数规模排队，等待下一轮处理；
如果 n<C，则寻找剩余空位数大于等于 n 的编号最小的赛场，将队员安排进去；
如果 n<C，且找不到任何非空的、剩余空位数大于等于 n 的赛场了，则新开一个赛场，将队员安排进去。
由于近年来天梯赛的参赛人数快速增长，2023年超过了 480 所学校 1.6 万人，所以我们必须写个程序来处理赛场安排问题。
输入格式：
输入第一行给出两个正整数 N 和 C，分别为参赛学校数量和每个赛场的规定容量，其中 0<N≤5000，10≤C≤50。随后 N 行，每行给出一个学校的缩写（为长度不超过 6 的非空小写英文字母串）和该校参赛人数（不超过 500 的正整数），其间以空格分隔。题目保证每所学校只有一条记录。
输出格式：
按照输入的顺序，对每一所参赛高校，在一行中输出学校缩写和该校需要联系的监考人数，其间以 1 空格分隔。
最后在一行中输出系统中应该开设多少个赛场。
输入样例：
10 30
zju 30
hdu 93
pku 39
hbu 42
sjtu 21
abdu 10
xjtu 36
nnu 15
hnu 168
hsnu 20
输出样例：
zju 1
hdu 4
pku 2
hbu 2
sjtu 1
abdu 1
xjtu 2
nnu 1
hnu 6
hsnu 1
16
#include<bits/stdc++.h>
using namespace std;
int n, c, res, cnt, a[5005], x;
string s;
priority_queue<int> Q;
int main() {
cin >> n >> c;
while(n--) {
cin >> s >> x;
cout << s << " " << ceil(1.0 * x / c) << endl;
res += (x / c);
if(x % c) Q.emplace(x % c);
}
while(!Q.empty()) {
x = Q.top(), Q.pop();
bool flag = true;
for(int i = 0; i < cnt; ++i) {
if(a[i] + x <= c) {
a[i] += x, flag = false;
break;
}
}
if(flag) a[cnt++] = x;
}
cout << cnt + res;
return 0;
}
L2-047 锦标赛
有 2k 名选手将要参加一场锦标赛。锦标赛共有 k 轮，其中第 i 轮的比赛共有 2k−i 场，每场比赛恰有两名选手参加并从中产生一名胜者。每场比赛的安排如下：
对于第 1 轮的第 j 场比赛，由第 (2j−1) 名选手对抗第 2j 名选手。
对于第 i 轮的第 j 场比赛（i>1），由第 (i−1) 轮第 (2j−1) 场比赛的胜者对抗第 (i−1) 轮第 2j 场比赛的胜者。
第 k 轮唯一一场比赛的胜者就是整个锦标赛的最终胜者。
举个例子，假如共有 8 名选手参加锦标赛，则比赛的安排如下：
第 1 轮共 4 场比赛：选手 1 vs 选手 2，选手 3 vs 选手 4，选手 5 vs 选手 6，选手 7 vs 选手 8。
第 2 轮共 2 场比赛：第 1 轮第 1 场的胜者 vs 第 1 轮第 2 场的胜者，第 1 轮第 3 场的胜者 vs 第 1 轮第 4 场的胜者。
第 3 轮共 1 场比赛：第 2 轮第 1 场的胜者 vs 第 2 轮第 2 场的胜者。
已知每一名选手都有一个能力值，其中第 i 名选手的能力值为 ai。在一场比赛中，若两名选手的能力值不同，则能力值较大的选手一定会打败能力值较小的选手；若两名选手的能力值相同，则两名选手都有可能成为胜者。
令 li,j 表示第 i 轮第 j 场比赛 败者 的能力值，令 w 表示整个锦标赛最终胜者的能力值。给定所有满足 1≤i≤k 且 1≤j≤2k−i 的 li,j 以及 w，请还原出 a1,a2,⋯,an。
输入格式:
第一行输入一个整数 k（1≤k≤18）表示锦标赛的轮数。
对于接下来 k 行，第 i 行输入 2k−i 个整数 li,1,li,2,⋯,li,2k−i（1≤li,j≤109），其中 li,j 表示第 i 轮第 j 场比赛 败者 的能力值。
接下来一行输入一个整数 w（1≤w≤109）表示锦标赛最终胜者的能力值。
输出格式:
输出一行 n 个由单个空格分隔的整数 a1,a2,⋯,an，其中 ai 表示第 i 名选手的能力值。如果有多种合法答案，请输出任意一种。如果无法还原出能够满足输入数据的答案，输出一行 No Solution。
请勿在行末输出多余空格。
输入样例1:
3
4 5 8 5
7 6
8
9
输出样例1:
7 4 8 5 9 8 6 5
输入样例2:
2
5 8
3
9
输出样例2:
No Solution
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7;
int k, x;
int res[N], id[N][20], tr[N][20];
bool flag = true;
int main() {
cin >> k;
for(int j = 1; j <= k; ++j) {
for(int i = 1; i <= (1 << (k - j)); ++i) {
cin >> x;
if(j == 1) res[i * 2] = x, id[i][1] = i * 2 - 1, tr[i][1] = x;
else if(tr[i * 2 - 1][j - 1] > x && tr[i * 2][j - 1] > x) flag = false;
else {
if(tr[i * 2 - 1][j - 1] <= x) res[id[i * 2 - 1][j - 1]] = x, id[i][j] = id[i * 2][j - 1];
else res[id[i * 2][j - 1]] = x, id[i][j] = id[i * 2 - 1][j - 1];
tr[i][j] = max({x, tr[i * 2 - 1][j - 1], tr[i * 2][j - 1]});
}
}
}
cin >> x;
if(x < tr[1][k]) flag = false;
else res[id[1][k]] = x;
if(!flag) puts("No Solution");
else for(int i = 1; i <= (1 << k); ++i) cout << res[i] << " \n"[i == (1 << k)];
return 0;
}
L2-048 寻宝图
给定一幅地图，其中有水域，有陆地。被水域完全环绕的陆地是岛屿。有些岛屿上埋藏有宝藏，这些有宝藏的点也被标记出来了。本题就请你统计一下，给定的地图上一共有多少岛屿，其中有多少是有宝藏的岛屿。
输入格式：
输入第一行给出 2 个正整数 N 和 M（1<N×M≤105），是地图的尺寸，表示地图由 N 行 M 列格子构成。随后 N 行，每行给出 M 位个位数，其中 0 表示水域，1 表示陆地，2-9 表示宝藏。
注意：两个格子共享一条边时，才是“相邻”的。宝藏都埋在陆地上。默认地图外围全是水域。
输出格式：
在一行中输出 2 个整数，分别是岛屿的总数量和有宝藏的岛屿的数量。
输入样例：
10 11
01000000151
11000000111
00110000811
00110100010
00000000000
00000111000
00114111000
00110010000
00019000010
00120000001
输出样例：
7 2
#include<bits/stdc++.h>
using namespace std;
int n, m, cnt1, cnt2;
bool flag;
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, 1, -1, 0};
int main() {
cin >> n >> m, getchar();
vector<vector<int>> a(n, vector<int>(m));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
a[i][j] = (getchar() - '0');
}
getchar();
}
function<void(int, int)> dfs = [&](int x, int y) {
if(a[x][y] != 1) flag = true;
a[x][y] = 0;
for(int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && a[nx][ny]) dfs(nx, ny);
}
};
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(a[i][j]) {
++cnt1;
flag = false;
dfs(i, j);
if(flag) ++cnt2;
}
}
}
cout << cnt1 << " " << cnt2;
return 0;
}