分类： 赛事资讯

Bessie is a hungry cow. Each day, for dinner, if there is a haybale in the barn, she will eat one haybale. Farmer John does not want Bessie to starve, so some days he sends a delivery of haybales, which arrive in the morning (before dinner). In particular, on day di, Farmer John sends a delivery of bi haybales (1≤di≤1014, 1≤bi≤109).

Compute the total number of haybales Bessie will eat during the first T days.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N and T (1≤N≤105, 1≤T≤1014).
The next N lines each contain di and bi. It is additionally guaranteed that 1≤d1<d2<⋯<dN≤T.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the number of haybales that Bessie will eat during the first T days.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

SAMPLE INPUT:

1 5
1 2

SAMPLE OUTPUT:

2
Two haybales arrive on the morning of day 1. Bessie eats one haybale for dinner on day 1 and another haybale on day 2. On days 3…5, there are no more haybales for Bessie to eat. In total, Bessie eats 2 haybales during the first 5 days.

SAMPLE INPUT:

2 5
1 2
5 10

SAMPLE OUTPUT:

3
Two haybales arrive on the morning of day 1. Bessie eats one haybale on days 1 and 2. There are no haybales for Bessie to eat on days 3 and 4. On the morning of day 5, 10 haybales arrive. Bessie eats one haybale for dinner on day 5. In total, Bessie eats 3 haybales during the first 5 days.

SAMPLE INPUT:

2 5
1 10
5 10

SAMPLE OUTPUT:

5
10 haybales arrive on the morning of day 1. Bessie eats one haybale on days 1…4. On the morning of day 5, another 10 haybales arrive, meaning there are 16 haybales in the barn. For dinner on day 5, Bessie eats another haybale. In total, Bessie eats 5 haybales during the first 5 days.

SCORING:

Inputs 4-7: T≤105
Inputs 8-13: No additional constraints.
Problem credits: Brandon Wang

Note: The time limit for this problem is 4s, twice the default.

Bessie is on vacation! Due to some recent technological advances, Bessie will travel via technologically sophisticated flights, which can even time travel. Furthermore, there are no issues if two "parallel" versions of Bessie ever meet.

In the country there are N airports numbered 1,2,…,N and M time-traveling flights (1≤N,M≤200000). Flight j leaves airport cj at time rj, and arrives in airport dj at time sj (0≤rj,sj≤109, sj<rj is possible). In addition, she must leave ai time for a layover at airport i (1≤ai≤109). (That is to say, if Bessie takes a flight arriving in airport i at time s, she can then transfer to a flight leaving the airport at time r if r≥s+ai. The layovers do not affect when Bessie arrives at an airport.)

Bessie starts at city 1 at time 0. For each airport from 1 to N, what is the earliest time when Bessie can get to at it?

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains N and M.
The next M lines describe flights. The jth of these lines contains cj, rj, dj, sj in that order. (1≤cj,dj≤N, 0≤rj,sj≤109)

The next line describes airports. It contains N space separated integers, a1,…,aN.

OUTPUT FORMAT (print output to the terminal / stdout):

There are N lines of output. Line i contains the earliest time when Bessie can get to airport i, or -1 if it is not possible for Bessie to get to that airport.

SAMPLE INPUT:

3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 10

SAMPLE OUTPUT:

0
0
20
Bessie can take the 3 flights in the listed order, which allows her to arrive at airports 1 and 2 at time 0, and airport 3 at time 20.

Note that this route passes through airport 2 twice, first from time 10-11 and then from time 0-1.

SAMPLE INPUT:

3 3
1 0 2 10
2 10 2 0
2 1 3 20
10 1 10

SAMPLE OUTPUT:

0
10
-1
In this case, Bessie can take flight 1, arriving at airport 2 at time 10. However, she does not arrive in time to also take flight 2, since the departure time is 10 and she cannot make a 1 time-unit layover.

SCORING:

Inputs 3-5: rj<sj for all j, i.e. all flights arrive after they depart.
Inputs 6-10: N,M≤5000
Inputs 11-20: No additional constraints.
Problem credits: Brandon Wang

Note: The time limit for this problem is 4s, two times the default.

Somebody has been grazing in Farmer John's (1≤G≤105) private gardens! Using his expert forensic knowledge, FJ has been able to determine the precise time each garden was grazed. He has also determined that there was a single cow that was responsible for every grazing incident.

In response to these crimes each of FJ's N (1≤N≤105) cows have provided an alibi that proves the cow was in a specific location at a specific time. Help FJ test whether each of these alibis demonstrates the cow's innocence.

A cow can be determined to be innocent if it is impossible for her to have travelled between all of the grazings and her alibi. Cows travel at a rate of 1 unit distance per unit time.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input will contain G and N separated by a space.
The next G lines contain the integers x, y, and t (−109≤x,y≤109;0≤t≤109) separated by a space describing the location and time of the grazing. It will always be possible for a single cow to travel between all grazings.

The next N lines contain x, y, and t (−109≤x,y≤109;0≤t≤109) separated by a space describing the location and time of each cow's alibi.

OUTPUT FORMAT (print output to the terminal / stdout):

Output a single integer: the number of cows with alibis that prove their innocence.

SAMPLE INPUT:

2 4
0 0 100
50 0 200
0 50 50
1000 1000 0
50 0 200
10 0 170

SAMPLE OUTPUT:

2
There were two grazings; the first at (0,0) at time 100 and the second at (50,0) at time 200.

The first cow's alibi does not prove her innocence. She has just enough time to arrive at the first grazing.

The second cow's alibi does prove her innocence. She is nowhere near any of the grazings.

Unfortunately for the third cow, being at the scene of the crime does not prove innocence.

Finally, the fourth cow is innocent because it's impossible to make it from her alibi to the final grazing in time.

SCORING:

Inputs 2-4: 1≤G,N≤103. Also, for both the fields and alibis, −106≤x,y≤106 and 0≤t≤106.
Inputs 5-11: No additional constraints.
Problem credits: Mark Gordon

Bessie has opened a bakery!

In her bakery, Bessie has an oven that can produce a cookie in tC units of time or a muffin in tM units of time (1≤tC,tM≤109). Due to space constraints, Bessie can only produce one pastry at a time, so to produce A cookies and B muffins, it takes A⋅tC+B⋅tM units of time.

Bessie's N (1≤N≤100) friends would each like to visit the bakery one by one. The ith friend will order ai (1≤ai≤109) cookies and bi (1≤bi≤109) muffins immediately upon entering. Bessie doesn't have space to store pastries, so she only starts making pastries upon receiving an order. Furthermore, Bessie's friends are very busy, so the ith friend is only willing to wait ci (ai+bi≤ci≤2⋅1018) units of time before getting sad and leaving.

Bessie really does not want her friends to be sad. With one mooney, she can upgrade her oven so that it takes one less unit of time to produce a cookie or one less unit of time to produce a muffin. She can't upgrade her oven a fractional amount of times, but she can choose to upgrade her oven as many times as she needs before her friends arrive, as long as the time needed to produce a cookie and to produce a muffin both remain strictly positive.

For each of T (1≤T≤100) test cases, please help Bessie find out the minimum amount of moonies that Bessie must spend so that her bakery can satisfy all of her friends.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T, the number of test cases.
Each test case starts with one line containing N, tC, tM. Then, the next N lines each contain three integers ai,bi,ci.

Consecutive test cases are separated by newlines.

OUTPUT FORMAT (print output to the terminal / stdout):

The minimum amount of moonies that Bessie needs to spend for each test case, on separate lines.

SAMPLE INPUT:

2

3 7 9
4 3 18
2 4 19
1 1 6

5 7 3
5 9 45
5 2 31
6 4 28
4 1 8
5 2 22

SAMPLE OUTPUT:

11
6
In the first test case, Bessie can pay 11 moonies to decrease the time required to produce a cookie by 4 and a muffin by 7, so that her oven produces cookies in 3 units of time and muffins in 2 units of time. Then she can satisfy the first friend in 18 units of time, the second friend in 14 units of time, and the third friend in 5 units of time, so none of them will get sad and leave.

In the second test case, Bessie should decrease the time required to produce a cookie by 6 and a muffin by 0.

SCORING:

Inputs 2-4: N≤10,tC,tM≤1000
Inputs 5-11: No additional constraints.
Problem credits: Benjamin Qi

Farmer John wrote down N (1≤N≤300) digits on pieces of paper. For each i∈[1,N], the ith piece of paper contains digit ai (1≤ai≤9).

The cows have two favorite integers A and B (1≤A≤B<1018), and would like you to answer Q (1≤Q≤5⋅104) queries. For the ith query, the cows will move left to right across papers li…ri (1≤li≤ri≤N), maintaining an initially empty pile of papers. For each paper, they will either add it to the top of the pile, to the bottom of the pile, or neither. In the end, they will read the papers in the pile from top to bottom, forming an integer. Over all 3ri−li+1 ways for the cows to make choices during this process, count the number of ways that result in the cows reading an integer in [A,B] inclusive, and output this number modulo 109+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains three space-separated integers N, A, and B.

The second line contains N space-separated digits a1,a2,…,aN.

The third line contains an integer Q, the number of queries.

The next Q lines each contain two space-separated integers li and ri.

OUTPUT FORMAT (print output to the terminal / stdout):

For each query, a single line containing the answer.

SAMPLE INPUT:

5 13 327
1 2 3 4 5
3
1 2
1 3
2 5

SAMPLE OUTPUT:

2
18
34
For the first query, there are nine ways Bessie can stack papers when reading the interval [1,2]:

Bessie can ignore 1 then ignore 2, getting 0.
Bessie can ignore 1 then add 2 to the top of the stack, getting 2.
Bessie can ignore 1 then add 2 to the bottom of the stack, getting 2.
Bessie can add 1 to the top of the stack then ignore 2, getting 1.
Bessie can add 1 to the top of the stack then add 2 to the top of the stack, getting 21.
Bessie can add 1 to the top of the stack then add 2 to the bottom of the stack, getting 12.
Bessie can add 1 to the bottom of the stack then ignore 2, getting 1.
Bessie can add 1 to the bottom of the stack then add 2 to the top of the stack, getting 21.
Bessie can add 1 to the bottom of the stack then add 2 to the bottom of the stack, getting 12.
Only the 2 ways that give 21 yield a number between 13 and 327, so the answer is 2.

SCORING:

Inputs 2-3: B<100
Inputs 4-5: A=B
Inputs 6-13: No additional constraints.
Problem credits: Jesse Choe

There are N pastures (2≤N≤2⋅105), connected by N−1 roads, such that they form a tree. Every road takes 1 second to cross. Each pasture starts out with 0 grass, and the ith pasture's grass grows at a rate of ai (1≤ai≤108) units per second. Farmer John is in pasture 1 at the start, and needs to drive around and fertilize the grass in every pasture. If he visits a pasture with x units of grass, it will need x amount of fertilizer. A pasture only needs to be fertilized the first time it is visited, and fertilizing a pasture takes 0 time.

The input contains an additional parameter T∈{0,1}.

If T=0, Farmer John must end at pasture 1.
If T=1, Farmer John may end at any pasture.
Compute the minimum amount of time it will take to fertilize every pasture and the minimum amount of fertilizer needed to finish in that amount of time.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N and T.
Then for each i from 2 to N, there is a line containing pi and ai, meaning that there is a road connecting pastures pi and i. It is guaranteed that 1≤pi<i.

OUTPUT FORMAT (print output to the terminal / stdout):

The minimum amount of time and the minimum amount of fertilizer, separated by spaces.

SAMPLE INPUT:

5 0
1 1
1 2
3 1
3 4

SAMPLE OUTPUT:

8 21
The optimal route for Farmer John is as follows:

