# Codeforces Round #453 (Div. 1 & Div. 2) 官方题解 # A. Masha and Bears

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A family consisting of father bear, mother bear and son bear owns three cars. Father bear can climb into the largest car and he likes it. Also, mother bear can climb into the middle car and she likes it. Moreover, son bear can climb into the smallest car and he likes it. It’s known that the largest car is strictly larger than the middle car, and the middle car is strictly larger than the smallest car.

Masha came to test these cars. She could climb into all cars, but she liked only the smallest car.

It’s known that a character with size a can climb into some car with size b if and only if a ≤ b, he or she likes it if and only if he can climb into this car and 2a ≥ b.

You are given sizes of bears and Masha. Find out some possible integer non-negative sizes of cars.

### Input

You are given four integers V1V2V3Vm(1 ≤ Vi ≤ 100) — sizes of father bear, mother bear, son bear and Masha, respectively. It’s guaranteed that V1 > V2 > V3.

### Output

Output three integers — sizes of father bear’s car, mother bear’s car and son bear’s car, respectively.

If there are multiple possible solutions, print any.

If there is no solution, print “-1” (without quotes).

### Note

In first test case all conditions for cars’ sizes are satisfied.

In second test case there is no answer, because Masha should be able to climb into smallest car (so size of smallest car in not less than 21), but son bear should like it, so maximum possible size of it is 20.

# B. Tic-Tac-Toe

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Two bears are playing tic-tac-toe via mail. It’s boring for them to play usual tic-tac-toe game, so they are a playing modified version of this game. Here are its rules.

The game is played on the following field. Players are making moves by turns. At first move a player can put his chip in any cell of any small field. For following moves, there are some restrictions: if during last move the opposite player put his chip to cell with coordinates (xl, yl) in some small field, the next move should be done in one of the cells of the small field with coordinates (xl, yl). For example, if in the first move a player puts his chip to lower left cell of central field, then the second player on his next move should put his chip into some cell of lower left field (pay attention to the first test case). If there are no free cells in the required field, the player can put his chip to any empty cell on any field.

You are given current state of the game and coordinates of cell in which the last move was done. You should find all cells in which the current player can put his chip.

A hare works as a postman in the forest, he likes to foul bears. Sometimes he changes the game field a bit, so the current state of the game could be unreachable. However, after his changes the cell where the last move was done is not empty. You don’t need to find if the state is unreachable or not, just output possible next moves according to the rules.

### Input

First 11 lines contains descriptions of table with 9 rows and 9 columns which are divided into 9 small fields by spaces and empty lines. Each small field is described by 9 characters without spaces and empty lines. character “x” (ASCII-code 120) means that the cell is occupied with chip of the first player, character “o” (ASCII-code 111) denotes a field occupied with chip of the second player, character “.” (ASCII-code 46) describes empty cell.

The line after the table contains two integers x and y (1 ≤ x, y ≤ 9). They describe coordinates of the cell in table where the last move was done. Rows in the table are numbered from up to down and columns are numbered from left to right.

It’s guaranteed that cell where the last move was done is filled with “x” or “o“. Also, it’s guaranteed that there is at least one empty cell. It’s not guaranteed that current state of game is reachable.

### Output

Output the field in same format with characters “!” (ASCII-code 33) on positions where the current player can put his chip. All other cells should not be modified.

### Note

In the first test case the first player made a move to lower left cell of central field, so the second player can put a chip only to cells of lower left field.

In the second test case the last move was done to upper left cell of lower central field, however all cells in upper left field are occupied, so the second player can put his chip to any empty cell.

In the third test case the last move was done to central cell of central field, so current player can put his chip to any cell of central field, which is already occupied, so he can move anywhere. Pay attention that this state of the game is unreachable.

# C. Shockers

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Valentin participates in a show called “Shockers”. The rules are quite easy: jury selects one letter which Valentin doesn’t know. He should make a small speech, but every time he pronounces a word that contains the selected letter, he receives an electric shock. He can make guesses which letter is selected, but for each incorrect guess he receives an electric shock too. The show ends when Valentin guesses the selected letter correctly.

