## CodeForces 756B Travel Card 二分 DP

http://codeforces.com/problemset/problem/756/B

# B. Travel Card

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A new innovative ticketing systems for public transport is introduced in Bytesburg. Now there is a single travel card for all transport. To make a trip a passenger scan his card and then he is charged according to the fare.

The fare is constructed in the following manner. There are three types of tickets:

1. a ticket for one trip costs 20 byteland rubles,
2. a ticket for 90 minutes costs 50 byteland rubles,
3. a ticket for one day (1440 minutes) costs 120 byteland rubles.

Note that a ticket for x minutes activated at time t can be used for trips started in time range from t to t + x - 1, inclusive. Assume that all trips take exactly one minute.

To simplify the choice for the passenger, the system automatically chooses the optimal tickets. After each trip starts, the system analyses all the previous trips and the current trip and chooses a set of tickets for these trips with a minimum total cost. Let the minimum total cost of tickets to cover all trips from the first to the current is a, and the total sum charged before is b. Then the system charges the passenger the sum a - b.

You have to write a program that, for given trips made by a passenger, calculates the sum the passenger is charged after each trip.

### Input

The first line of input contains integer number n (1 ≤ n ≤ 105) — the number of trips made by passenger.

Each of the following n lines contains the time of trip ti (0 ≤ ti ≤ 109), measured in minutes from the time of starting the system. All ti are different, given in ascending order, i. e. ti + 1 > ti holds for all 1 ≤ i < n.

### Output

Output n integers. For each trip, print the sum the passenger is charged after it.

### Examples

input

output

input

output

Note

In the first example, the system works as follows: for the first and second trips it is cheaper to pay for two one-trip tickets, so each time 20 rubles is charged, after the third trip the system understands that it would be cheaper to buy a ticket for 90 minutes. This ticket costs 50 rubles, and the passenger had already paid 40 rubles, so it is necessary to charge 10 rubles only.

## HDU 5951 Winning an Auction 博弈论DP

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

# Winning an Auction

### Problem Description

Alice and Bob play an auction game. Alice has A dollars and Bob has B dollars initially. There are N items on sale. In each round, an item will be sold by the following way. Alice writes down an integer a (0 ≤ a ≤ A) and Bob writes down an integer b (0 ≤ b ≤ B), which are the amount of dollars they want to pay for the item. If a > b, then Alice gets the item and pays a dollars to the seller. If a < b, then Bob gets the item and pays b dollars to the seller. If a = b, then for the 1st, 3rd, 5th, 7th ... round, Alice gets the item and pays a dollars; for the 2rd, 4th, 6th, 8th ... round, Bob gets the item and pays b dollars. Since all the items have the same value, the goal of the auction game is to get as many items as possible. Both Alice and Bob know the values of N,A and B. Your task is to calculate how many items they will get if both of them play optimally.

### Input

The first line is the number of test cases.
Each test case contains 3 integers N,A and B, which are no larger than
255.

### Output

For each test case, output the number of items
Alice and Bob will get if both of them play optimally.

3
1 1 2
2 4 2
3 3 3

Alice 0 Bob 1
Alice 1 Bob 1
Alice 2 Bob 1

## HDU 5981 Guess the number DP决策

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

# Guess the number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 160000/160000 K (Java/Others)

### Problem Description

AOA just met a problem when he attended an interview, as shown below:
A and B two people play guessing games. A thinks of a number x between a and b randomly in his mind, and he lets B to guess this number. A will say too small if B’s guess is less than x and A will say yes if B’s guess is just x.Once B’sguess is bigger than x,A won't speak any more.After that,A just nods his head if B’s guess is just x,otherwise shakes his head.The problem is that how many kinds of best guess strategies to make the least number of guesses in the worst situation?

### Input

Input contains multiple sets of test data and each of them occupies one line,including two integersa, b(1≤a≤b≤5 * 10^6),on behalf of range of the number.Input to the end of the file.