At time 1, move to node 3, which now has 1⋅2=2 grass and so needs 2 fertilizer.
At time 2, move to node 5, which now has 2⋅4=8 grass and so needs 8 fertilizer.
At time 3, move back to node 3, which we already fertilized and so don't need to fertilize again.
At time 4, move to node 4, which now has 4⋅1=4 grass and so needs 4 fertilizer.
At time 5, move back to node 3, which we already fertilized.
At time 6, move back to node 1.
At time 7, move to node 2, which now has 7⋅1=7 grass and so needs 7 fertilizer.
At time 8, return to node 1.
This route takes 8 time and uses 2+8+4+7=21 fertilizer. It can be shown that 8 is the least possible amount of time for any route that returns to node 1 at the end and 21 is the least possible fertilizer used for any route that returns to node 1 and takes 8 time.

SAMPLE INPUT:

5 1
1 1
1 2
3 1
3 4

SAMPLE OUTPUT:

6 29
The optimal route for Farmer John is as follows:

At time 1, move to node 2, which now has 1⋅1=1 grass and so needs 1 fertilizer.
At time 2, move back to node 1.
At time 3, move to node 3, which now has 3⋅2=6 grass and so needs 6 fertilizer.
At time 4, move to node 5, which now has 4⋅4=16 grass and so needs 16 fertilizer.
At time 5, move back to node 3, which we already fertilized and so don't need to fertilize again.
At time 6, move to node 4, which now has 6⋅1=6 grass and so needs 6 fertilizer.
This route takes 6 time and uses 1+6+16+6=29 fertilizer. It can be shown that 6 is the least possible amount of time for any route and 29 is the least possible fertilizer used for any route that takes 6 time.

SCORING:

Inputs 3-10: T=0
Inputs 11-22: T=1
Inputs 3-6 and 11-14: No pasture is adjacent to more than three roads.
Problem credits: Rohin Garg

Note: The time limit for this problem is 3s, 1.5x the default.

FJ gave Bessie an array a of length N (2≤N≤500,−1015≤ai≤1015) with all N(N+1)2 contiguous subarray sums distinct. For each index i∈[1,N], help Bessie compute the minimum amount it suffices to change ai by so that there are two different contiguous subarrays of a with equal sum.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.
The next line contains a1,…,aN (the elements of a, in order).

OUTPUT FORMAT (print output to the terminal / stdout):

One line for each index i∈[1,N].

SAMPLE INPUT:

2
2 -3

SAMPLE OUTPUT:

2
3
Decreasing a1 by 2 would result in a1+a2=a2. Similarly, increasing a2 by 3 would result in a1+a2=a1.

SAMPLE INPUT:

3
3 -10 4

SAMPLE OUTPUT:

1
6
1
Increasing a1 or decreasing a3 by 1 would result in a1=a3. Increasing a2 by 6 would result in a1=a1+a2+a3.

SCORING:

Input 3: N≤40
Input 4: N≤80
Inputs 5-7: N≤200
Inputs 8-16: No additional constraints.
Problem credits: Benjamin Qi

Note: The time limit for this problem is 3s, 1.5x the default.

Bessie likes to watch shows on Cowflix, and she watches them in different places. Farmer John's farm can be represented as a tree with N (2≤N≤2⋅105) nodes, and for each node, either Bessie watches Cowflix there or she doesn't. It is guaranteed that Bessie watches Cowflix in at least one node.

Unfortunately, Cowflix is introducing a new subscription model to combat password sharing. In their new model, you can choose a connected component of size d in the farm, and then you need to pay d+k moonies for an account that you can use in that connected component. Formally, you need to choose a set of disjoint connected components c1,c2,…,cC so that every node where Bessie watches Cowflix must be contained within some ci. The cost of the set of components is ∑Ci=1(|ci|+k), where |ci| is the number of nodes in component ci. Nodes where Bessie does not watch Cowflix do not have to be in any ci.

