# 尔尔序的神奇计数问题

Time Limit: 8000 MS Memory Limit: 2097152 KB

## Description

现在有$4$个集合，分别为$A,B,C,D$，且每一个集合的大小都是$n$。尔尔序想求解一个问题，现在他把$A,B,C$的交集的大小、$A,B,D$的交集的大小，$A,C,D$的交集的大小，$B,C,D$的交集的大小之和记为$X$，同时把$A,B$的交集的大小、$A,C$的交集的大小、$A,D$的交集的大小、$B,C$的交集的大小、$B,D$的交集的大小之和记为$Y$，求解$|X-Y|$的值。

# 尔尔序才是最强的

Time Limit: 1000 MS Memory Limit: 2097152 KB

## Description

和往常一样，尔尔序和他的小伙伴兮兮芜开始了每天的王者荣耀之旅。在某局游戏中，尔尔序有了一个新奇的想法。现在尔尔序想独自以最快的速度击杀游戏里的主宰，向兮兮芜证明他才是最强的。
现在主宰有$x$滴血，每秒钟会恢复$y$滴血，如果主宰回了血之后超过了初始的血量$x$，那么主宰的血量仍然为初始血量$x$。
尔尔序有$n$个技能(不要执着于王者只有3个技能QAQ)。对于编号为$i$的技能，如果主宰当前有超过（严格大于）$p_i\%$的初始血量时，则该技能无法使用。使用后，该技能会给主宰挂上一个每秒掉$d_i$滴血的BUFF。
尔尔序想知道他能否一个人击杀主宰，获得兮兮芜的崇拜？
请注意，每个技能尔尔序最多只能使用一次。且每秒钟尔尔序最多只能使用一个技能。主宰每秒钟会先受到以前挂上的BUFF的伤害，再恢复$y$滴血。如果回血之后，主宰的血量仍然小于等于0，主宰即被尔尔序击杀。该秒挂上的BUFF在这秒不会对主宰造成伤害。

## Codeforces 754C Vladik and chat 字符串处理+DP

http://codeforces.com/problemset/problem/754/C

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Recently Vladik discovered a new entertainment — coding bots for social networks. He would like to use machine learning in his bots so now he want to prepare some learning data for them.

At first, he need to download t chats. Vladik coded a script which should have downloaded the chats, however, something went wrong. In particular, some of the messages have no information of their sender. It is known that if a person sends several messages in a row, they all are merged into a single message. It means that there could not be two or more messages in a row with the same sender. Moreover, a sender never mention himself in his messages.

Vladik wants to recover senders of all the messages so that each two neighboring messages will have different senders and no sender will mention himself in his messages.

He has no idea of how to do this, and asks you for help. Help Vladik to recover senders in each of the chats!

### Input

The first line contains single integer t (1 ≤ t ≤ 10) — the number of chats. The t chats follow. Each chat is given in the following format.

The first line of each chat description contains single integer n (1 ≤ n ≤ 100) — the number of users in the chat.

The next line contains n space-separated distinct usernames. Each username consists of lowercase and uppercase English letters and digits. The usernames can't start with a digit. Two usernames are different even if they differ only with letters' case. The length of username is positive and doesn't exceed 10 characters.

The next line contains single integer m (1 ≤ m ≤ 100) — the number of messages in the chat. The next m line contain the messages in the following formats, one per line:

• <username>:<text> — the format of a message with known sender. The username should appear in the list of usernames of the chat.
• <?>:<text> — the format of a message with unknown sender.

The text of a message can consist of lowercase and uppercase English letter, digits, characters '.' (dot), ',' (comma), '!' (exclamation mark), '?' (question mark) and ' ' (space). The text doesn't contain trailing spaces. The length of the text is positive and doesn't exceed 100 characters.

We say that a text mention a user if his username appears in the text as a word. In other words, the username appears in a such a position that the two characters before and after its appearance either do not exist or are not English letters or digits. For example, the text "Vasya, masha13 and Kate!" can mention users "Vasya", "masha13", "and" and "Kate", but not "masha".

It is guaranteed that in each chat no known sender mention himself in his messages and there are no two neighboring messages with the same known sender.

### Output

Print the information about the t chats in the following format:

If it is not possible to recover senders, print single line "Impossible" for this chat. Otherwise print m messages in the following format:

If there are multiple answers, print any of them.

Input

Output

Input

Output

Input

Output

## Codeforces 708B 找规律+模拟

### D. Recover the String

time limit per test

1 second

memory limit per test

256 megabytes

For each string s consisting of characters '0' and '1' one can define four integers a00, a01, a10 and a11, where axy is the number ofsubsequences of length 2 of the string s equal to the sequence {x, y}.

In these problem you are given four integers a00, a01, a10, a11 and have to find any non-empty string s that matches them, or determine that there is no such string. One can prove that if at least one answer exists, there exists an answer of length no more than1 000 000.

### Input

The only line of the input contains four non-negative integers a00, a01, a10 and a11. Each of them doesn't exceed 109.