### Output

For each set of input, output one line containing two integers. The first one represents the least number of times of guessing in the worst situation. The second one represents the number of best guess method modulo 100000073.

1 5

### Sample Output

3 3

Hint

B can guess the number in A's mind up to 3 times in the worst case. The first method,B can guess in the order of (2,4,5) The second method,B can guess in the order of (3,4,5) The third method,B can guess in the order of (3,5) Each method is up to three times.

## HDU 5972 Regular Number Bitset优化字符串匹配

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

# Regular Number

### Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Problem Description

Using regular expression to define a numeric string is a very common thing. Generally, use the shape as follows:
(0|9|7) (5|6) (2) (4|5)
Above regular expression matches 4 digits:The first is one of 0,9 and 7. The second is one of 5 and 6. The third is 2. And the fourth is one of 4 and 5. The above regular expression can be successfully matched to 0525, but it cannot be matched to 9634.
Now,giving you a regular expression like the above formula,and a long string of numbers,please find out all the substrings of this long string that can be matched to the regular expression.

### Input

It contains a set of test data.The first line is a positive integer N (1 ≤ N ≤ 1000),on behalf of the regular representation of the N bit string.In the next N lines,the first integer of the i-th line is $a_i(1 ≤a_i≤ 10)$,representing that the i-th position of regular expression has $a_i$ numbers to be selected.Next there are $a_i$ numeric characters. In the last line,there is a numeric string.The length of the string is not more than 5 * 10^6.

### Output

Output all substrings that can be matched by the regular expression. Each substring occupies one line

4
3 0 9 7
2 5 7
2 2 5
2 4 5
09755420524

9755
7554
0524

## HDU 5956 树上进行斜率优化DP + 记录操作并撤销

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

# The Elder

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

### Problem Description

Once upon a time, in the mystical continent, there is a frog kingdom, ruled by the oldest frog, the Elder. The kingdom consists of N cities, numbered from east to west. The 1-th city, which is located to the east of others, is the capital. Each city, except the capital, links none or several cities to the west, and exactly one city to the east.
There are some significant news happening in some cities every day. The Elder wants to know them as soon as possible. So, that is the job of journalist frogs, who run faster than any other frog. Once some tremendous news happen in a city, the journalist in that city would take the message and run to the capital. Once it reach another city, it can either continue running, or stop at that city and let another journalist to transport. The journalist frogs are too young and simple to run a long distance efficiently. As a result, it takes $L^2$ time for them to run through a path of length L. In addition, passing message requires P time for checking the message carefully, because any mistake in the message would make the Elder become extremely angry.
Now you are excited to receive the task to calculate the maximum time of sending a message from one of these cities to the capital.

### Input

The first line of input contains an integer t, the number of test cases. t test cases follow. For each test case, in the first line there are two integers N (N ≤ 100000) and P (P ≤ 1000000). In the next N-1 lines, the i-th line describes the i-th road, a line with three integers u,v,w denotes an edge between the u-th city and v-th city with length w(w ≤ 100).

### Output

For each case, output the maximum time.

3
6 10
1 2 4
2 3 5
1 4 3
4 5 3
5 6 3
6 30
1 2 4
2 3 5
1 4 3
4 5 3
5 6 3
6 50
1 2 4
2 3 5
1 4 3
4 5 3
5 6 3

### Sample Output

51
75
81

Hint

In the second case, the best transportation time is: • The 2-th city: 16 = 4^2 • The 3-th city: 72 = 4^2 + 30 + 5^2 • The 4-th city: 9 = 3^2 • The 5-th city: 36 = (3 + 3)^2 • The 6-th city: 75 = (3 + 3)^2 +30 + 3^2 Consequently, the news in the 6-th city requires most time to reach the capital.

## HDU 6004 Periodical Cicadas 中国剩余定理 + 二维RMQ

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

# Periodical Cicadas