Valentin can’t keep in mind everything, so he could guess the selected letter much later than it can be uniquely determined and get excessive electric shocks. Excessive electric shocks are those which Valentin got after the moment the selected letter can be uniquely determined. You should find out the number of excessive electric shocks.

### Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of actions Valentin did.

The next n lines contain descriptions of his actions, each line contains description of one action. Each action can be of one of three types:

1. Valentin pronounced some word and didn’t get an electric shock. This action is described by the string “. w” (without quotes), in which “.” is a dot (ASCII-code 46), and w is the word that Valentin said.
2. Valentin pronounced some word and got an electric shock. This action is described by the string “! w” (without quotes), in which “!” is an exclamation mark (ASCII-code 33), and wis the word that Valentin said.
3. Valentin made a guess about the selected letter. This action is described by the string “? s” (without quotes), in which “?” is a question mark (ASCII-code 63), and s is the guess — a lowercase English letter.

All words consist only of lowercase English letters. The total length of all words does not exceed 105.

It is guaranteed that last action is a guess about the selected letter. Also, it is guaranteed that Valentin didn’t make correct guesses about the selected letter before the last action. Moreover, it’s guaranteed that if Valentin got an electric shock after pronouncing some word, then it contains the selected letter; and also if Valentin didn’t get an electric shock after pronouncing some word, then it does not contain the selected letter.

### Output

Output a single integer — the number of electric shocks that Valentin could have avoided if he had told the selected letter just after it became uniquely determined.

### Note

In the first test case after the first action it becomes clear that the selected letter is one of the following: a, b, c. After the second action we can note that the selected letter is not a. Valentin tells word “b” and doesn’t get a shock. After that it is clear that the selected letter is c, but Valentin pronounces the word cd and gets an excessive electric shock.

In the second test case after the first two electric shocks we understand that the selected letter is e or o. Valentin tries some words consisting of these letters and after the second word it’s clear that the selected letter is e, but Valentin makes 3 more actions before he makes a correct hypothesis.

In the third example the selected letter can be uniquely determined only when Valentin guesses it, so he didn’t get excessive electric shocks.

# D. Seating of Students

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Students went into a class to write a test and sat in some way. The teacher thought: “Probably they sat in this order to copy works of each other. I need to rearrange them in such a way that students that were neighbors are not neighbors in a new seating.”

The class can be represented as a matrix with n rows and m columns with a student in each cell. Two students are neighbors if cells in which they sit have a common side.

Let’s enumerate students from 1 to n·m in order of rows. So a student who initially sits in the cell in row i and column j has a number (i - 1)·m + j. You have to find a matrix with n rows and m columns in which all numbers from 1 to n·m appear exactly once and adjacent numbers in the original matrix are not adjacent in it, or determine that there is no such matrix.

### Input

The only line contains two integers n and m (1 ≤ n, m ≤ 105n·m ≤ 105) — the number of rows and the number of columns in the required matrix.

### Output

If there is no such matrix, output “NO” (without quotes).

Otherwise in the first line output “YES” (without quotes), and in the next n lines output mintegers which form the required matrix.

### Note

In the first test case the matrix initially looks like this:

It’s easy to see that there are no two students that are adjacent in both matrices.

In the second test case there are only two possible seatings and in both of them students with numbers 1 and 2 are neighbors.

# E. Party

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Arseny likes to organize parties and invite people to it. However, not only friends come to his parties, but friends of his friends, friends of friends of his friends and so on. That’s why some of Arseny’s guests can be unknown to him. He decided to fix this issue using the following procedure.

At each step he selects one of his guests A, who pairwise introduces all of his friends to each other. After this action any two friends of A become friends. This process is run until all pairs of guests are friends.

Arseny doesn’t want to spend much time doing it, so he wants to finish this process using the minimum number of steps. Help Arseny to do it.

### Input

The first line contains two integers n and m (1 ≤ n ≤ 22 ) — the number of guests at the party (including Arseny) and the number of pairs of people which are friends.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ nu ≠ v), which means that people with numbers u and v are friends initially. It’s guaranteed that each pair of friends is described not more than once and the graph of friendship is connected.

### Output

In the first line print the minimum number of steps required to make all pairs of guests friends.

In the second line print the ids of guests, who are selected at each step.

