• 2018-10-17
• 18
• 0

# 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 \leq a, b, c \leq 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.

3 4 5

0

2 5 3

1

100 10 10

81

# 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 \oplus x) – x = 0 for some given a, where \oplus 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

3
0
2
1073741823

## Sample Output:

1
2
1073741824

### 题目链接

a – (a \oplus x) – x = 0移项可得(a \oplus x) = a – x

# 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 \le n \le 100\,000) — 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.

5
oolol

ololo

16

abccbaghghghgdfd

# 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.

4 5
3 2
1 2
…..
.***.
…**
*….

10

4 4
2 2
0 1
….
..*.
….
….

7