Codeforces Round #516 (Div. 2, by Moscow Team Olympiad)
A. Make a triangle!
Description:
Masha has three sticks of length a, b and c centimeters respectively. In one minute Masha can pick one arbitrary stick and increase its length by one centimeter. She is not allowed to break sticks.
What is the minimum number of minutes she needs to spend increasing the stick’s length in order to be able to assemble a triangle of positive area. Sticks should be used as triangle’s sides (one stick for one side) and their endpoints should be located at triangle’s vertices.
Input:
The only line contains tree integers a, b and c ( 1≤a,b,c≤100) — the lengths of sticks Masha possesses.
Output:
Print a single integer — the minimum number of minutes that Masha needs to spend in order to be able to make the triangle of positive area from her sticks.
Sample Input:
3 4 5
Sample Output:
0
Sample Input:
2 5 3
Sample Output:
1
Sample Input:
100 10 10
Sample Output:
81
题目链接
求最小截取三段棍的多长可以使得三段棍拼成三角形。
显然截取最长棍直至小于另两棍长度之和。
AC代码:
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char *argv[]) {
vector<int> Length(3);
for (int i = 0; i < 3; ++i) {
scanf("%d", &Length[i]);
}
sort(Length.begin(), Length.end());
printf("%d\n", max(0, Length[2] - (Length[0] + Length[1]) + 1));
return 0;
}
B. Equations of Mathematical Magic
Description:
Colossal! — exclaimed Hawk-nose. — A programmer! That’s exactly what we are looking for.Arkadi and Boris Strugatsky. Monday starts on SaturdayReading the book “Equations of Mathematical Magic” Roman Oira-Oira and Cristobal Junta found an interesting equation: a−(a⊕x)−x=0 for some given a, where ⊕ stands for a bitwise exclusive or (XOR) of two integers (this operation is denoted as ^ or xor in many modern programming languages). Oira-Oira quickly found some x, which is the solution of the equation, but Cristobal Junta decided that Oira-Oira’s result is not interesting enough, so he asked his colleague how many non-negative solutions of this equation exist. This task turned out to be too difficult for Oira-Oira, so he asks you to help.
Input:
sal! — exclaimed Hawk-nose. — A programmer! That’s exactly what we are looking for.Arkadi and Boris Strugatsky. Monday starts on Saturday
Output:
and Boris Strugatsky. Monday starts on Saturday
Sample Input:
3
0
2
1073741823
Sample Output:
1
2
1073741824
题目链接
给出a，求使得 a−(a⊕x)−x=0成立的x个数。
a−(a⊕x)−x=0移项可得 (a⊕x)=a−x。
对于这个公式若a为1则x可以取0或1，若a为0则x只能取0，所以对于a二进制中每个1，x在此位上都有两种取法，统计a在二进制下1的个数做2的幂即为结果。
AC代码:
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char *argv[]) {
int T;
scanf("%d", &T);
for (int Case = 1, N; Case <= T; ++Case) {
scanf("%d", &N);
printf("%d\n", (1 << __builtin_popcount(N)));
}
return 0;
}
C. Oh Those Palindromes
Description:
A non-empty string is called palindrome, if it reads the same from the left to the right and from the right to the left. For example, “abcba”, “a”, and “abba” are palindromes, while “abab” and “xy” are not.
A string is called a substring of another string, if it can be obtained from that string by dropping some (possibly zero) number of characters from the beginning and from the end of it. For example, “abc”, “ab”, and “c” are substrings of the string “abc”, while “ac” and “d” are not.
Let’s define a palindromic count of the string as the number of its substrings that are palindromes. For example, the palindromic count of the string “aaa” is 6 because all its substrings are palindromes, and the palindromic count of the string “abc” is 3 because only its substrings of length 1 are palindromes.
You are given a string s. You can arbitrarily rearrange its characters. You goal is to obtain a string with the maximum possible value of palindromic count.
Input:
The first line contains an integer n ( 1≤n≤100000) — the length of string s.
The second line contains string s that consists of exactly n lowercase characters of Latin alphabet.
Output:
Print string t, which consists of the same set of characters (and each characters appears exactly the same number of times) as string s. Moreover, t should have the maximum possible value of palindromic count among all such strings strings.
If there are multiple such strings, print any of them.
Sample Input:
5
oolol
Sample Output:
ololo
Sample Input:
16
gagadbcgghhchbdf
Sample Output:
abccbaghghghgdfd
题目链接
重新排序字符串使其拥有最多回文子串。
显然相同字母排列在一起回文子串最多。
AC代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int N;
char Str[maxn];
int main(int argc, char *argv[]) {
scanf("%d", &N);
scanf("%s", Str);
sort(Str, Str + N);
printf("%s\n", Str);
return 0;
}
D. Labyrinth
Description:
You are playing some computer game. One of its levels puts you in a maze consisting of n lines, each of which contains m cells. Each cell either is free or is occupied by an obstacle. The starting cell is in the row r and column c. In one step you can move one square up, left, down or right, if the target cell is not occupied by an obstacle. You can’t move beyond the boundaries of the labyrinth.
Unfortunately, your keyboard is about to break, so you can move left no more than x times and move right no more than y times. There are no restrictions on the number of moves up and down since the keys used to move up and down are in perfect condition.
Now you would like to determine for each cell whether there exists a sequence of moves that will put you from the starting cell to this particular one. How many cells of the board have this property?
Input:
The first line contains two integers n, m (1 ≤ n, m ≤ 2000) — the number of rows and the number columns in the labyrinth respectively.
The second line contains two integers r, c (1 ≤ r ≤ n, 1 ≤ c ≤ m) — index of the row and index of the column that define the starting cell.
The third line contains two integers x, y (0 ≤ x, y ≤ 109) — the maximum allowed number of movements to the left and to the right respectively.
The next n lines describe the labyrinth. Each of them has length of m and consists only of symbols ‘.’ and ‘’. The j-th character of the i-th line corresponds to the cell of labyrinth at row i and column j. Symbol ‘.’ denotes the free cell, while symbol '’ denotes the cell with an obstacle.
It is guaranteed, that the starting cell contains no obstacles.
Output:
Print exactly one integer — the number of cells in the labyrinth, which are reachable from starting cell, including the starting cell itself.
Sample Input:
4 5
3 2
1 2
…
.***.
…**
*…
Sample Output:
10
Sample Input:
4 4
2 2
0 1
…
…*.
…
…
Sample Output:
7
题目链接
在一个迷宫中从起点开始出发，只能向左、向右走有限步，求可达点数量。
宽度优先搜索每个可达点计数即可。
某点可能之前被不是最优解搜索并标记，所有可能再次搜索到此点被跳过，注意根据搜索此点使状态进行有效筛选。
AC代码:
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 2e3 + 5;
struct Search {
int X, Y;
int LeftCnt, RightCnt;
};
int N, M;
int R, C;
int StartX, StartY;
int Ans;
char Maze[maxn][maxn];
bool Vis[maxn][maxn];
int LeftCnt[maxn][maxn];
int RightCnt[maxn][maxn];
int DX[4] = {1, -1, 0, 0}, DY[4] = {0, 0, -1, 1};
void Bfs() {
memset(Vis, false, sizeof(Vis));
memset(LeftCnt, INF, sizeof(LeftCnt));
memset(RightCnt, INF, sizeof(RightCnt));
queue<Search> Que;
Que.push(Search {StartX, StartY, 0, 0});
Vis[StartX][StartY] = true;
Ans++;
while (!Que.empty()) {
Search Cur = Que.front(); Que.pop();
for (int i = 0; i < 4; ++i) {
int NX = Cur.X + DX[i], NY = Cur.Y + DY[i];
if (NX >= 1 && NX <= N && NY >= 1 && NY <= M && Maze[NX][NY] == '.') {
Search Temp;
if (i == 2) {
if (Cur.LeftCnt + 1 > R) {
continue;
}
Temp = Search {NX, NY, Cur.LeftCnt + 1, Cur.RightCnt};
}
else if (i == 3) {
if (Cur.RightCnt + 1 > C) {
continue;
}
Temp = Search {NX, NY, Cur.LeftCnt, Cur.RightCnt + 1};
}
else {
Temp = Search {NX, NY, Cur.LeftCnt, Cur.RightCnt};
}
if (Vis[NX][NY]) {
if (Temp.LeftCnt >= LeftCnt[NX][NY] && Temp.RightCnt >= RightCnt[NX][NY]) {
continue;
}
else {
if (Temp.LeftCnt < LeftCnt[NX][NY]) {
LeftCnt[NX][NY] = Temp.LeftCnt;
}
if (Temp.RightCnt < RightCnt[NX][NY]) {
RightCnt[NX][NY] = Temp.RightCnt;
}
}
}
Que.push(Temp);
if (!Vis[NX][NY]) {
Ans++;
}
Vis[NX][NY] = true;
}
}
}
}
int main(int argc, char *argv[]) {
scanf("%d%d", &N, &M);
scanf("%d%d", &StartX, &StartY);
scanf("%d%d", &R, &C);
for (int i = 1; i <= N; ++i) {
scanf("%s", Maze[i] + 1);
}
Ans = 0;
Bfs();
printf("%d\n", Ans);
return 0;
}
