Codeforces Round #677 (Div. 3)
A. Boring Apartments
There is a building consisting of 10 000 apartments numbered from 1 to 10 000, inclusive.
Call an apartment boring, if its number consists of the same digit. Examples of boring apartments are 11,2,777,9999 and so on.
Our character is a troublemaker, and he calls the intercoms of all boring apartments, till someone answers the call, in the following order:
First he calls all apartments consisting of digit 1, in increasing order (1,11,111,1111). Next he calls all apartments consisting of digit 2, in increasing order (2,22,222,2222) And so on. The resident of the boring apartment x answers the call, and our character stops calling anyone further.
Our character wants to know how many digits he pressed in total and your task is to help him to count the total number of keypresses.
For example, if the resident of boring apartment 22 answered, then our character called apartments with numbers 1,11,111,1111,2,22 and the total number of digits he pressed is 1+2+3+4+1+2=13.
You have to answer t independent test cases.
Input The first line of the input contains one integer t (1≤t≤36) — the number of test cases.
The only line of the test case contains one integer x (1≤x≤9999) — the apartment number of the resident who answered the call. It is guaranteed that x consists of the same digit.
Output For each test case, print the answer: how many digits our character pressed in total.
中文大意:输入房间号的位数之和,如输入22时输出13
(1 11 111 1111 22 = 1 + 2 + 3 + 4 + 1 + 2 = 13)
解析:模拟就完事,但是不知道为什么直接的过不了,(感觉CF的编译器有问题)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string str;
cin >> str;
int num = int(str[0] - '1') * 10 + str.size() * (str.size() + 1) / 2;
cout << num << endl;
}
return 0;
}
B. Yet Another Bookshelf
There is a bookshelf which can fit n books. The i-th position of bookshelf is ai=1 if there is a book on this position and ai=0 otherwise. It is guaranteed that there is at least one book on the bookshelf.
In one move, you can choose some contiguous segment [l;r] consisting of books (i.e. for each i from l to r the condition ai=1 holds) and:
Shift it to the right by 1: move the book at index i to i+1 for all l≤i≤r. This move can be done only if r+1≤n and there is no book at the position r+1. Shift it to the left by 1: move the book at index i to i−1 for all l≤i≤r. This move can be done only if l−1≥1 and there is no book at the position l−1. Your task is to find the minimum number of moves required to collect all the books on the shelf as a contiguous (consecutive) segment (i.e. the segment without any gaps).
For example, for a=[0,0,1,0,1] there is a gap between books (a4=0 when a3=1 and a5=1), for a=[1,1,0] there are no gaps between books and for a=[0,0,0] there are also no gaps between books.
You have to answer t independent test cases.
Input The first line of the input contains one integer t (1≤t≤200) — the number of test cases. Then t test cases follow.
The first line of the test case contains one integer n (1≤n≤50) — the number of places on a bookshelf. The second line of the test case contains n integers a1,a2,…,an (0≤ai≤1), where ai is 1 if there is a book at this position and 0 otherwise. It is guaranteed that there is at least one book on the bookshelf.
Output For each test case, print one integer: the minimum number of moves required to collect all the books on the shelf as a contiguous (consecutive) segment (i.e. the segment without gaps).
中文大意:输出移动的最小次数
解析:输出最左边的1和最右边的1之间的零的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;
int arr[55];
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int left = 0, right = 0, flag = 0;
for (int i = 0; i < n; i++) {
cin >> arr[i];
if (arr[i] == 1) {
if (flag == 0) { // 最左边的1
left = i;
flag = 1;
}
right = i; // 最右边的1
}
}
int res = 0;
for (int i = left; i <= right; i++) {
if (arr[i] == 0) {
res++;
}
}
cout << res << endl;
}
return 0;
}
C. Dominant Piranha
There are n piranhas with sizes a1,a2,…,an in the aquarium. Piranhas are numbered from left to right in order they live in the aquarium.
Scientists of the Berland State University want to find if there is dominant piranha in the aquarium. The piranha is called dominant if it can eat all the other piranhas in the aquarium (except itself, of course). Other piranhas will do nothing while the dominant piranha will eat them.
Because the aquarium is pretty narrow and long, the piranha can eat only one of the adjacent piranhas during one move. Piranha can do as many moves as it needs (or as it can). More precisely:
The piranha i can eat the piranha i−1 if the piranha i−1 exists and ai−1<ai. The piranha i can eat the piranha i+1 if the piranha i+1 exists and ai+1<ai. When the piranha i eats some piranha, its size increases by one (ai becomes ai+1).
Your task is to find any dominant piranha in the aquarium or determine if there are no such piranhas.
Note that you have to find any (exactly one) dominant piranha, you don’t have to find all of them.
For example, if a=[5,3,4,4,5], then the third piranha can be dominant. Consider the sequence of its moves:
The piranha eats the second piranha and a becomes [5,5–,4,5] (the underlined piranha is our candidate). The piranha eats the third piranha and a becomes [5,6–,5]. The piranha eats the first piranha and a becomes [7–,5]. The piranha eats the second piranha and a becomes [8–]. You have to answer t independent test cases.
Input The first line of the input contains one integer t (1≤t≤2⋅104) — the number of test cases. Then t test cases follow.
The first line of the test case contains one integer n (2≤n≤3⋅105) — the number of piranhas in the aquarium. The second line of the test case contains n integers a1,a2,…,an (1≤ai≤109), where ai is the size of the i-th piranha.
It is guaranteed that the sum of n does not exceed 3⋅105 (∑n≤3⋅105).
Output For each test case, print the answer: -1 if there are no dominant piranhas in the aquarium or index of any dominant piranha otherwise. If there are several answers, you can print any.
中文大意:有没有鱼可能成为那条可以吃掉所有其他鱼的鱼
解析:所有鱼的体积不一样时,必然会出现这样的鱼,输出左右两边存在比它体积小的鱼的鱼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
int n;
int arr[300005];
int main() {
int t;
cin >> t;
while (t--) {
int max_cnt = 0, max = 0, res;
cin >> n;
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
if (arr[i] >= max) {
if (arr[i] > max) {
max = arr[i];
max_cnt = 1;
res = i + 1;
} else {
max_cnt++;
}
}
}
if (max_cnt == n) { // 所有鱼体积一样
cout << -1 << endl;
} else {
if (arr[n - 1] == max && arr[n - 2] != max) { // 最右边的特殊处理
res = n - 1 + 1;
}
for (int i = 0; i < n - 1; i++) { // 遍历,比较右边是否有比它小的鱼
if (arr[i] == max && arr[i + 1] != max) {
res = i + 1;
break;
}
}
cout << res << endl;
}
}
return 0;
}
D. Districts Connection
There are n districts in the town, the i-th district belongs to the ai-th bandit gang. Initially, no districts are connected to each other.
You are the mayor of the city and want to build n−1 two-way roads to connect all districts (two districts can be connected directly or through other connected districts).
If two districts belonging to the same gang are connected directly with a road, this gang will revolt.
You don’t want this so your task is to build n−1 two-way roads in such a way that all districts are reachable from each other (possibly, using intermediate districts) and each pair of directly connected districts belong to different gangs, or determine that it is impossible to build n−1 roads to satisfy all the conditions.
You have to answer t independent test cases.
Input The first line of the input contains one integer t (1≤t≤500) — the number of test cases. Then t test cases follow.
The first line of the test case contains one integer n (2≤n≤5000) — the number of districts. The second line of the test case contains n integers a1,a2,…,an (1≤ai≤109), where ai is the gang the i-th district belongs to.
It is guaranteed that the sum of n does not exceed 5000 (∑n≤5000).
Output For each test case, print:
NO on the only line if it is impossible to connect all districts satisfying the conditions from the problem statement. YES on the first line and n−1 roads on the next n−1 lines. Each road should be presented as a pair of integers xi and yi (1≤xi,yi≤n;xi≠yi), where xi and yi are two districts the i-th road connects. For each road i, the condition a[xi]≠a[yi] should be satisfied. Also, all districts should be reachable from each other (possibly, using intermediate districts).
中文大意:将所有地区相连,帮派一样的地区不能直接相连
解析:跟0地区帮派不一样的地区跟0连,其他跟0地区帮派一样的随便连一个其他帮派地区
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream> // 跟0地区帮派不一样的地区跟0连
#include <cstring> // 其他跟0地区帮派一样的随便连一个其他帮派地区
using namespace std;
int arr[5005];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n, flag_other = 0; // 第一个跟0地区帮派不一样的地区
cin >> n;
memset(arr, 0, sizeof(arr));
cin >> arr[0];
for (int i = 1; i < n; i++) {
cin >> arr[i];
if (flag_other == 0 && arr[i] != arr[0]) {
flag_other = i;
}
}
if (flag_other == 0) {
cout << "NO" << endl;
} else {
cout << "YES" << endl;
for (int i = 1; i < n; i++) {
if (arr[i] != arr[0]) {
cout << 1 << " " << i + 1 << endl;
} else {
cout << flag_other + 1 << " " << i + 1 << endl;
}
}
}
}
return 0;
}
E. Two Round Dances
One day, n people (n is an even number) met on a plaza and made two round dances, each round dance consists of exactly n2 people. Your task is to find the number of ways n people can make two round dances if each round dance consists of exactly n2 people. Each person should belong to exactly one of these two round dances.
Round dance is a dance circle consisting of 1 or more people. Two round dances are indistinguishable (equal) if one can be transformed to another by choosing the first participant. For example, round dances [1,3,4,2], [4,2,1,3] and [2,1,3,4] are indistinguishable.
For example, if n=2 then the number of ways is 1: one round dance consists of the first person and the second one of the second person.
For example, if n=4 then the number of ways is 3. Possible options:
one round dance — [1,2], another — [3,4]; one round dance — [2,4], another — [3,1]; one round dance — [4,1], another — [3,2]. Your task is to find the number of ways n people can make two round dances if each round dance consists of exactly n2 people.
Input The input contains one integer n (2≤n≤20), n is an even number.
Output Print one integer — the number of ways to make two round dances. It is guaranteed that the answer fits in the 64-bit integer data type.
中文大意:有n个人,将平分为两组,分组围成一个圆圈跳舞,不区分两个圆圈及每个圆圈的顺序.
解析:数学问题,排列组合.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long int res = 1;
for (int i = 1; i <= n - 1; i++) {
res *= i;
}
for (int i = 1; i <= n / 2; i++) {
res /= i;
}
for (int i = 1; i <= n / 2 - 1; i++) {
res *= i;
}
cout << res << endl;
return 0;
}
F. Zero Remainder Sum
You are given a matrix a of size n×m consisting of integers.
You can choose no more than ⌊m2⌋ elements in each row. Your task is to choose these elements in such a way that their sum is divisible by k and this sum is the maximum.
In other words, you can choose no more than a half (rounded down) of elements in each row, you have to find the maximum sum of these elements divisible by k.
Note that you can choose zero elements (and the sum of such set is 0).
Input The first line of the input contains three integers n, m and k (1≤n,m,k≤70) — the number of rows in the matrix, the number of columns in the matrix and the value of k. The next n lines contain m elements each, where the j-th element of the i-th row is ai,j (1≤ai,j≤70).
Output Print one integer — the maximum sum divisible by k you can obtain.
中文大意:给你一个n*m的矩阵,每行最多选m/2(向下取整)个元素相加,求能整除k的最大值.
解析:四重dp,给的是个n×m矩阵,状态有(m/2)×k种.
1
2
3
//状态转移方程
dp[nx][ny][cnt][rem] = max(dp[nx][ny][cnt][rem], dp[x][y][cnt][rem]); // 不选
dp[nx][ny][cnt + 1][nrem] = max(dp[nx][ny][cnt + 1][nrem], dp[x][y][cnt][rem] + mat[x][y]); // 选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstring>
#include <iostream>
using namespace std;
int mat[72][72];
int dp[72][72][36][72]; // n, m, 选了多少个数, 余数
int main() {
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> mat[i][j];
}
}
memset(dp, -128, sizeof(dp));
dp[0][0][0][0] = 0;
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
for (int cnt = 0; cnt <= m / 2; cnt++) {
for (int rem = 0; rem < k; rem++) {
int nx = (y == m - 1) ? x + 1 : x; // nx为下一位的行
int ny = (y == m - 1) ? 0 : y + 1; // ny为下一位的列
if (x != nx) { // 不选
dp[nx][ny][0][rem] = max(dp[nx][ny][0][rem], dp[x][y][cnt][rem]);
} else {
dp[nx][ny][cnt][rem] = max(dp[nx][ny][cnt][rem], dp[x][y][cnt][rem]);
}
if (cnt + 1 <= m / 2) { // 选
int nrem = (rem + mat[x][y]) % k;
if (x != nx) {
dp[nx][ny][0][nrem] = max(dp[nx][ny][0][nrem], dp[x][y][cnt][rem] + mat[x][y]);
} else {
dp[nx][ny][cnt + 1][nrem] = max(dp[nx][ny][cnt + 1][nrem], dp[x][y][cnt][rem] + mat[x][y]);
}
}
}
}
}
}
cout << max(0, dp[n][0][0][0]);
return 0;
}