Time Limit: 14000/7000 MS (Java/Others)    Memory Limit: 80000/80000 K (Java/Others)

### Problem Description

Nearly all cicadas spend years underground as juveniles, before emerging above ground for a short adult stage of several weeks to a few months.
The seven periodical cicada species are so named because, in any one location, all of the members of the population are developmentally synchronized they emerge as adults all at once every seven years.
The lifecycles of most periodical cicada species range from two to seventeen years, although some could be longer.
There is a forest which can be roughly divided into a matrix of size N ×M. The upper-left region is (1, 1) and the lower-right region is (N, M).
A population of periodical cicadas live within each region of the matrix. The population in region (i, j) emerged in year $a_{i,j}$ for the first time, and re-emerges every $b_{i,j}$ years. i.e. they are $b_{i,j}$ - periodical cicadas.
Given a selected rectangular area, entomologists wonder if there is a time when all cicadas in that area emerge together.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test cases begin with two integers N and M.
The following N lines each consists of M integers $a_{i,j}$ representing the year cicadas emerged in region (i, j) for the first time.
The following N more lines each consists of M integers $b_{i,j}$ representing the periodical cycle of the cicadas in that region.
Then comes a line with an integer Q representing the number of queries. The following Q lines each consists of 4 integers: $x_1, y_1, x_2, y_2,$ representing the upper-left and lower-right coordinate of the selected rectangular area.

### Output

For each test case, first output one line containing “Case #x:”, where x is the test case number (starting from 1).
The following Q lines each consists of an integer which is the year when all cicadas in the selected area emerge together for the first time or -1 if it’s impossible.

### limits

$\bullet 1 ≤ T ≤ 10.$
$\bullet 1 ≤ N, M ≤ 200.$
$\bullet 0 ≤ a_{i,j} < b_{i,j} ≤ 40.$
$\bullet 1 ≤ x_1 ≤ x_2 ≤ N.$
$\bullet 1 ≤ y_1 ≤ y_2 ≤ M.$
$\bullet$ 1 ≤ Q ≤ 500000.

2
3 4
3 1 1 2
1 1 2 1
1 0 5 5
5 4 2 3
2 2 3 2
4 2 6 6
5
2 2 2 2
1 1 3 4
1 4 2 4
1 1 1 2
2 2 3 4
1 2
0 1
2 2
1
1 1 1 2

Case #1:
1
-1
5
13
-1
Case #2:
-1

## HDU5957 Query on a graph 基环树 + BFS序列 + 线段树区间维护

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

# Query on a graph

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

### Problem Description

You are given a connected simple graph(in which both multiple edges and loops are disallowed) with N nodes and N edges. In this graph each node has a weight, and each edge has the same length of one unit. Define D(u,v) as the distance between node u and node v. Define S(u,k) as the set of nodes x which satisfy D(u,x) ≤ k.
We will ask you to perform some instructions of the following forms.
MODIFY u k d: weight of all nodes in S(u,k) increase by d or decrease by -d.
QUERY u k: ask for the sum of weight of all nodes in S(u,k).
In the beginning, the weight of all nodes are 0.

### Input

The first line of input contains an integer t, the number of test cases. t test cases follow. For each test case, in the first line there is an integer N(N ≤ 100000). The i-th line of the next N line describes the i-th edge: two integers u,v denotes an edge between u and v. In the next line, an integer Q(Q ≤ 100000) indicates the number of instructions. Next Q lines contain instructions MODIFY u k d or QUERY u k, where |d|≤ 100 and 0 ≤ k ≤ 2.

### Output

For each QUERY instruction, output a integer in a line.

2
6
1 2
2 3
3 4
4 1
4 5
3 6
5
MODIFY 1 1 3
MODIFY 3 1 2
MODIFY 5 2 1
QUERY 3 2
QUERY 4 1
6
1
2 2
3 3
1 1
4 2
5 3
6 5
MODIFY 3 1 5
MODIFY 2 2 2
QUERY 6 1
MODIFY 4 1 -2
QUERY 2 2

