Arcade mall is a new modern mall. It has a new hammer game called "Arcade Game". In this game you're presented with a number n which is hanged on a wall on top of a long vertical tube, at the bottom of the tube there is a button that you should hit with your hammer.
When you hit the button with all your force (as you always do), a ball is pushed all over the tube and hit the number n. The number n flies in the air and it's digits fall back in any random permutation with uniform probability.
If the new number formed is less than or equal to the previous number, the game ends and you lose what ever the new number is. Otherwise (if the number is greater than the previous number), you are still in the game and you should hit the button again.
You win if the new number formed is greater than the previous number and it is equal to the greatest possible permutation number.
Can you compute the probability of winning?
The first line of the input contains the number of test cases T. Following that there are T lines represents T test cases. In each line, there is a single integer (1 ≤ n ≤ 109) the target number. The digits of n are all unique, which means that any 2 digits of n are different.
For each test case, print one line containing the answer. Print the answer rounded to exactly 9 decimal digits.
3
952
925
592
0.000000000
0.166666667
0.194444444
In the first test case, the answer is 0 because 952 is greater than all 2,5 and 9 permutations so you can't win, whatever you do.
In the second test case, the answer is 0.166666667 because you may win by getting number 952 with probability 1/6.
In the third test case the answer is 0.194444444 because you may win by getting number 952 in round1 with probability 1/6 or you can win by getting number 925 in round 1 and then 952 in round 2 with probability 1/6 * 1/6.
Ali is a teacher in one of Kuwait universities. Last week he made a multi-choice test for his students. After the test, he marked some papers before collecting all papers and going home. However, he discovered that he forgot the solution key at the university. He is sure that he didn't make any mistake in correcting papers, so in order to complete the correction process, he decided to extract the solution key from the papers that have already been marked.
Ali knows that each question should have one and only one correct choice, can you help him with extracting the correct answers for all the questions?
The first line of the input is a single integer T, the number of test cases. Each test case will consist of several lines. The first line contains 2 integers separated by a single space: (1 ≤ Q ≤ 100 and 0 ≤ M ≤ 100) representing the number of questions in the test, and the number of the corrected papers, respectively. Each of the next M lines will contain 2Q upper case letters separated by single spaces: qi ai ( 
{'A','B','C','D'} and 
{'T','F'}) representing the student answer for the ith question (from a corrected paper) and the status of the student answer 'T' if it is True or 'F' if it is False.
For each test case, print a single line contains Q characters separated by single spaces: 
{'A','B','C','D','?'}) representing the correct answer of ith question that could be extracted from the given corrected papers or '?' in case it could not be determined.
2
3 2
A F B F C T
B T C F D F
1 3
A F
B F
C F
B ? C
D
Alex is known to be very clever, but Walter does not believe that. In order to test Alex, he invented a new game. He gave Alex n nodes, and a list of queries. Walter then gives Alex one query every second, there are two types of queries:
means: adding an undirected edge between nodes u and v.
means: what was the earliest time (query index) when u and v became connected? 2 nodes are connected if there is a path of edges between them. Alex can solve this problem easily, but he is too busy now, so he is asking for your help.
The first line contains an integer T, the number of test cases. Each test case begins with a line containing two integers (1 ≤ n, m ≤ 105), the number of nodes and queries, respectively. Then there are m lines, each line represents a query and contains three integers, type, u and v (
, 1 ≤ u, v ≤ n)
For each query of type 2, print one line with one integer, the answer to the query. If the 2 nodes in the query are not connected, print -1.
1
4 5
1 1 2
2 1 2
1 2 3
2 1 3
2 1 4
1
3
-1
Warning: large Input/Output data, be careful with certain languages.
In winter, all small rivers of Al-Asi great river in Syria are frozen. But when spring comes back they start to melt. These small rivers are connected to each other exactly like a tree, each river (direct edge in the tree) has a value equal to the amount of ice in it.
Here is the tree of the sample test case:
When rivers start to melt, water starts to flow from node 1 (root of the tree) to any node that it can reach. When the water first reaches a node u, ice starts to melt in all its direct children edges at a rate of 1 unit per second. Once (u, v) edge completely melted, the rate of melting of all other edges that start from u will slow down to be 0.5 unit per second, while the other edges that start from v start melting with 1 unit per second.
Given the rivers tree, and a certain time, can you tell us how many leaves of the tree did the water reach? A leaf is a node that has no children.
The first line contains T the number of test cases. For each test case, the first line contains N the number of nodes (2 ≤ N ≤ 100, 000). Followed by N - 1 lines, each line describes the nodes 2 to N. Each line will contain 2 integers Pi and Ci (1 ≤ Pi ≤ N) (0 ≤ Ci ≤ 100,000) representing the parent of the i-th node (i starts from 2 here) and the amount of ice in the edge connecting the current node to its parent. Node 1 is the root of the tree. After that there is a line contains (1 ≤ Q ≤ 100, 000), the number of queries. Then Q lines contain the times of these queries in seconds (0 ≤ query time ≤ 1012).
Print one line for each query in each test case, this line should contain the number of leaves that the water reached at the time of the query.
1
4
1 3
1 5
2 2
8
1
2
3
4
5
6
7
8
0
0
0
0
1
1
2
2
In the sample test case:
At time 0: water is at node 1
At time 1: water has melted 1 unit of edge (1, 2), and 1 unit of edge (1, 3)
At time 3: water has completely melted edge (1, 2). The rate of melting of (1, 3) drops to 0.5 unit/second, while edge (2, 4) starts to melt at rate 1 unit/second.
At time 5: water has completely melted edge (2, 4), and the remaining edge (1, 3) has 4 units melted, 1 to go.
At time 7: Ice completely melted in all edges.
Palmyra is an oasis in the Syrian desert, north-east of Damascus, Palmyra contains the monumental ruins of a great city that was one of the most important cultural centers of the ancient world.
Omar is a famous Archaeologist from Egypt, he came to Syria in a monument drilling mission.
After one year of hard work with his team, Omar has a very good reason to believe that the ancient Syrians used the base - 6 numerical system (instead of the base - 10 we usually use). They found an ancient map, and they plan to use it to support their claim.
The map describes a rectangular city buried underground, the city has n × m district distributed on n rows and m columns. Each district contains a magical stone has a power p. If we merge two stones of power a and b we will have a stone of power a × b. Omar will dig exactly n + m - 1 districts starting from the most top left district, each time he digs a district he can choose to move either right or down.
Omar thinks that, after moving in the described way and merging all the magical stones he has, he will get a stone with some trailing zeros in the base - 6 representation of its power.
Given the power of stones in each district , Your task is to tell Omar what is the maximum possible number of trailing zeros in the base - 6 numeral system representation of the power of the final stone he could make.
Your program will be tested on one or more test cases. The first line of the input contains a single integer T the number of test cases. Followed by T test cases.
Each test case consists of N+1 lines. The first line contains two integers N (2 ≤ N ≤ 100), M (2 ≤ M ≤ 100), the dimensions of the city.
The next N lines consists of M integers separated by a single space: Xij (1 ≤ Xij ≤ 103) which refers to the power of the stone in the jth district of the ith row written in base - 10 numeral system representation.
For each test case print a single line containing the maximum possible number of trailing zeros in the base - 6 representation of the final merged stone power.
1
3 3
3 2 3
2 3 2
3 2 3
2
Trailing zeros are a sequence of continuous 0's in the right most digits of the representation of a number, that are followed by a none-zero digit, for example: 18010 = 5006 has one trailing zero in the decimal representation, and two trailing zeros in base-6 system.
Geometry is a very important field in mathematics, Squares and rectangles are essential shapes in geometry, both of them have 4 right angles, but a square is a special case of a rectangle where width and height are the same.
The figure below shows a square on the left and a rectangle on the right:
If you have the width and the height of a 4 right angled shape, can you figure out if it is a square or a rectangle?
The first line contains T, the number of test cases, for each test case there is a line with two integers (1 ≤ w, h ≤ 1, 000, 000) representing width and height, respectively.
For each test case, print one line consists of 'Square' if the shape is a square, otherwise print 'Rectangle' if it is a rectangle.
3
10 10
13 200
300 300
Square
Rectangle
Square
Foki is the president of the Martian United States of Altanie, Altanie is a very large and strange country. Each citizen in it has a positive integer wisdom value calculated based on her/his age and educational level (of course Foki has the maximum value). Altanie has a big map for all its roads, this map has the following properties:
- There are N cities in Altanie, and the cities are numbered from 1 to N.
- Each road connects 2 different cities, and all roads are bidirectional.
- Each road requires a minimal wisdom value for the citizen to have the right to use it.
- Each road costs some amount of Martian money to use it.
- There is at most one road between each 2 cities.
Foki cares about all people of his country, so he is wondered about the minimum wisdom value that is needed to go from city 1 to city N with a total cost less than K, your job is to answer this question for him.
The first line of the input contains T the number of the test cases. The first line of each test contains 1 < N ≤ 105 the number of the cities in Altanie, 1 ≤ M ≤ 105, the number of roads connecting the N cities and 1 ≤ K ≤ 109 the total cost.
Each of the next M lines contain a description of one of the M roads, each road is described with 1 ≤ s1, s2 ≤ N the numbers of two cities the road connects,1 ≤ c ≤ 109 the cost you have to pay each time you use this road, 1 ≤ W ≤ 109the minimal amount of wisdom value needed to have the right to use the road.
For each test case print one line contains the answer of the following question: What is the minimum wisdom value a citizen should have to be able to go from city 1 to city N with cost less than K? if there is no solution, print -1.
2
5 6 3
1 2 1 1
1 4 1 1
1 3 1 1
2 5 2 1
2 4 1 1
3 5 1 5
5 6 2
1 2 1 1
1 4 1 1
1 3 1 1
2 5 2 1
2 4 1 1
3 5 1 5
5
-1
Warning: large Input/Output data, be careful with certain languages.
Reem is organizing a big dinner tonight. In her garden there are two tables in the shape of regular polygons. One of those tables is the dinner table, and the other one is the dessert table. The guests will first eat dinner at the dinner table, and when dinner is over, they will all go to the dessert table to eat dessert. They will sit at the corners of the polygonal tables. Reem decided to assign a certain seating order for the guests around the dinner table, and another seating order for the guests around the dessert table. When dessert time comes, all guests will leave the dinner table, follow different paths in the garden, and reach their assigned seats at the dessert table. Reem wants the paths that the guests will follow to have minimal total number of intersections among themselves. She will provide you with the seating orders of the guests, and you will find the least possible number of intersections for the paths.
You may assume the following:
1) There will be n guests at the party and each will sit at a different corner. No two guests may share the same table corner. Reem herself is not considered a guest and won't be seated.
2) The garden has unlimited length in all directions. The dinner and the dessert table are regular polygons with n sides and n corners and they are centered at 2 different points in the garden. Dinner and dessert tables do not intersect in any way.
3) Each path is a curve that starts at a corner of the dinner table, and ends at a corner of the dessert table. A path may not intersect the tables at any point.
4) For any pair of guests (A,B), the path of guest A will have at most 1 point in common with the path of guest B.
5) No three or more paths will intersect at the same point, so each intersection point is between exactly 2 paths only.
The figure below shows one of the optimal solutions for first test case in the sample test:
The input will start with a single integer T, the number of test cases. Each test case will consist of three lines: The first line contains a single integer (2 < n < 100), the number of guests. The second line contains n space-separated strings (the names of the guests, given according to their seating order around the dinner table). The third line contains n space-separated strings (the names of the guests, given according to their seating order around the dessert table). Names will consist of no more than 10 alphanumeric characters and no two guests will have the same name. The list of names will be given in the clockwise order around each table.
Print a single line for each test case containing a single integer representing the minimum total number of intersections between paths.
2
3
A B C
A B C
3
Rayan Mustafa Ahmad
Rayan Ahmad Mustafa
1
0
Salem is known to be one of the best competitive programmers in the region. However, he always finds a hard time understanding the concept of the hamming distance. The hamming distance of two numbers is defined as the number of different digits in their binary representations (leading zeros are used if necessary to make the binary representations have the same length). For example the hamming distance between 12 and 5 is 2 since their binary representations are 1100 and 0101 respectively and they differ in the first and fourth positions.
Recently, Salem got a problem that he needs your help to solve. He is given N integers and asked to get the maximum among the hamming distances of all possible pairs of the given integers.
The first line of the input will be a single integer T representing the number of test cases. Followed by T test cases. Each test case will start with a line with single integer (2 ≤ N ≤ 100) representing the number of the integers. Each of the following N lines contains one of the integers (1 ≤ Ai ≤ 10, 000) from the list of the integers.
For each test case print one line consists of one integer representing the maximum hamming distance between all possible pairs from the given integers.
2
2
12
5
3
1
2
3
2
2
Salah and Marzo were reading a research paper, when they found a very large string A contains only lower case English letters. They decided to play a game with it. In the beginning, they agreed on a mapping that maps each pair of characters into a new character, for example:
(a, a) - > b
(a, b) - > d
(a, c) - > a
...
(z, y) - > r
(z, z) - > o
Then they start playing the game on the string, each move is either LEFT or RIGHT:
LEFT Move takes each two consecutive characters and combines them into a single character starting from the last two characters (two rightmost characters). For example if we have the transformation (a, a) - > d, (c, a) - > e and we have the string acaa it becomes ed.
RIGHT Move takes each two consecutive characters and combines them into a single character starting from the first two characters (two leftmost characters). For example if we have the transformation (a, a) - > d, (d, a) - > f and we have the string aadaa it becomes dfa. Notice that the last character couldn't be combined with any other character so it's left as is.
They start making moves and alternating turns until they end up with a single character, Salah wins if this character is a vowel, otherwise Marzo wins. Salah always plays first. If both of them are playing in an optimal way, can you determine the winner?
The first line contains T, the number of test cases, then T test cases follow:
Each test case begins with 26 lines, the ith line contains a string Si of 26 lowercase english letters. Si, j is the mapping of letters i and j ('a'=1,'b'=2,...,'z'=26) e.g. S3, 2 is the mapping of letters 'c' and 'b'. (You can assume that Si, j = Sj, i for all 1 ≤ i, j ≤ 26 ) The next line of each test case contains the string A ( 1 ≤ |A| ≤ 10, 000 )
The output should consist of T lines, the ith line is "Salah" if Salah wins in the ith test case, or "Marzo" otherwise.
1
daeaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
eaaaaaaaaaaaaaaaaaaaaaaaaa
aaaahaaaaaaaaaaaaaaaaaaaaa
aaahaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
acaa
Marzo
Vowel letters are : a, e, i, o, u
Johnny is a brilliant mathematics student. He loves mathematics since he was a child, now he is working on his PhD thesis. He faces a small mathematical problem, he has a n digit integer number (let us call it s) , he wants to find how many substring of s are divisible by a prime number p.
His supervisor professor is on vacation now, so can you play his role and help him with that?
The first line contains the number of test cases T. Each of the next T lines represents a test case. For each test case you will be given 4 numbers: 1 ≤ a, b ≤ 1018, 1 ≤ n ≤ 106, 2 ≤ p < 200. Where a < b. s is not directly given in the input, you have to calculate it from a and b as follows: s is the first n digits from the decimal representation of a / b (treat a / b decimal representation as it has an infinite digits and just take the first n digits from the left)
For each test case you should print one line containing the number of substrings of s that can be divided by p without remainder.
3
2 4 3 5
2 4 2 5
2 4 1 5
6
3
1
For the first test case in the sample, a=2, b=4, n=3 and p=5. So s=500 and there are 6 substrings that are divided by p which are: 5, 0, 0, 50, 00, 500.
Alice and Bob love to play the following game, they have N jars and the rules are as follows:
- Each jar has a strictly positive number of candies.
- Alice plays first and the two players alternate.
- In his/her turn, the player selects any jar X, throws away all candies in all the other jars and redistributes the candies in X among all jars in anyway he/she wishes, as long as in the end there is at least one candy in each jar (including X).
- The player who cannot make a move in his/her turn loses the game.
Assuming both players play optimally, you are asked the following question who wins the game? Playing optimally means that both players will have insight into all possible next moves and will play in such a way to maximize their chance of winning without making a mistake. However, if all moves lead to the other player winning, then this player still has to play, and any move would be equivalent.
The first line contains the number of test cases T. Each of the next T lines contains an integer (2 ≤ N ≤ 1, 000) the number of jars, and N integers (1 ≤ ai ≤ 1000) where ai is the number of candies in jar i.
Output T lines, one for each test case, containing "Alice" if Alice wins the game, or "Bob" otherwise.
3
4 1 2 3 3
4 1 2 3 4
2 1 3
Bob
Alice
Bob
Another asteroid hit Mars. Fortunately, no Martians were hurt this time. Scotty, the king of Mars, decided to build force fields to protect the human colonies on Mars. As (not many) people know, building force fields costs a lot of energy, therefore he wants to minimize the total length of the force fields, can you help him?
You can imagine Mars as a 2D plane (y = 0 represents the surface of the planet) where each colony is a point with integer coordinates (xi, yi) (yes, there are flying colonies in Mars). A force field is a polyline that starts in one of the colonies and ends in another. You can build as many force fields as you want, as long as the following rules are satisfied:
- A force field must cover at least 2 colonies.
- Each colony must be covered by exactly one force field.
A colony with coordinates (x, y) is covered by a force field that starts in x1 and ends in x2 along the X axis, if x1 ≤ x ≤ x2 and y ≤ f(x) where f(x) is the y coordinate of the point of the force field polyline with X coordinate x. What is the minimum total length of force fields that is needed to cover all colonies?
The first line contains one integer T, the number of test cases. Each test case consists of two lines, the first one contains an integer n, the number of colonies ( 2 ≤ n ≤ 1,000) . The next line contains 2n space separated integers, the x and y coordinates of each colony (0 ≤ x, y ≤ 106) colonies are given in increasing order of their x coordinates. You can assume that no two colonies have the same x coordinates.
For each test case, print on a single line, a single number representing the minimum total length of force fields needed to cover all colonies, rounded to six decimal digits.
3
3
0 2 1 1 2 2
3
0 0 1 1 2 0
4
0 0 1 100 2 1 3 100
2.000000
2.828427
102.005000