### Output

If there exists a non-empty string that matches four integers from the input, print it in the only line of the output. Otherwise, print "Impossible". The length of your answer must not exceed 1 000 000.

# C. Letters Cyclic Shift

time limit per test

1 second

memory limit per test

256 megabytes

You are given a non-empty string s consisting of lowercase English letters. You have to pick exactly one non-empty substring of s and shift all its letters 'z' 'y' 'x' 'b' 'a' 'z'. In other words, each character is replaced with the previous character of English alphabet and 'a' is replaced with 'z'.

What is the lexicographically minimum string that can be obtained from s by performing this shift exactly once?

### Input

The only line of the input contains the string s (1 ≤ |s| ≤ 100 000) consisting of lowercase English letters.

### Output

Print the lexicographically minimum string that can be obtained from s by shifting letters of exactly one non-empty substring.

### Note

String s is lexicographically smaller than some other string t of the same length if there exists some 1 ≤ i ≤ |s|, such thats1 = t1, s2 = t2, ..., si - 1 = ti - 1, and si < ti.

## Codeforces 581D Three Logos 枚举 模拟

http://codeforces.com/contest/581/problem/D

D. Three Logos
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Three companies decided to order a billboard with pictures of their logos. A billboard is a big square board. A logo of each company is a rectangle of a non-zero area.

Advertisers will put up the ad only if it is possible to place all three logos on the billboard so that they do not overlap and the billboard has no empty space left. When you put a logo on the billboard, you should rotate it so that the sides were parallel to the sides of the billboard.

Your task is to determine if it is possible to put the logos of all the three companies on some square billboard without breaking any of the described rules.

Input

The first line of the input contains six positive integers x1, y1, x2, y2, x3, y3 (1 ≤ x1, y1, x2, y2, x3, y3 ≤ 100), where xi and yi determine the length and width of the logo of the i-th company respectively.

Output

If it is impossible to place all the three logos on a square shield, print a single integer "-1" (without the quotes).

If it is possible, print in the first line the length of a side of square n, where you can place all the three logos. Each of the next n lines should contain n uppercase English letters "A", "B" or "C". The sets of the same letters should form solid rectangles, provided that:

• the sizes of the rectangle composed from letters "A" should be equal to the sizes of the logo of the first company,
• the sizes of the rectangle composed from letters "B" should be equal to the sizes of the logo of the second company,
• the sizes of the rectangle composed from letters "C" should be equal to the sizes of the logo of the third company,

Note that the logos of the companies can be rotated for printing on the billboard. The billboard mustn't have any empty space. If a square billboard can be filled with the logos in multiple ways, you are allowed to print any of them.

See the samples to better understand the statement.

Sample test(s)
Input

Output

Input

Output

## Codeforces 581C Developing Skills 模拟 贪心

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Petya loves computer games. Finally a game that he's been waiting for so long came out!

The main character of this game has n different skills, each of which is characterized by an integer ai from 0 to 100. The higher the number ai is, the higher is the i-th skill of the character. The total rating of the character is calculated as the sum of the values of for all i from 1 to n. The expression x denotes the result of rounding the number x down to the nearest integer.

At the beginning of the game Petya got k improvement units as a bonus that he can use to increase the skills of his character and his total rating. One improvement unit can increase any skill of Petya's character by exactly one. For example, if a4 = 46, after using one imporvement unit to this skill, it becomes equal to 47. A hero's skill cannot rise higher more than 100. Thus, it is permissible that some of the units will remain unused.

Your task is to determine the optimal way of using the improvement units so as to maximize the overall rating of the character. It is not necessary to use all the improvement units.

Input

The first line of the input contains two positive integers n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 107) — the number of skills of the character and the number of units of improvements at Petya's disposal.

The second line of the input contains a sequence of n integers ai (0 ≤ ai ≤ 100), where ai characterizes the level of the i-th skill of the character.

Output

The first line of the output should contain a single non-negative integer — the maximum total rating of the character that Petya can get using k or less improvement units.

Sample test(s)
Input

Output

Input

Output

Input

Output

Note

In the first test case the optimal strategy is as follows. Petya has to improve the first skill to 10 by spending 3 improvement units, and the second skill to 10, by spending one improvement unit. Thus, Petya spends all his improvement units and the total rating of the character becomes equal to lfloor frac{100}{10} rfloor +  lfloor frac{100}{10} rfloor = 10 + 10 =  20.

In the second test the optimal strategy for Petya is to improve the first skill to 20 (by spending 3 improvement units) and to improve the third skill to 20 (in this case by spending 1 improvement units). Thus, Petya is left with 4 improvement units and he will be able to increase the second skill to 19 (which does not change the overall rating, so Petya does not necessarily have to do it). Therefore, the highest possible total rating in this example is .

In the third test case the optimal strategy for Petya is to increase the first skill to 100 by spending 1 improvement unit. Thereafter, both skills of the character will be equal to 100, so Petya will not be able to spend the remaining improvement unit. So the answer is equal to .