HDU 6047 Maximum Sequence 贪心 优先队列

http://acm.hdu.edu.cn/showproblem.php?pid=6047

Maximum Sequence

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Steph is extremely obsessed with “sequence problems” that are usually seen on magazines: Given the sequence 11, 23, 30, 35, what is the next number? Steph always finds them too easy for such a genius like himself until one day Klay comes up with a problem and ask him about it.
Given two integer sequences {ai} and {bi} with the same length n, you are to find the next n numbers of {ai}: $a_{n+1}…a_{2n}$. Just like always, there are some restrictions on $a_{n+1}…a_{2n}$: for each number $a_i$, you must choose a number $b_k$ from {bi}, and it must satisfy $a_i$≤max{$a_j$-j│$b_k$≤j<i}, and any $b_k$ can’t be chosen more than once. Apparently, there are a great many possibilities, so you are required to find max{$\sum_{n+1}^{2n}a_i$} modulo $10^9$+7 .
Now Steph finds it too hard to solve the problem, please help him.

Input

The input contains no more than 20 test cases.
For each test case, the first line consists of one integer n. The next line consists of n integers representing {ai}. And the third line consists of n integers representing {bi}.
1≤n≤250000, n≤a_i≤1500000, 1≤b_i≤n.

Output

For each test case, print the answer on one line: max{$\sum_{n+1}^{2n}a_i$} modulo $10^9$+7。

 Sample Input

Sample Output

Hint

For the first sample: 1. Choose 2 from {bi}, then a_2…a_4 are available for a_5, and you can let a_5=a_2-2=9; 2. Choose 1 from {bi}, then a_1…a_5 are available for a_6, and you can let a_6=a_2-2=9;

Source

题意

给定两个长度为$n$数组$a_i,b_i$,现在要把$a_i$补充到长度为$2n$,从左到右补充,对于每一个$a_i$,需要选取一个未使用的$b_k$,$a_i$ 为$a$数组在$b_k~i-1$区间内的最小值。求$\sum_{n+1}^{2n}a_i$的最大值。

思路

对于每次取数,尽量取大即可,即使用当前能使用的最小的$b_k$。那么对$b_i$排序,将$a_i-i$放入优先队列,每次将堆顶的不合法元素弹掉,再取值记录答案,再将取出的值减去下标后压入优先队列。

 

 

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 709B Checkpoints 分类讨论

B. Checkpoints

time limit per test

1 second

memory limit per test

256 megabytes

 

Vasya takes part in the orienteering competition. There are n checkpoints located along the line at coordinates x1, x2, ..., xn. Vasya starts at the point with coordinate a. His goal is to visit at least n - 1 checkpoint in order to finish the competition. Participant are allowed to visit checkpoints in arbitrary order.

Vasya wants to pick such checkpoints and the order of visiting them that the total distance travelled is minimized. He asks you to calculate this minimum possible value.

Input

The first line of the input contains two integers n and a (1 ≤ n ≤ 100 000,  - 1 000 000 ≤ a ≤ 1 000 000) — the number of checkpoints and Vasya's starting position respectively.

The second line contains n integers x1, x2, ..., xn ( - 1 000 000 ≤ xi ≤ 1 000 000) — coordinates of the checkpoints.

Output

Print one integer — the minimum distance Vasya has to travel in order to visit at least n - 1 checkpoint.

Examples

input

output

input

output

input

output

Note

In the first sample Vasya has to visit at least two checkpoints. The optimal way to achieve this is the walk to the third checkpoints (distance is 12 - 10 = 2) and then proceed to the second one (distance is 12 - 7 = 5). The total distance is equal to 2 + 5 = 7.

In the second sample it's enough to visit only one checkpoint so Vasya should just walk to the point  - 10.

题意

给出n个横坐标上的点$x_{i}$,现在位于a位置,要访问其中的n-1个点,问最小需要跑多少距离。

题解:

很显然,不访问的点只会是排序后的第一个点或者最后一个点。分别处理两种方案,将答案求最小值即可。对于其中任意一种方案,假设删掉不访问的点后,如果a小于第一个点或者大于最后一个点,是一种情况;如果a在这两个点之间,又是另一种情况。

 

Codeforces 709A Juicer 水题

A. Juicer

time limit per test

1 second

memory limit per test

256 megabytes

 

Kolya is going to make fresh orange juice. He has n oranges of sizes a1, a2, ..., an. Kolya will put them in the juicer in the fixed order, starting with orange of size a1, then orange of size a2 and so on. To be put in the juicer the orange must have size not exceeding b, so if Kolya sees an orange that is strictly greater he throws it away and continues with the next one.

The juicer has a special section to collect waste. It overflows if Kolya squeezes oranges of the total size strictly greater than d. When it happens Kolya empties the waste section (even if there are no more oranges) and continues to squeeze the juice. How many times will he have to empty the waste section?

Input

The first line of the input contains three integers n, b and d (1 ≤ n ≤ 100 000, 1 ≤ b ≤ d ≤ 1 000 000) — the number of oranges, the maximum size of the orange that fits in the juicer and the value d, which determines the condition when the waste section should be emptied.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1 000 000) — sizes of the oranges listed in the order Kolya is going to try to put them in the juicer.

Output

Print one integer — the number of times Kolya will have to empty the waste section.

Examples

input

output

input

output

input

output

input

output

Note

In the first sample, Kolya will squeeze the juice from two oranges and empty the waste section afterwards.

In the second sample, the orange won't fit in the juicer so Kolya will have no juice at all.

题意

按顺序给了N个橘子,按顺序放进榨汁机进行榨汁,如果某个橘子的体积超过了b,直接扔掉,如果装进榨汁机的橘子的总体积超过了d,进行一次废渣清除。问需要进行多少次废渣清除操作。

题解

按照题意说的模拟就行了!

 

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个在下的情况。只要姿势好,代码就短。

代码: