You have n candies. You want to give as much to your friends as possible, but you have a problem; every time you give two friends a candy each, you can't help but eat one yourself (if you have one left). You tried to resist after giving the first one, but after giving the second, it was unbearable.
What is the maximum number of friends you can give candies to?
The first line of input contains n (1 ≤ n ≤ 109), the number of candies you have.
Output a single line with the maximum number of friends you can give candies to.
4
3
5
4
6
4
You have a problem set of ten problems. Each team in the contest has a skill level from 1 to 10 and each of the ten problems has a difficulty level from 1 to 10. A team can only solve problems that have a difficulty level less than or equal to their skill level.
You want to add one more problem with difficulty from 1 to 10 such that each team solves at least one problem. What is the maximum difficulty that this problem can have?
The first line of input contains n (1 ≤ n ≤ 32), the number of teams participating in the contest.
The second line of input contains n integers si (1 ≤ si ≤ 10), the skill level of the teams.
The third line of input contains 10 integers di (1 ≤ di ≤ 10), the difficulty level of the problems in the problem set so far.
Output on a single line the maximum possible difficulty level for the new problem from 1 to 10 such that each team solves at least one problem.
4 3 7 5 5 4 6 5 7 4 4 9 10 7 9
3
You have a class of n number of students arranged in a circle. Last month, this seating arrangement caused too much noise in the class and now you want to rearrange the students.
To avoid chatting, you want to arrange the students such that no two students that were next to each other in last month's arrangement are next to each other in the new arrangement.
If possible, print one arrangement that satisfies the conditions.
The first line of input contains n (3 ≤ n ≤ 3 × 105), the size of the class.
The next line of input contains a permutation of the numbers from 1 to n, representing the IDs of the students in last month's seating arrangement. Note that the permutation is circular, and the first student is adjacent to the last student.
Output the students' IDs in one possible circular seating arrangement that satisfies the conditions. If there is no possible answer, output -1 on a single line.
If there is more than one possible solution, output any of them.
8 6 1 3 5 7 8 4 2
1 7 2 3 8 6 5 4
3 1 3 2
-1
The sample test is illustrated in the picture above. Note that no two students are adjacent in both arrangements.
You have a class of even number of students n. The class can be divided into n / 2 pairs of best friends, who always like to stay next to each other. Unfortunately, this makes your job harder because today is picture day.
For a perfect picture, you want to align the students in order of non-decreasing heights then non-increasing heights. Each pair of best friends must be next to each other, however, their relative order does not matter (friends a and b ordered as ab or ba both work).
For example, [1, 2, 4, 3, 3, 1] ,[1, 5, 10, 11], [11, 10, 5, 5], [3, 3, 3, 3] are perfect height arrangements as numbers first do not decrease, then they do not increase.
Given the pairs of best friends, can you arrange them to make a perfect picture?
The first line of input contains a single even integer n (2 ≤ n ≤ 3 × 105), the number of students in the class.
Each of the following n / 2 lines contains two integers ha hb (1 ≤ ha, hb ≤ 109), the heights of a pair of best friends in the class.
Output any valid arrangement of the class' heights such that each pair of best friends are standing next to each other.
If there is no answer, output -1 on a single line.
8 1 3 4 2 6 7 5 7
2 4 5 7 7 6 3 1
You are playing the classical snake game on your phone, where a snake moves around on an infinite grid. However in this game, the snake has been programmed with a series of moves represented as a string. The characters 'U', 'D', 'L', and 'R' in the string cause the snake to move up, down, left, and right, respectively. The snake cannot visit the same cell twice in fear of colliding with itself.
In this version of the game, you want to find out the longest substring of the string of moves such that the snake never visits the same cell twice.
The first line of input is n (1 ≤ n ≤ 106), the length of the string of snake moves.
The second line contains the string of snake moves where each character is in the set {'L', 'R', 'U', 'D'}.
Output a single line with the length of the longest substring of moves such that the snake would not visit the same cell twice if it followed those moves.
4 RULD
3
13 RRDDLLUUURDDR
10
3 RRU
3
2 RL
1
You are given an array of n positive integers. You want to divide the array into one or more parts, where each part is a subarray of the original array. Every integer must be included in exactly one part. After that, you will get the sum of each part, then multiply all the sums together.
For example, the array [8, 1, 1, 3] can be divided into parts [8], [1, 1], and [3], with sums 8, 2, and 3, respectively, giving a product of 48. Note that each part consists of consecutive elements of the array.
Divide the given array in a way that maximizes the final product.
The first line of input contains a single integer n (1 ≤ n ≤ 3 × 105), the size of the array.
The second line of input contains n integers ai (1 ≤ ai ≤ 109), where ai is the ith integer in the array.
Print exactly one line; the line must contain the input succession a1, a2, ... an divided into parts such that the product of the sums of each part is maximized. Use the slash character ('/') to separate the parts. Separate numbers and slashes with a single space.
If there are multiple solutions, print any of them.
4 8 1 1 3
8 / 1 1 / 3
3 1 1 1
1 1 1
You are given a number with n digits written in base b. For example, our monetary system is written in base 10 (i.e. 926 JOD) and a binary number is written in base 2 (i.e. 10101110).
Your task is to find the next greater number that consists of distinct digits (no digit is repeated twice).
It is guaranteed that there is an answer for the given number.
The first line of input contains two integers n and b (1 ≤ n ≤ 3 × 105) (2 ≤ b ≤ 3 × 105), the number of digits of the number and the base it is written in.
The second line of input contains n integers ai (0 ≤ ai < b), where ai is the ith digit in the number. It is guaranteed that the number has no leading zeros.
Output a single line with the next greater number that consists of distinct digits. Separate the digits by a single space.
3 10 9 2 6
9 2 7
4 11 10 5 5 1
10 5 6 0
4 4 3 2 0 1
3 2 1 0
2 5 4 3
1 0 2
You are given a string of digits from 1 to 8, each digit represents one of the 8 directions in clockwise order as shown in the following picture. The picture also states the changes in the X and Y coordinates for each direction.
Count the number of substrings such that if you start at (0, 0) and follow the directional moves in the substring, you will draw one closed convex polygon, that is, you need to finish at (0, 0), all interior angles should be less than or equal to 180°, and the polygon should not intersect itself.
The first line of input contains a single integer n (1 ≤ n ≤ 3 × 105), the length of the string.
The second line contains a string of n digits from 1 to 8.
Output on a single line with the number of substrings that draw out one closed convex polygon.
8 31753317
3
8 33228666
1
8 28863535
0
In the first sample test, substrings (1, 4), (2, 5), and (3, 6) draws the three convex polygons from left to right, respectively.
In the second sample test, the whole string represents a convex polygon, any other substring will be open, so the answer is 1.
In the third sample test, the whole string represents a closed polygon but it is not convex, other substrings draw open polygons, so the answer is 0.
You are given a tree that represents a hierarchy in a company, where the parent of node u is their direct manager.
Each employee is assigned a project, and multiple employees can be assigned to the same project. When it is time for the presentation of the ith project, all employees u that are assigned that project and their direct and indirect managers must attend the presentation (u and their manager and their manager's manager and so on until the CEO).
Find for each project the number of people attending its presentation.
The first line of input is n and m (1 ≤ m ≤ n ≤ 106), the number of employees and the number of projects, respectively.
The second line of input contains n integers ai (1 ≤ ai ≤ m), where ai is the project assigned to the ith employee. It is guaranteed that each project has at least one employee assigned to it.
The third line of input contains n integers pi (0 ≤ pi ≤ n), where pi is the direct manager of the ith employee. If pi = 0, then the ith employee is the CEO and does not have a manager. It is guaranteed that there is only one CEO, and this CEO is a direct or indirect manager of all other employees.
Output m integers, where the ith integer is the number of people attending the presentation of the ith project.
6 4 1 2 4 3 2 4 0 1 1 3 3 2
1 4 3 4
You have a grid of 2 rows and c columns where n cells in the grid are colored black. A black colored cell is adjacent to another black colored cell if they share an edge in the up, down, left, or right direction.
All black cells in the grid are initially connected as one component. You then assign unique indices from 1 to n randomly to all the black cells, and draw an undirected graph that connects two indices of black cells if they were adjacent in the original grid.
Unfortunately, after drawing the graph, you lost the original grid. Given the drawn graph, build and color a new grid of 2 rows and c columns with n black cells, and assign the unique indices from 1 to n to the black cells such that we can build the same given graph from this grid.
The first line of input contains three integers c, n and e (1 ≤ c ≤ 105, 1 ≤ n ≤ 2 × c, e ≥ n - 1), the number of columns, the number of black cells, and the number of edges in the graph.
Each of the following e lines contains two space-separated integers u and v (1 ≤ u, v ≤ n), representing an edge between two black cells with indices u and v.
It is guaranteed that the given graph is constructed in the described method and doesn't contain loops or multiple edges.
Print two lines, each with c integers, representing the constructed grid. Each black cell should contain a distinct number from 1 to n, other cells should contain 0.
If there is more than one solution, output any of them.
7 10 10 2 10 7 4 10 3 1 4 3 9 9 6 1 6 5 4 6 8 8 3
2 10 3 8 0 7 0 0 0 9 6 1 4 5
You are given an undirected connected weighted graph that is comprised of a chain that connects simple cycles. No two cycles in the graph share a common vertex, therefore you can imagine the graph as circles of nodes connected by chains. Assuming size n, the nodes 1 and n are guaranteed to not be on cycles and have a degree of size one, and all nodes of the graph are on a simple path from node 1 to node n.
You want to travel from node 1 to node n and back to node 1 in minimal time. At any node along the way from node 1 to n, when you are at node u, you can assign it as one end of a magical portal. But once you assign it, you have no more than k seconds to assign the other end of the portal v, otherwise it will disappear. Once you assign the two ends, the portal is activated and you may use it to travel between node u and v in zero time.
Assuming you travel and choose the portal ends optimally, what is the minimal time needed to get from node 1 to node n and back to node 1 using at most one portal?
The first line of input contains three integers n, e, k (2 ≤ n ≤ 3 × 105, e ≥ n - 1, 1 ≤ k ≤ 108), the number of nodes, edges, and k is the timeout after first portal end is assigned.
Each of the following e lines contains three integers u, v, w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 1000), representing that nodes u and v are connected by an edge that takes w seconds to cross.
It is guaranteed that there are no loops or multiple edges and that the graph is connected, with nodes 1 and n having degree one.
The given graph matches the description in the problem statement.
On a single line, output the minimal time needed to get from node 1 to node n and back to node 1 using at most one portal.
12 13 14 1 2 2 4 3 5 10 9 2 9 8 7 2 5 3 6 4 2 2 3 2 10 11 5 11 7 6 9 12 4 5 4 3 8 7 1 10 6 3
24
The sample test is illustrated in the picture above. To minimize the time, we start at node 1 move to node 5 in 5 seconds, assign it as the first end of the portal, then move to node 12 in 14 seconds, and assign it as the other end of the portal, then we can go back from node 12 to node 5 in zero seconds using the portal, then move to node 1 in 5 seconds. So the total time would be 5+14+0+5=24.
As the travelling distance between the two ends of the portal doesn't exceed k = 14, our solution is valid.