Little Tinu is a handsome kid and likes only beautiful things. He has an array and wants its most beautiful permutation. The beauty of a 1-indexed array A is defined as:
is integer division.The first line contains T(1 ≤ T ≤ 10), the number of test cases. Every test case contains 2 lines. First line has an integer N(1 ≤ N ≤ 103), the size of the array A. Second line contains the array A as space separated integers(0 ≤ Ai ≤ 106).
Output for each test case, the maximum beauty of any permutation of the array A.
2
3
3 2 1
4
1 40 70 40
2
69
Sample test case 1:
There are 6 permutations possible:
Beauty = 2
Beauty = 1
Beauty = 1
Beauty = - 1
Beauty = - 1
Beauty = - 2
Maximum of all beauties is 2.
Sample test case 2:
The best permutation is [1, 40, 70, 40] where beauty is 69.
An array is called a 'Mirror' if it reads the same backward and forward. For example, [23, 15, 23] is a 'Mirror' but [2, 0, 1] is not.
You are given an array A of size N. Your task is to make a given array a 'Mirror'. The only allowed operation is that you can merge two adjacent elements in the array and replace them with their sum.
Find minimum number of operations required to make given array a 'Mirror' such that it reads the same backward and forward.
First line contains T(1 ≤ T ≤ 20), the number of test cases. Each test case consist of 2 lines. First line contains number N(1 ≤ N ≤ 105), size of the array. Next line contains N space separated integers Ai(0 ≤ Ai ≤ 109) denoting elements in the array A.
For each test case output in one line minimum steps required to make given array a 'Mirror'.
2
3
1 0 1
5
10 20 20 10 40
0
3
Sample test case 1:
Given array is already a 'Mirror' . So, no need to perform any operation.
Sample test case 2:
One possible sequence of operations.
Step 1 : Merge 2nd and 3rd element to get array [10, 40, 10, 40].
Step 2 : Merge 1st and 2nd element to get array [50, 10, 40].
Step 3 : Merge 2nd and 3rd element to get array [50, 50].
Chunin exams are going on. To pass the "Stage 2:The Forest of Death", Naruto has to reach the tower in time. As you know Naruto has very little memory. Help Naruto find his way through the forest of death.
The forest of death is N × M grid(N and M are not given in input). Rows are numbered from 1 to N in 
to 
direction and columns are numbered 1 to M in 
to 
direction. Naruto is currently at position (1, 1) and tower is at position (N, M). It is given that 1 ≤ N, M ≤ 104.
P cells are dangerous for Naruto and he can't go to those cells(0 ≤ P ≤ 5 * 104). Your task is to help Naruto navigate through the grid with help of a system which responds to two type of queries:
- Naruto can
at four edge-adjacent cells from his current position in the grid. In response to this query, system will tell whether its safe to go to those positions. Its always unsafe to go outside the grid. - Naruto can perform
queries, which will result in Naruto moving one step from his current position to one of the adjacent safe cells. In response to such query, you will be told whether you've reached tower or not.
You are not allowed more than 12 * P + 4 * (N + M) queries. Also, note the unusual memory limit.
All lines of input stream consist of response to queries in one line.
To make a query, print a line which contains a string query. Don’t forget to put a newline character and to flush the output stream after you print your query.
Note that testing system will not provide N and M in input. Your solution asks the queries and the system answers them as given in statement.
For a query, you specify the string 
, where 
denoting the direction of adjacent square to which you want to look. In response to this query, you can read from STDIN, one of the string, 
or 
denoting whether you can go to the adjacent cell in corresponding direction or not.
For a query, you specify the string 
, where denoting the direction of adjacent square to which you want to go to. System will change the current position of Naruto to corresponding square and return a string 
or 
denoting whether Naruto has reached the tower or not. After receiving a , your program should exit successfully.
If your query contains wrong characters, the system will terminate the testing and you will receive the "Presentation Error" outcome.
If you perform a query which results in Naruto's position to a dangerous cell, or if you exceed the number of allowed queries, you will receive a "Wrong Answer" outcome.
You will receive the "Time Limit Exceeded" outcome and other errors for the usual violations.
Finally, if everything is OK (i.e. Naruto reaches destination) on every test, you will receive the "Accepted" outcome, in this case you will have solved the problem.
SAFE
NO
UNSAFE
SAFE
YES
LOOK RIGHT
GO RIGHT
LOOK DOWN
LOOK RIGHT
GO RIGHT
In this example, N = 1 and M = 3.
Read sample output and then system input line by line.
Naruto starts at (1, 1) and looks at (1, 2)(output line 1) which is safe(input line 1), then goes there(output line 2), where system tells that Naruto hasn't reached tower(input line 2), looks at (2, 2)(output line 3) which is unsafe(input line 3), then he looks at (1, 3)(output line 4), which is safe(input line 4), and reaches there(output line 5), which is the location of the target(input line 5).
You are given two positive integers N and M.
Let function 
denote the number of distinct positive divisors of k. For example, 
, 
.
The set 
is defined as the set of all positive integers i such that 
and all prime factors of i are less than or equal to the Mth prime number. For example, 
as 3rd prime number is 5 and the numbers with prime factors less than or equal to 5 with number of positive divisors = 2 are 2, 3, 5.
You have to print the number of elements in 
. As this number can be very large, print this number modulo 109 + 7.
The first line contains T(1 ≤ T ≤ 5 * 105), the number of test cases. Each test case contains two numbers N and M(1 ≤ N ≤ 2 * 106 and 1 ≤ M ≤ 109).
Output for each test case the answer in a separate line.
2
2 3
4 5
3
15
Sample test case 1:
The 3rd prime number is 
.
Sample test case 2:
The 5th prime number is 
As these are the only numbers with number of divisors equal to 4 and prime factors ≤ 11.
Jorah Mormont and Khal Drogo both like the Khaleesi. Why wouldn't they, she's incredibly hot! But only one of them can get her, right? Since battling it out has become a little old-fashioned, they decided to play a game to decide the winner.
There exists a directed acyclic graph with N nodes, numbered from 1 to N, and M directed edges(no self-loops or multi edges). Jorah is at the node 1 initially. The players play turn by turn, Jorah starts. In every turn, Jorah can move along one directed edge from his current position to any node x, if and only if there exists a directed edge from his current node to node x. Also, Khal can remove any one edge he wants in his turn. The game goes on until Jorah reaches node N, or if he is unable to make any valid move. It is guaranteed that between any pair of nodes, there exists at most one edge.
The Khaleesi is waiting at node N. If Jorah is able to reach this node, he gets to keep her, else, Khal does. Assuming both play optimally, who will win?
The first line of input contains number of test cases, T(1 ≤ T ≤ 10). Every test case starts with two integers N and M(2 ≤ N ≤ 100 and 0 ≤ M ≤ 200). Next M lines contain two integers u and v, signifying that there exists a directed edge from node u to node v(1 ≤ u, v ≤ N). It is guaranteed that the resulting graph is acyclic.
The output must contain T lines. If Jorah wins, output "Jorah Mormont"(without quotes) or else, output "Khal Drogo"(without quotes).
2
2 1
1 2
5 6
1 2
1 3
2 3
2 4
3 4
4 5
Jorah Mormont
Khal Drogo
Sample test case 1:
Jorah moves from node 1 to node 2 and reaches the Khaleesi. Hence, he wins.
Sample test case 2:
Jorah moves from node 1 to node 3. Then Khal removes the edge from node 3 to node 4. Jorah cannot make any more moves, hence Khal wins.
You are given 2 coordinate axis aligned rectangles R1 and R2. You can apply at most K moves on R1.
A move is defined as follows: You can choose any of the four edges E of the current configuration of R1 and flip(reflect) R1 about E. E can be different in each move. For example, if R1 is currently between denoted by bottom-left and top-right corners by (0, 0) and (1, 1) and we flip it about the right edge(i.e. edge between (1, 1) and (1, 0)) then the configuration of R1 will be between (1, 0) and (2, 1).
Let A be the area of overlap of R2 and final configuration of R1. What is the maximum overlap area you can achieve?
The first line contains T(1 ≤ T ≤ 105), the number of test cases. Every test cases has three lines of input. First line has four integers Sx, Sy, Sw, Sh, where (Sx, Sy) are the x and y coordinates of the bottom-left corner of the R1 rectangle. Sw is its width (along x-axis) and Sh is its height(along y-axis). Next line has four integers Dx, Dy, Dw, Dh representing the R2 rectangle in a similar fashion. Next line has one integer K(0 ≤ K ≤ 109). Absolute value of all coordinates doesn't exceed 109. Width and height lie between 1 and 109(both inclusive).
Output for each query, the maximum overlap area you can achieve.
1
0 0 10 10
20 20 5 10
0
0
Sample test case 1:
There is no overlap initially and we can't make any move.
You want to buy a gift pack for a party, and you figure what better than a fine collection of wine.
The wine cellar has gift packs containing three wine bottles each. But the old salesman does not remember the exact ages of the wine bottles. He only remembers that the first bottle in the pack is aged somewhere between L and R(both inclusive), the second bottle is at-most A years old and the third bottle is at-most B years old. Note that a bottle can be 0 years old too.
Being a wine connoisseur you know that if the age of first bottle is x, second bottle is y and third bottle is z, then the combined deliciousness of the gift pack will be
where '^' is bitwise XOR and '&' is the bitwise AND operator.
You want to know what can be the maximum deliciousness for each of the N gift packs. You have the information given by the salesman for each pack.
First line contains N(1 ≤ N ≤ 104), the number of gift packs in the cellar. Next, N lines follow, ith line describing ith gift pack. Each line has four integers L, R, A and B(0 ≤ L ≤ R ≤ 1018 and 0 ≤ A, B ≤ 1018).
Print N lines, ith line containing the answer for the ith gift-pack.
2
0 1 1 1
0 2 2 2
3
8
Sample test case 1:
One possible answer is x = 0, y = 1, z = 1.
Sample test case 2:
One possible answer is x = 1, y = 2, z = 2.
In the magical world of felicity, there is a merry go round. This merry go round is in the shape of a convex polygon. The polygon has N points each of which is defined by x and y coordinates. Felicity celebrates a lot of magical festivals, in which any one side of the polygon acts as a magical base, i.e, it lies on the x-axis. This side is denoted by two vertices, pl and pr. When the side acts as a magical base, pl coincides with the origin and pr lies somewhere else to the right of the origin on the magical base. Unfortunately, there is an infinitely long vertical magical wand, perpendicular to the magical base, that lies at k distance from the origin on the magical base. It is ensured that k > x', where x' is maximum x-coordinate of any polygon vertex. Now this wand falls in counter-clockwise direction till it hits the merry go round.
When the wand hits the merry go round, it generates a flash at the point(s) of collision. Given Q festivals where each is defined by a base, pl and pr, and by a k, can you tell what the flash points are?
The first line contains N(3 ≤ N ≤ 105) and Q(1 ≤ Q ≤ 105), the number of points and number of festivals.
The first N lines are the points of the merry go round in counter-clockwise order and each of the lines has two integers xi and yi( - 109 ≤ xi, yi ≤ 109). Points are indexed from 0 to N - 1 in the order of input.
This is followed by Q lines where each line has two integers 
and k(
and 1 ≤ k ≤ 109). Here denotes pl of an edge and pr of that edge is 
.
Output for each query is the indices of the points that lit up. If the wand collides with only a point, output the index of that point. Else, if it collides with an edge, output the indices of the two vertices where the second vertex lies counter clockwise ahead of the first vertex.
4 1
0 0
1 0
1 1
0 1
0 2
2
iChandu is a playful young man. He like strings a lot and has an interesting problem for you. He gives a string of lowercase letters of length N. You have to replace exactly one position in the string by character 
, such that the number of distinct palindromic substrings in the new string is maximized. You also have to find the number of different such strings possible.
First line contains T(1 ≤ T ≤ 5), the number of test cases. Each test case consist of one line, the string iChandu gave you. Length of the string is N(1 ≤ N ≤ 105).
For each test case output two values: maximum number of distinct palindromic substrings in the new string and different number of such strings possible.
1
aba
3 3
Sample test case 1:
Three different strings possible:
distinct palindromic substrings = 3 
.
distinct palindromic substrings = 3 
.
distinct palindromic substrings = 3 
.
Hence maximum distinct palindromic substrings are 3, and count of distinct strings that generate 3 different substrings is 3.
You have just visited a country which consists of N cities, with exactly one path between every pair of cities(i.e. the country forms a weighted undirected tree with N vertices).
A non-empty subset of all the cities form a set of "special" cities. For every "special" city, you need to find what is the farthest distance from that city to any other "special" city. But since the country is still developing, the roads between two cities can change and the set of "special" cities also keep changing.
First line contains N(1 ≤ N ≤ 105), followed by N - 1 lines each containing three values u v w, which means that there is a road between cities u and v with distance w(1 ≤ u, v ≤ N and 1 ≤ w ≤ 109).
The next line contains Q(1 ≤ Q ≤ 105), the number of queries. The next Q queries contain an integer 1 or 2 in one line, indicating the type of query.
For each type, the next line in the input is of the format:
- u v w : Update the weight of edge between u and v to w(1 ≤ u, v ≤ N and 1 ≤ w ≤ 109).
- An integer K(1 ≤ K ≤ N) followed by the K integers denoting the set of "special" cities for current query.
Note that sum of K over all queries ≤ 5 * 105.
For each query of type 2, print a single line with K values which is the answer for each of those "special" cities.
5
1 2 2
2 3 2
2 4 2
1 5 1
3
2
3 5 2 4
1
4 2 5
2
3 5 2 4
5 3 5
8 5 8
For first query:
For city 5, city 4 is farthest "special city" at distance 5 and vice-versa. For city 2, city 5 is farthest "special city" at distance 3.
CodeCraft'16 gives you the opportunity to become a killer(legally!). Subject to the constraint that you are best at your job. So you have to prove yourself.
Given an undirected, unweighted, connected graph with N vertices and M edges, you have to add at most K new edges in the graph to minimize the number of bridges.
There will be Q queries each with a K. Each query is independent i.e. you have to consider the original graph for each query.
First line contains three integers N, M and Q(1 ≤ N, Q ≤ 105 and 0 ≤ M ≤ 2 * 105). Next M lines contain u and v denoting an undirected edge between u and v(1 ≤ u, v ≤ N). Next Q lines contain a single integer K(1 ≤ K ≤ M) denoting the maximum number of edges that you can add.
For each query output the maximum number of bridges you can kill.
3 2 1
1 2
2 3
1
2
Adding the edge 
removes the existing 2 bridges.
You have organized an event and for that you decorated the entire city, the City Mayor is the chief guest after all. You would like to show the Mayor around. But the Mayor is a picky person, he says he will travel exactly for K roads.
The City has N areas(numbered from 1 to N) and M undirected roads in total. You know the map and the fatigue value of each road, each pair of areas have at-most one road between them. You need to find for each pair of cities, what is the minimum fatigue value the Mayor will get if you show him around between that pair of cities, also you need to find out what are the number of ways in which the Mayor will get the minimum fatigue for that pair of city. Since the number of ways may be very large output it modulo (109 + 7).
First line contains N, M and K(0 ≤ N ≤ 150, 
and 0 ≤ K ≤ 109). Next M lines consists of description of all the roads; ith line has three integers u, v and w(1 ≤ u, v ≤ N and - 106 ≤ w ≤ 106) which means that there is a direct path between area u and area v and has a fatigue value of w(the paths are undirected).
Output N lines, each containing 2 * N numbers. In the ith line, for each j(1 ≤ j ≤ N) output two integers: the minimum fatigue value if you start from i and go to j using exactly K roads; the number of ways to achieve that minimum fatigue value, modulo 109 + 7. If there is no path between i and j, using exactly K edges, output character 
for fatigue value and 0 for number of ways.
3 3 1
1 2 1
2 3 1
3 1 1
X 0 1 1 1 1
1 1 X 0 1 1
1 1 1 1 X 0
Note that there is no shortest path using one road from node i to node i, for all i.
For all other pair of nodes, there exist exactly one shortest path using one road.