Heidi is in a big store. She would like to purchase $$$n$$$ items.
Today is her lucky day. The store runs a special sale: on every purchase, the customer receives one of the following two promotions:
- When at least $$$3$$$ items are bought together, the cheapest one is free.
- When fewer than $$$3$$$ items are bought together, the customer gets a $$$q$$$% discount on the purchase.
Heidi would like to buy all $$$n$$$ items on her shopping list, each exactly once. She can make an arbitrary number of purchases. For each purchase she'll make, the appropriate promotion will apply.
What is the minimum total price she has to pay to buy all $$$n$$$ items?
The first line contains two single space-separated integers $$$n$$$ ($$$1 \le n \le 100\,000$$$) and $$$q$$$ ($$$0 \le q \le 100$$$) – the number of items Heidi wants to buy and the percentage discount she gains for purchases of fewer than three items.
The following line contains $$$n$$$ single space separated integers $$$p_1, \dots, p_n$$$ – the prices of the goods ($$$100 \le p_i \le 100\,000$$$, $$$1\le i \le n$$$).
Additionally, it is guaranteed that each $$$p_i$$$ will always be divisible by 100. Hence, the discounted price of each purchase will always be an integer.
Output a single integer – the minimum total price Heidi has to pay in order to buy all $$$n$$$ items.
Subtask 1 (8 points): $$$n = 3$$$ and $$$100 \le p_i \le 1000$$$ ($$$1 \le i \le 3$$$)
Subtask 2 (18 points): $$$q = 0$$$
Subtask 3 (16 points): $$$q = 40$$$
Subtask 4 (22 points): $$$100 \le p_i \le 1\,000$$$ ($$$1 \le i \le n$$$)
Subtask 5 (36 points): No additional constraints.
7 10 300 200 200 300 100 300 200
1090
3 20 1000 500 100
1280
4 0 200 100 300 200
600
First, Heidi can buy the three items that cost 200 in a single transaction for 400 (she gets one of them for free). Then she can purchase the three items that cost 300 for 600 (again, one is free). Finally, she can purchase the last remaining item (with cost 100) with a $$$10\%$$$ discount.
In the second example test, if Heidi buys all three items in a single transaction, she receives discount of $$$100$$$. However, if she buys each item individually, her discount will be $$$(1000 + 500 + 100) \cdot 20/100 = 320$$$.
There is a railway between Zürich and Lugano of length $$$s$$$ kilometers. The railway crosses the beautiful Alps, resulting in a spectacular scenery during the ride. Since some passes are too high for the railway, there are $$$t$$$ tunnels on the track. The $$$i$$$-th of them starts $$$a_i$$$ kilometers from Zürich and ends $$$b_i$$$ kilometers from Zürich. (Thus, the length of the $$$i$$$-th tunnel is $$$b_i - a_i$$$.)
You have a timetable of the rail service between the two cities. There are $$$m$$$ services from Zürich to Lugano, the $$$j$$$-th of which departs at $$$c_j$$$ minutes, and $$$n$$$ services from Lugano to Zürich, the $$$k$$$-th of which departs at $$$d_k$$$ minutes. All trains operating on the track have a constant speed of 1 kilometer per minute, regardless of their direction and whether they are in a tunnel or not. There are no stations on the route, and the trains never stop at semaphores. Hence, each service arrives to its destination in exactly $$$s$$$ minutes.
The length of a train is negligible in comparison to the length of the railway, so in this problem please assume that each train is a point that moves along the railway.
Usually, the railway has two tracks: one in each direction. The only exception are the tunnels. Each tunnel has just a single track that can be used in either direction.
Whenever two trains going in the opposite directions meet outside a tunnel, they can pass each other safely. This includes trains meeting exactly at either end of a tunnel. On the other hand, if a pair of trains meets strictly inside a tunnel, there is a collision.
Given the description of the tunnels and the train services, determine whether there will be any collision.
The first line contains four space-separated integers $$$s$$$, $$$t$$$, $$$m$$$, $$$n$$$ ($$$1 \leq s \leq 1\,000\,000\,000$$$, $$$0 \leq t \leq 100\,000$$$, $$$0 \leq m, n \leq 2\,000$$$) – the length of the track, the number of tunnels, the number of services from Zürich and the number of services from Lugano, respectively.
The second line contains $$$t$$$ space-separated integers $$$a_i$$$ ($$$0 \leq a_i \lt s$$$) – the starting positions of the tunnels.
The third line contains $$$t$$$ space-separated integers $$$b_i$$$ ($$$0 \lt b_i \leq s$$$) – the ending positions of the tunnels.
For each $$$i$$$ between $$$1$$$ and $$$t$$$, $$$a_i \lt b_i$$$ holds. Additionally, for each $$$i$$$ between $$$1$$$ and $$$t-1$$$, $$$b_i \lt a_{i+1}$$$. (In other words, each tunnel has a positive length, the tunnels are pairwise disjoint, and they are given in increasing order of distance from Zürich.)
The fourth line contains $$$m$$$ space-separated integers $$$c_j$$$ ($$$0 \leq c_j \leq 1\,000\,000\,000$$$) – the starting times (in minutes) of the services starting in Zürich. The times are given in increasing order, that is, $$$c_j \lt c_{j+1}$$$ for all valid $$$j$$$.
The fifth line contains $$$n$$$ space-separated integers $$$d_k$$$ ($$$0 \leq d_k \leq 1\,000\,000\,000$$$) – the starting times (in minutes) of the services starting in Lugano. The times are given in increasing order, that is, $$$d_k \lt d_{k+1}$$$ for all valid $$$k$$$.
Output a single line, containing "YES" (quotes for clarity) if at least one crash occurs, or "NO" if all trains reach their destination safely.
In all subtasks except the last one, the value of $$$s$$$ and all $$$c_j$$$ and $$$d_k$$$ are even.
Subtask 1 (14 points): $$$t, m, n \leq 100$$$ and $$$s \leq 5\,000$$$.
Subtask 2 (16 points): $$$t \leq 5\,000$$$ and $$$s \leq 1\,000\,000$$$.
Subtask 3 (41 points): there are no further restrictions.
Subtask 4 (29 points): there are no further restrictions. Additionally, $$$s$$$, $$$c_j$$$ and $$$d_k$$$ are not necessarily even.
100 2 1 4 20 50 30 60 120 30 100 200 250
NO
1000 1 1 1 600 700 100 400
YES
1000 1 1 1 600 700 100 300
NO
1000 1 1 1 600 700 100 500
NO
In the first example there are two tunnels on a track of length $$$100$$$ kilometers: one $$$20$$$ to $$$30$$$ kilometers from Zürich, the other $$$50$$$ to $$$60$$$ kilometers from Zürich. The only train coming from Zürich manages to avoid all the Lugano services as follows:
- the first is met $$$5$$$ kilometers from Zürich,
- the second is met halfway between the tunnels,
- the third is met $$$10$$$ kilometers from Lugano,
- the fourth starts long after the Zürich train had arrived at its destination.
In the second example the only two trains meet exactly in the middle of the only tunnel, resulting in a crash.
In the third example the two trains meet exactly at the end of the tunnel that is closer to Zürich. In the fourth example they meet exactly at the other end of the tunnel. Both cases are fine, the trains pass each other and reach their destination safely.
Recent years have seen a rapid spread of the Extremely Green Oxen Illness (EGOI), which is a disease that makes cows dangerous to hikers. After several incidents it has been decided that we need to separate the areas where cows graze from the part of Alps where people want to hike.
You are given a map of the Alps. On the map there are $$$n$$$ areas. Each of them can be either a cow-populated area, a hiking area, or an unused area. Some pairs of areas are connected by bidirectional trails. Each trail has a non-negative length. (In graph-theoretic terms, the map is an undirected graph with weighted edges.)
You can build walls in some of the areas. Once you build a wall in an area, the area becomes inaccessible to hikers and cows – they will no longer be able to walk through such an area.
Your task is to select the set of areas where walls will be placed. This set of areas must satisfy the following conditions:
- It must consist only of unused areas.
- It must separate cow-populated areas from hiking areas. That is, a cow should no longer be able to walk along trails from a cow-populated area to a hiking area (without passing through an area with a wall).
- It must not separate any hiking areas from each other. That is, a hiker should still be able to walk along trails from any hiking area to any other hiking area (without passing through an area with a wall).
If there are multiple ways to reach the above goal, we will care about the ease of maintenance of the walls. The walls will be maintained by specialized crews. There is one such crew based in each hiking area.
For any area $$$A$$$ we define its remoteness as the minimum length of a path of trails between $$$A$$$ and some hiking area. (The length of a path is the sum of the lengths of its trails. Note that these paths may pass through walls and cow-populated areas – the wall maintenance crew has all the skills and equipment needed to do that.)
The remoteness of a set of areas is then the maximum remoteness of any area in this set.
Among all sets of areas with walls that have the required properties, find and return one with the smallest possible remoteness. If there are many such sets of areas, you may return any one of them.
Note that the number of areas does not matter. In particular, it is not required to use as few walls as possible.
The first line of the input contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$, $$$n-1 \leq m \leq 3 \cdot 10^5$$$) – the number of areas and trails, respectively. The areas are numbered from $$$1$$$ to $$$n$$$.
The second line contains $$$n$$$ space-separated integers $$$t_1, ..., t_n$$$, where $$$t_i$$$ is $$$-1$$$ if the $$$i$$$-th area is cow-populated, $$$0$$$ if it is unused, and $$$1$$$ if it is a hiking area.
The remaining $$$m$$$ lines describe trails. The $$$j$$$-th of them contains three space-separated integers $$$a_j$$$, $$$b_j$$$ and $$$\ell_j$$$ ($$$1 \le a_j \lt b_j \le n$$$, $$$0 \le \ell_j \le 10^9$$$), denoting a trail between areas $$$a_j$$$ and $$$b_j$$$ of length $$$\ell_j$$$.
It is guaranteed that:
- between any two areas there is at most one trail,
- it is currently possible to walk between any two areas using zero or more trails,
- there is at least one cow-populated area,
- there is at least one hiking area.
If it is impossible to build the walls according to the requirements, output -1.
Otherwise, the first line of the output should contain an integer $$$k$$$ – the number of walls you want to build. The second line should contain $$$k$$$ integers – the numbers of areas where you want to build the walls. (These numbers must be distinct numbers between $$$1$$$ and $$$n$$$, inclusive. They do not have to be in any particular order.)
The output will be accepted if it is an allowed set of walls with minimum remoteness.
Subtask 1 (7 points): $$$n \le 10$$$.
Subtask 2 (22 points): all lengths $$$\ell_j = 0$$$.
Subtask 3 (16 points): there is exactly one hiking area.
Subtask 4 (11 points): there are exactly $$$n-1$$$ trails (in graph-theoretic terms, the graph is a tree).
Subtask 5 (8 points): we have $$$n, m \le 2000$$$ and all lengths $$$\ell_j = 1$$$.
Subtask 6 (36 points): there are no additional constraints.
10 14 1 0 1 0 0 0 0 0 -1 -1 1 2 1 1 6 1 2 3 1 2 5 2 3 4 1 4 5 1 4 8 2 5 6 1 5 7 1 6 7 2 6 10 1 7 8 1 7 9 1 8 9 1
3 4 5 6
5 5 1 0 0 -1 0 1 2 1000 2 3 1000 3 4 10 4 5 10 1 5 10
2 3 5
4 3 1 0 -1 1 1 2 0 2 3 21 2 4 13
-1
In all of the figures, blue (dotted) is used for hiking areas, brown (full) for cow-populated areas and orange (dashed) for walls.
In the first example, the minimum possible remoteness is 2, achieved by placing walls in areas $$$4$$$, $$$5$$$ and $$$6$$$. Note that one cannot place walls in areas $$$4$$$, $$$2$$$ and $$$6$$$, even though this would yield a remoteness of $$$1$$$, because then it would be impossible to travel between the hiking areas $$$1$$$ and $$$3$$$ without passing through a wall.
In the second example, the remoteness of area 2 is 1000, and the remoteness of area 3 is 30, as it can be reached via path 1–5–4–3. (Recall that maintenance crews can pass through walls and cow-populated areas.) Therefore we should place walls in areas 5 and 3 (not 2), and the remoteness will be 30.
Alice and Bob are playing a game, and Claire is helping them. There are $$$n$$$ stones, numbered from $$$1$$$ to $$$n$$$. The game consists of three phases.
In the first phase, Alice and Bob make alternating moves. Alice moves first. In each move, a player declares their intention to take a stone, but instead of saying exactly which one, they name two options. It is possible for the two options to be the same. It is also possible to name stones that were already named in the previous moves. No stones are actually taken during the first phase — the players merely declare their intentions for the second phase. The first phase ends when $$$n+1$$$ declarations have been made.
Here is an example first phase for $$$n=3$$$:
- Alice: "I will take either stone 1 or stone 3"
- Bob: "I will take either stone 2 or stone 2"
- Alice: "I will take either stone 3 or stone 2"
- Bob: "I will take either stone 1 or stone 3"
In the second phase, for each of the $$$n+1$$$ declarations that have been made, Claire picks one of the two options by saying "first" or "second". We will call each sequence of $$$n+1$$$ choices made by Claire a scenario. Note that there are exactly $$$2\cdot2\cdot2\cdot\cdots\cdot2=2^{n+1}$$$ possible scenarios. (Even if, in some declaration, the first and the second option are the same, we consider picking the "first" or the "second" option to result in different scenarios.)
Here's one of the 16 scenarios Claire could choose in the above example:
- "First": Alice will take stone 1
- "First": Bob will take stone 2
- "Second": Alice will take stone 2
- "First": Bob will take stone 1
Finally, in the third phase, Alice and Bob actually start taking stones according to Claire's decisions. The first player who cannot make the required move – because the corresponding stone has already been taken – loses the game. Note that since there are $$$n$$$ stones and $$$n+1$$$ moves, one of the players must eventually lose the game.
In the above example, Alice starts by actually taking stone 1. Bob continues by taking stone 2. Alice wants to continue by taking stone 2, but it was already taken, so Alice loses the game and therefore Bob wins.
You are given the number $$$n$$$, and the state of the game at some point during the first phase: a sequence of $$$k$$$ declarations that have already been made. These declarations can be completely arbitrary.
From this point on, Alice and Bob will play the game optimally, as described in the following paragraph.
Regardless of how Alice and Bob play, Claire is equally likely to choose each of the $$$2^{n+1}$$$ possible scenarios. Alice and Bob know this and therefore when playing optimally, they are both trying to minimize the number of scenarios in which they lose.
Assume Alice and Bob will play the rest of the game as described above. For each of the two players find the number of scenarios in which they win the game.
The first line of input contains two space-separated integers $$$n$$$ and $$$k$$$ ($$$1\leq n\leq 35$$$, $$$0 \le k \le n+1$$$) – the number of stones and the number of declarations that have already been made.
The rest of the input consists of $$$k$$$ lines, each describing one declaration, in the order in which they were made. Each of these lines contains two space-separated integers: the numbers of two stones (both between $$$1$$$ and $$$n$$$, inclusive, and not necessarily distinct).
Note that when $$$k \lt n + 1$$$, the next player to make a declaration depends on the parity of $$$k$$$.
Output a single line with two space-separated integers: the number of scenarios in which Alice wins and the number of scenarios in which Bob wins, assuming both players play the rest of the game as described in the statement.
Note that the sum of the two numbers you print must be equal to $$$2^{n+1}$$$.
Subtask 1 (15 points): $$$n \leq 4$$$.
Subtask 2 (34 points): $$$n \leq 10$$$.
Subtask 3 (20 points): $$$n \leq 25$$$.
Subtask 4 (10 points): $$$k = 0$$$.
Subtask 5 (21 points): no additional restrictions.
3 4 1 3 2 2 3 2 1 3
4 12
2 0
4 4
The first example corresponds to the example from the problem statement. There are no more declarations to be made, so we just need to see how many of Claire's possible decisions lead to Alice's win, and how many of them lead to Bob's win. Alice will win if Claire picks stone $$$1$$$ for her on the first move, and stone $$$3$$$ for her on the second move, and will lose in all other cases.
In the second example, if Alice starts by declaring "1 1" , Bob will continue "2 2", and no matter what Alice declares on the third move, she will lose, as Claire will have to pick stone $$$1$$$ for the first move, and stone $$$2$$$ for the second move, and there will be no stones left for Alice in the third move. However, this is not the optimal first move for Alice: instead, she should start by declaring "1 2". Then, no matter what Bob does on the second move and what Alice does on the third move, each of them will win in $$$4$$$ cases out of $$$8$$$.