Bessie is worried that the new subscription model may be too expensive for her given all the places she visits and is thinking of switching to Mooloo. To aid her decision-making, calculate the minimum amount she would need to pay to Cowflix to maintain her viewing habits. Because Cowflix has not announced the value of k, calculate it for all integer values of k from 1 to N.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.
The second line contains a bit string s1s2s3…sN where si=1 if Bessie watches Cowflix at node i.

Then N−1 lines follow, each containing two integers a and b (1≤a,b≤N), which denotes an edge between a and b in the tree.

OUTPUT FORMAT (print output to the terminal / stdout):

The answers for each k from 1 to N on separate lines.

SAMPLE INPUT:

5
10001
1 2
2 3
3 4
4 5

SAMPLE OUTPUT:

4
6
8
9
10
For k≤3, it's optimal to have two accounts: c1={1},c2={5}. For k≥3, it's optimal to have one account: c1={1,2,3,4,5}.

SAMPLE INPUT:

7
0001010
7 4
5 6
7 2
5 1
6 3
2 5

SAMPLE OUTPUT:

4
6
8
9
10
11
12

SCORING:

Inputs 3-5: N≤5000
Inputs 6-8: i is connected to i+1 for all i∈[1,N).
Inputs 9-19: N≤105
Inputs 20-24: No additional constraints.
Problem credits: Danny Mittal

Note: The memory limit for this problem is 512MB, twice the default.

Farmer John created N (1≤N≤105) problems. He then recruited M (1≤M≤20) test-solvers, each of which rated every problem as "easy" or "hard."

His goal is now to create a problemset arranged in increasing order of difficulty, consisting of some subset of his N problems arranged in some order. There must exist no pair of problems such that some test-solver thinks the problem later in the order is easy but the problem earlier in the order is hard.

Count the number of distinct nonempty problemsets he can form, modulo 109+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N and M.
The next M lines each contain a string of length N. The ith character of this string is E if the test-solver thinks the ith problem is easy, or H otherwise.

OUTPUT FORMAT (print output to the terminal / stdout):

The number of distinct problemsets FJ can form, modulo 109+7.

SAMPLE INPUT:
3 1
EHE

SAMPLE OUTPUT:
9
The nine possible problemsets are as follows:

[1]
[1,2]
[1,3]
[1,3,2]
[2]
[3]
[3,1]
[3,2]
[3,1,2]
Note that the order of the problems within the problemset matters.

SAMPLE INPUT:

10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE

SAMPLE OUTPUT:
33
SCORING:
Inputs 3-4: M=1
Inputs 5-14: M≤16
Inputs 15-22: No additional constraints.
Problem credits: Benjamin Qi

Note: The time limit for this problem is 6s, three times the default. The memory limit for this problem is 512MB, twice the default.

Bessie is a hungry cow. Each day, for dinner, if there is a haybale in the barn, she will eat one haybale. Farmer John does not want Bessie to starve, so some days he sends a delivery of haybales, which arrive in the morning (before dinner). In particular, on day di, Farmer John sends a delivery of bi haybales (1≤di≤1014, 0≤bi≤109).

Process U (1≤U≤105) updates as follows: Given a pair (d,b), update the number of haybales arriving on day d to b. After each update, output the sum of all days on which Bessie eats haybales modulo 109+7.

INPUT FORMAT (input arrives from the terminal / stdin):

U, followed by U lines containing the updates.

OUTPUT FORMAT (print output to the terminal / stdout):

The sum after each update modulo 109+7.

SAMPLE INPUT:

3
4 3
1 5
1 2

SAMPLE OUTPUT:

15
36
18
Answers after each update:

4+5+6=15
1+2+3+4+5+6+7+8=36
1+2+4+5+6=18

SAMPLE INPUT:

9
1 89
30 7
101 26
1 24
5 1
60 4
5 10
101 0
1 200

SAMPLE OUTPUT:

4005
4656
7607
3482
3507
3753
4058
1107
24531

SCORING:

Input 3: U≤5000
Inputs 4-10: Updates only increase the number of haybales arriving on day d.
Inputs 11-22: No additional constraints.
Problem credits: Brandon Wang and Benjamin Qi