If there are multiple solutions, you can output any of them.

### Note

In the first test case there is no guest who is friend of all other guests, so at least two steps are required to perform the task. After second guest pairwise introduces all his friends, only pairs of guests (4, 1) and (4, 2) are not friends. Guest 3 or 5 can introduce them.

In the second test case guest number 1 is a friend of all guests, so he can pairwise introduce all guests in one step.

# F. Power Tower

time limit per test

4.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Priests of the Quetzalcoatl cult want to build a tower to represent a power of their god. Tower is usually made of power-charged rocks. It is built with the help of rare magic by levitating the current top of tower and adding rocks at its bottom. If top, which is built from k - 1 rocks, possesses power p and we want to add the rock charged with power wk then value of power of a new tower will be {wk}p.

Rocks are added from the last to the first. That is for sequence w1, …, wm value of power will be After tower is built, its power may be extremely large. But still priests want to get some information about it, namely they want to know a number called cumulative power which is the true value of power taken modulo m. Priests have n rocks numbered from 1 to n. They ask you to calculate which value of cumulative power will the tower possess if they will build it from rocks numbered l, l + 1, …, r.

### Input

First line of input contains two integers n (1 ≤ n ≤ 105) and m (1 ≤ m ≤ 109).

Second line of input contains n integers wk (1 ≤ wk ≤ 109) which is the power of rocks that priests have.

Third line of input contains single integer q (1 ≤ q ≤ 105) which is amount of queries from priests to you.

kth of next q lines contains two integers lk and rk (1 ≤ lk ≤ rk ≤ n).

### Output

Output q integers. k-th of them must be the amount of cumulative power the tower will have if is built from rocks lk, lk + 1, …, rk.

### Note

327 = 7625597484987

# G. Reverses

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Hurricane came to Berland and to suburbs Stringsvill. You are going to it to check if it’s all right with you favorite string. Hurrinace broke it a bit by reversing some of its non-intersecting substrings. You have a photo of this string before hurricane and you want to restore it to original state using reversing minimum possible number of its substrings and find out which substrings you should reverse.

You are given a string s — original state of your string and string t — state of the string after hurricane. You should select k non-intersecting substrings of t in such a way that after reverse of these substrings string will be equal s and k is minimum possible.

### Input

First line of input contains string s and second line contains string t. Both strings have same length and consist of lowercase English letters. 1 ≤ |s| = |t| ≤ 5·105

### Output

In first line print k — minimum number of substrings you should reverse. Next output k lines. Each line should contain two integers liri meaning that you should reverse substring from symbol number li to symbol ri (strings are 1-indexed). These substrings shouldn’t intersect. If there are multiple answers print any. If it’s impossible to restore string output -1.

### Example

##### output

2017-12-23 18:02:19 Announcement Problem C. Shockers
*****
There was a mistake in description of first sample test case. Instead of “Valentin makes a hypothesis about the letter b and gets an electric shock.” you there should be “Valentin tells word b and doesn’t get a shock”.
2017-12-23 17:18:12 Announcement Problem C. Shockers
*****
To make it clear: jury chooses only one hidden letter.

### 907A – Masha and Bears

Sizes of cars should satisfy the following constraints:

1. in i-th car, Masha and corresponding bear are able to get into, so size of the car should not be less than max(Vi, Vm);
2. each bear likes its car, so size of i-th car is no more than Vi;
3. Masha doesn’t like first two cars, then their sizes are more than Vm;
4. Masha likes last car, so it’s size is not more than V3;
5. Sizes of cars are strictly ordered. It means that size of father’s car is strictly more than size of mother’s one, and size of mother’s car is strictly more than son’s car.

Sizes of bears don’t exceed 100; then, sizes of cars does not exceed 200, and there are only 2003 possible variants of sizes of cars. In given constraints, one can just go through all possible triples of sizes and check if each of them satisfies the constrains above or not.

### 907B – Tic-Tac-Toe

Let us describe each cell of the field by four numbers (xb, yb, xs, ys)0 ≤ xb, yb, xs, ys ≤ 2), where (xb, yb) are coordinates of small field containing the cell, and (xs, ys) are coordinates of the cell in it’s small field. It can be seen that for cell with “usual” coordinates (x, y)1 ≤ x, y ≤ 9 and our new (xb, yb, xs, ys), there are following equalities which give us a key to go between coordinate systems:

• xb = ⌊((x - 1) / 3)⌋yb = ⌊((y - 1) / 3)⌋;
• xs = (x - 1) mod 3yb = (y - 1) mod 3;
• x = 3 * xb + xs + 1y = 3 * yb + ys + 1.

In terms of new coordinates, if last move was in cell (xb, yb, xs, ys), then next move should be in arbitrary free cell with coordinates (xs, ys, x‘, y‘) for some if it’s possible; otherwise, next move can be done in arbitrary free cell. To solve the problem, one can go through all such pairs (x‘, y‘) and write “!” in each empty cell (xs, ys, x‘, y‘); if there are not such empty cells, write “!” in all empty cells of the field.

### 906A – Shockers

From last action, selected letter can be found; let it be c (without loss of generality). For each of other 25 letters, answers on some actions are contradicting with assumption that this letter was selected; moreover, for each letter d not equal to c, we can find the earlest such action with number Ad (for each action, we can easily check if assumption “d is selected” is contradicting with the action or not on linear time). Then, the answer is a number of electric shocks after action with number which is maximal among all such Ad-s.

### 906B – Seating of Students

The problem has many solutions, including random ones. Consider one of deterministic solutions. Without loss of generality, assume that n ≤ m.

There are a couple of corner cases:

1. n = 1, m = 1. In this case, good seating exists.
2. n = 1, m = 2. In this case, seating does not exist (obviously).
3. n = 1, m = 3. In any seating, one of neighbours of student 2 will be one of his former neighbours, so correct seating does not exist.
4. n = 2, m = 2. Only student 4 can be a neighbour of student 1, but there should be 2 neighbours for student 1; then, correct seating does not exist.
5. n = 2, m = 3. Both students 5 and 2 have 3 neighbours in the initial seating; then, in new seating, these students should be in non-neighbouring corner cells. Moreover, these corner cells can not be in one row because in this case it’s impossible to find a student for cell between 2 and 5. So, without loss of generality, let 5 be in lower left corner, and 2 — in upper right corner. Then, only students 1 and 3 can seat on lower middle cell; but if sduent 1 seats in the cell, then student 4 is impossible to seat at any of the remaining cells, so do student 6 in case of student 3 seating at the cell. So, correct seating does not exist in this case too.
6. n = 1, m = 4. In this case, one of correct seatings is 2 4 1 3.
7. n = 1;5 ≤ m. In this case, let students with odd numbers in increasing order will be in first half of the row, and others in increasing order – in second half. For example, for m = 7 the seating will be 1 3 5 7 2 4 6.
8. n = m = 3. One of possible correct seatings is:6 1 8

7 5 3

2 9 4;

9. If 2 ≤ n;4 ≤ m, then shift each even row cyclically on two symbols in the right, and then shift each even column cyclically on one symbol upwards. If students are vertical neighbours in the initial seating, then in new seating, they will be in different columns on the distance 2 (possibly through the edge of the table); but if students are horizontal neighbours in the initial seating, then in new seating they will be in neighbouring rows and neighbouring columns (possibly thorugh the edges again). So, for case 2 ≤ n, 4 ≤ m, we build a correct seating.

### 906C – Party

Let’s formulate and prove several facts.

1. If we change an call order, the result doesn’t change. Let’s consider two vertices which are called consecutively. If they are not connected by edge, then regardless of the order, we get that at the end, neighbours of each vertex form a clique.

If they are connected, then independently on the order, we get clique from 2 vertices and all neighbours of them.

2. If graph is a tree, it’s sufficient to take as an answer all its vertices except leaves. Indeed, if we consider any 2 tree vertices, we get that all vertices on the way between them are in the answer. Each vertex reduces on 1 the distance between those 2, it means that the distance between them is 1.

3. Let’s select from source graph spanning tree, that has the largest number of leaves. One can say that we can use all vertices except leaves as an answer.

Obviously from point 2, that after all our operations with such set graph will become complete. Let’s show that it is minimal number of vertices.

Let we selected some set of vertices, that is the answer. Then subgraph of given graph, built on the selected set of vertices, should be connected (otherwise between connected component can’t appear the edge and graph can’t be complete. Also, each of vertices, that isn’t in an answer should have at least one of neighbours selected (otherwise it is impossible to add new edge to it). Now let’s select a spanning tree in selected set (it’s possible because our set is connected) and add non-selected vertices into the tree as leafs. Then we see that our selected can be represented as spanning tree in the initial graph, in which all selected vertices are all non-leaf vertices and possibly, some leafs; but leafs can be obviously removed from the selected set by proved above. So, one of optimal answers can be described as set of non-leaf vertices of spanning tree with minimal possible number of non-leaves and, as a consequence, with maximal possible number of leaves, QED.

4. Implementation. It is necessary to implement an algorithm that should work for 2n·n or faster or with worse asymptotic but with non-asymptotical optimization. One of possible solutions is following. Let contain any subset of vertices as a n-bit mask; for example, mask of a subset containing vertices {v1, v2, …, vk} will be equal to 2v1 + 2v2 + … + 2vk. Then, for subset with mask m, vertex v is in set iff m & 2v is not equal to 0; here & is a bitwise AND.

Let for each vertex vneighbours[v] be a mask of subset of vertices containing vertex vand it’s neighbours. Array neighbours[v] can be calculated easily. Then, let bool isConnected[m] be 1 for some mask m iff subset coded by m is connected. Array isConnected can be calculated in O(2n * n) by the following algorithm:

• for all vertices (let vertices be enumerated in 0-indexation), isCalculated[2v] is assigned to 1; for all other masks, isCalculated should be equal to 0;
• then, go through all masks in increasing order by a simple cycle; let m be current mask in the cycle;
• if isConnected[m] = 0, then go to the next iteration of cycle;
• otherwise, let v1, v2, …, vk be vertices of subset coded by m. Then, mask m‘:  = maskNeighbours[m]:  = neighbours[v1]|neighbours[v2]|… |neighbours[vk]for | as bitwise OR is a mask coding a subset of vertices containing vertices of mask mand their neighbours. Then, for each vertex w in subset of mask m we assign isConnected[m|2w] to be 1.

The described algorithm works in O(2n * n); it can be proved by induction that at the end, isConnected[m] = 1 for mask m iff m is a code of connected subset of vertices.

But how to find an answer? Notice that mask m = 2v1 + 2v2 + … + 2vk is a code of good (for our purposes) subset iff isConnected[m] = 1 and maskNeighbours[m] = 2n - 1 = 20 + 21 + … + 2n - 1. For each mask m, we can check if it’s good in O(n) time having an array isConnected calculated; the answer is a good mask with minimal possible number of elements in the corresponding set.

### 906D – Power Tower

Let’s learn to calculate . Assume that we want to find where n and m non necessary co-prime, and x is some big number which we can calculate only modulo some value.

We can solve this problem for co-prime n and m via Euler’s theorem. Let’s reduce general case to that one. Note that . Indeed if n = d·m + r, |r| < m, then an = d·am + ar, |ar| < |am|. Let p1, …, pt to be common prime divisors of n and ma = p1k1… ptkt to be such number that it divisible by such divisors to the power they occur in m, and k to be least number such that . Then we have a chain Here n and m / a are co-prime so we can calculate power value module . Moreover, , thus case x < k can be considered in .

This is already enough to solve the problem, but continuing one can prove that for it holds Where φ(m) is Euler totient function of m. Finally, to solve the problem one shoud note that so it will take only steps before m turns into 1.

### 906E – Reverses

After inverses we have transform . Consider operator for strings of equal lengths. Under such operator string will turn into where Xk is string which has all characters doubled and Yk is arbitrary palindrome of even length.

Let’s move through letters from left to right and keep minimum number on which we can split current prefix. Last letter will either be in some palindrome or is doubled. For doubled letters we consider ansi = min(ansi, ansi - 2). As for palindromes of even length, one can fit standard algorithm of splitting string into the minimum number of palindromes in such way that it will consider only splittings on even palindromes. For example, one can consider only such spits that every palindrome in the split end up in even index.