PowerOJ 尔尔序的神奇计数问题 暴力or容斥


尔尔序的神奇计数问题

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|$的值。

Input

第一行输入一个整数$n$ ($1 \leq n \leq 5 \times 10^4$)代表这$4$个集合的大小。 第二行输入$n$整数$A_i$ ($1 \leq A_i \leq 10^{18}$),代表集合$A$中的数。 第三行输入$n$整数$B_i$ ($1 \leq B_i \leq 10^{18}$),代表集合$B$中的数。 第四行输入$n$整数$C_i$ ($1 \leq C_i \leq 10^{18}$),代表集合$C$中的数。 第五行输入$n$整数$D_i$ ($1 \leq D_i \leq 10^{18}$),代表集合$D$中的数。 保证在同一集合内没有重复的数。

Output

输出$|X-Y|$的值。

Sample Input

Sample Output

题解

数据量比较小,对每个集合排序后,用set_intersection求交集即可。使用容斥原理可以发现,最后的答案其实是|size(A+B+C+D) + size(CD) + size(ABCD) – 4*n|

C++代码

Java代码

 

 

 

 

PowerOJ 2611 尔尔序才是最强的 贪心+优先队列


尔尔序才是最强的

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在这秒不会对主宰造成伤害。

Input

第1行输入三个整数 $n, x, y$,分别代表尔尔序的技能数,主宰的初始血量,主宰每秒恢复的血量。 第2行到第$n+1$行输入两个整数,为编号为$i$的技能的$p_i$和$d_i$值,意义和描述中相同。 $ 1 \leq n,x,y \leq 1000$ $ 0 \leq p_i,d_i \leq 1000$

Output

如果尔尔序不能一个人击杀主宰,获得兮兮芜的崇拜,输出一行“What a pity eex!”(没有引号)。 否则先输出一行“Luckly dog eex!”(没有引号)。接下来一行先输出一个整数,为主宰被击杀的最早时刻,然后再输出一个整数,为需要使用技能的数量$num$。接下来$num$行输出两个整数,为每个技能使用的时刻和编号。从0时刻开始计算时间。

Sample Input

Sample Output

题解

由于主宰的血量越少,尔尔序可选用的技能就越多。所以直接选择当前能释放的能造成最大伤害的技能即可。维护两个优先队列,分别为不可用技能(释放限制血量大的优先出队)和可用技能(释放造成伤害大的优先出队)。每秒将已经可用的技能从不可用队列中取出,放到可用技能的队列中。如果此时可用技能不为空,则释放一个造成伤害最大的技能。如果当前没有可释放的技能,并且BUFF伤害小于等回血量y。则不可杀死主宰。

C++代码

Java代码

 

 

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

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

C. Vladik and chat

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:

<username>:<text>

If there are multiple answers, print any of them.

Examples

Input

Output

Input

Output

Input

Output

 题意:

给一段聊天记录,每条形如<username>:<text>或者<?>:<text>。其中<username>代表发出这条消息的人,<?>代表发消息的人未知。发话内容是由一些由逗号、句号、感叹号、问号和空格隔开的单词,并且每个人发话的单词中,不包含自己的名字。问给定的所有发话人的名单后,能不能将<?>确定下来。

思路:

先将每条记录处理出能发出这条记录的人,当然,已经确定<username>的就只有一个人,否则就是所有的未出现在这条消息中的单词的人。然后用dp[i][j]表示第i条记录由第j个人发出是否可行。记录一下dp的前驱,最后输出即可。

 

 

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.

Examples

input

output

input

output

题意

给定四个数,$a_{00}$,$a_{01}$,$a_{10}$,$a_{11}$,要求构建一个01串,使它的长度为2的子序列{x,y}的数目分别为$a_{xy}$。

题解

可以同个四个数字确定串内0的个数和1的个数,如果$a_{xx}=0$那么可以判断x的个数为0或者1,再根据$a_{xy}$和$a_{yx}$再进一步判断x的个数是0还是1。否则,如果x的个数为t,那么t*(t-1)/2=$a_{xx}$,如果找不到正整数t满足等式,说明给出的数据非法。这样就确定了0的个数n0和1的个数n1。可以发现n0*n1是一定要等于$a_{01}$+$a_{10}$的,否则数据非法。先将串初始化为n0个0和n1个1,此时这个串满足了$a_{00}$,$a_{11}$,但是$a_{01}$=n0*n1,$a_{10}$=0。可以发现,如果交换相邻两个01(起初0在1的前面),就会使$a_{01}$--,$a_{10}$++。那么根据这个规律,我们尝试把第一个0交换到后面第一个1的位置,第二个0交换到后面后面第一个1的位置,……每一次交换后,都可以让$a_{01}$-=n0,如果某一次交换会导致$a_{01}$--过小,那么只需要交换到刚好合适的位置即可。

 

Codeforces 708A Letters Cyclic Shift 水题

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.

Examples

input

output

input

output

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.

题意

给定一个字符串,要求选出一个非空子串,将其进行字母左移变换( 'z' 'y' 'x' 'b' 'a' 'z'),要求这样操作后,原串的字典序最小。

题解

从左往右,找到第一个不含a的子串,且长度在这个位置尽量延伸,那么找到的这个串就是题述要求的非空子串,将其左移变换即可。如果没有找到这样的串,说明原串是全a串,只能将最后一个字符变成z来达到题目要求。

 

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

题意:给出三个矩形的长和宽,问能否无缝无覆盖地拼接成正方形。

思路:先全排列着三个矩形,再枚举是否旋转每个矩形,这样,只需要检查3个并排和2个在上,1个在下的情况。只要姿势好,代码就短。

代码:

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 .

题意:给出n个技能及其伤害a[i],0<=a[i]<=100.现在有k点技能点,每点可以增加任意技能一点伤害,但是每个技能的伤害不能超过100,最后要求a[i]/10向下取整的和最大。

思路:先给个伤害位数大的技能加点,如果所有技能都变成10的倍数后还能加,再随意地把伤害小于100的技能加到100或者把k耗尽。

代码: