CODE FESTIVAL 2016 Qualification Round A

Again, think carefully and hope you can stick to it.

A - CODEFESTIVAL 2016

The question is to give a string of length 12 and output the first 4 characters + spaces + the last four characters.

B - Naka Liang しうさぎ / Friendly Rabbits

The meaning of the question is to give N rabbits, each rabbit has its own favorite rabbit $A_i$, and ask how many pairs of rabbits there are that like each other.

Direct simulation calculation.

C - Next Letter

The meaning of the question is to give a string. Each character in the string can be moved backward cyclically, but it must be moved backward K times in total. Find the string with the smallest lexicographic order after the change.

Be greedy on each character and do the rest on the last character.

D - MATCH / Grid and Integers

The meaning of the question is that a grid of R*C is given, and then there are N grids ($r_i,c_i$) that already have the value $a_i$. Now you are asked to judge whether each grid is greater than or equal to zero, so that in any 2*2 grid, the sum of the two diagonals is equal.

This is another question that requires you to transform the question.

First, for any 2*2 square, it must be satisfied
$$
b_{i,j}+b_{i+1,j+1}=b_{i+1,j}+b_{i,j+1}
$$
Move the equation into the form of difference, and you will find that for a fixed row i, the difference must be equal. For a fixed column j, the differences are also equal. Then thinking at this time, the above conditions can be transformed into whether there are two sequence $(x_1,x_2,…,x_R)$ and $(y_1,y_2,…,y_C)$, making $x_{rk}+y_{ck}=a_k$.

Therefore, the graph can be constructed according to the conditions given in the question. The weight of each edge is $a_k$. When a ring is formed, it is judged whether they are equal.

Finally, to determine whether they are all greater than or equal to 0, we first assume that the initial value

E - LRU パズル / LRU Puzzle

The meaning of the question is that there are N arrays increasing from 1 to M, and a series of operations are given. Each operation will select an array from N arrays and bring $a_i$ in this array to the front. Now the question is to ask whether the results obtained after Q operations are equal.

Assume that the operation is on (1, 2,…,M), then the result obtained after performing Q operations is looking from back to front. When this number appears for the first time, this number is placed at the end of the result queue. If it has appeared before, it is ignored. Then insert the numbers that do not appear in the result queue to the end.

Then the problem is now equivalent to dividing the array a of this operation into N substrings, and requiring that the operations of these N substrings on 1..M have equal results. Ask if it’s possible.

Then consider the case of N=2 first. Be greedy and take it. If you encounter something that has never appeared before, give it to the first one. If you encounter the first one that appears, give it to the second one. If they all appear, ignore them. Finally, check whether the two arrays are equal.

When N is greater than 2, the idea is the same, similar to pushing a box. . .

First, remember that there are N arrays with a length of 0, then get a number to determine the current state, push it down, and finally see if there is anything left in the box. . .