21
14
14
28

# E. Dividing Kingdom

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A country called Flatland is an infinite two-dimensional plane. Flatland has n cities, each of them is a point on the plane.

Flatland is ruled by king Circle IV. Circle IV has 9 sons. He wants to give each of his sons part of Flatland to rule. For that, he wants to draw four distinct straight lines, such that two of them are parallel to the Ox axis, and two others are parallel to the Oy axis. At that, no straight line can go through any city. Thus, Flatland will be divided into 9 parts, and each son will be given exactly one of these parts. Circle IV thought a little, evaluated his sons' obedience and decided that the i-th son should get the part of Flatland that has exactly aicities.

Help Circle find such four straight lines that if we divide Flatland into 9 parts by these lines, the resulting parts can be given to the sons so that son number i got the part of Flatland which contains ai cities.

### Input

The first line contains integer n (9 ≤ n ≤ 105) — the number of cities in Flatland. Next n lines each contain two space-separated integers: xi, yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of the i-th city. No two cities are located at the same point. The last line contains nine space-separated integers: .

### Output

If there is no solution, print a single integer -1.

Otherwise, print in the first line two distinct real space-separated numbers: x1, x2 — the abscissas of the straight lines that are parallel to the Oy axis. And in the second line print two distinct real space-separated numbers: y1, y2 — the ordinates of the straight lines, parallel to the Ox. If there are multiple solutions, print any of them.

When the answer is being checked, a city is considered to lie on a straight line, if the distance between the city and the line doesn't exceed 10 - 6. Two straight lines are considered the same if the distance between them doesn't exceed 10 - 6.

### Examples

input

output

input

output

input

output

Note

The solution for the first sample test is shown below:

The solution for the second sample test is shown below:

There is no solution for the third sample test.

## 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.

Input

Output

Input

Output

Input

Output

## Codeforces 754E Dasha and cyclic table bitset优化矩阵匹配

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

# E. Dasha and cyclic table

time limit per test

6 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

Dasha is fond of challenging puzzles: Rubik's Cube 3 × 3 × 3, 4 × 4 × 4, 5 × 5 × 5 and so on. This time she has a cyclic table of size n × m, and each cell of the table contains a lowercase English letter. Each cell has coordinates (i, j) (0 ≤ i < n, 0 ≤ j < m). The table is cyclic means that to the right of cell (i, j) there is the cell , and to the down there is the cell .

Dasha has a pattern as well. A pattern is a non-cyclic table of size r × c. Each cell is either a lowercase English letter or a question mark. Each cell has coordinates (i, j) (0 ≤ i < r, 0 ≤ j < c).

The goal of the puzzle is to find all the appearance positions of the pattern in the cyclic table.

We say that the cell (i, j) of cyclic table is an appearance position, if for every pair (x, y) such that 0 ≤ x < r and 0 ≤ y < c one of the following conditions holds:

• There is a question mark in the cell (x, y) of the pattern, or
• The cell of the cyclic table equals to the cell (x, y) of the pattern.

Dasha solved this puzzle in no time, as well as all the others she ever tried. Can you solve it?.

### Input

The first line contains two integers n and m (1 ≤ n, m ≤ 400) — the cyclic table sizes.

Each of the next n lines contains a string of m lowercase English characters — the description of the cyclic table.

The next line contains two integers r and c (1 ≤ r, c ≤ 400) — the sizes of the pattern.

Each of the next r lines contains a string of c lowercase English letter and/or characters '?' — the description of the pattern.

### Output

Print n lines. Each of the n lines should contain m characters. Each of the characters should equal '0' or '1'.

The j-th character of the i-th (0-indexed) line should be equal to '1', in case the cell (i, j) is an appearance position, otherwise it should be equal to '0'.