Faheem and Faheema love to play what they call the game of Osho, in this game they choose a number N randomly, the first player subtracts a non-zero number Bk1 less than or equal to N from N, then the second player subtracts number Bk2 (where B is given and ki is a non negative integer number), then again the first and so on until one of the players loses when he/she can't make any move. In other words, when it's a player's turn and N equals 0. For example let's see this game when B=2 and N=3. The first player Faheem can subtract 1 or 2 the optimal move here is 1, N now equals 2. In her turn Faheema subtract 2 because 1 will make Faheem win, Faheem now can't play any move and he loses.
After a while they found that this game is boring so they decided to upgrade it, their version combines multiple subgames of the form (Bi, Ni) and the player can choose which of them he wants to play his move in, a player loses when he/she can't make a move.
Given the subgames, your job is to determine which player wins the whole game assuming that both players play optimally.
The first line contains T, the number of test cases. The next T lines contain G (1 ≤ G ≤ 100) the number of subgames and then follows G pairs of integers (1 ≤ Bi, Ni ≤ 1, 000, 000, 000) describing each subgame.
For each test case print 1 if the first player wins the game, or 2 if the second wins.
3
1 2 3
1 7 3
2 6 11 3 2
2
1
2
As everyone knows. The last ACM-ICPC was in Phuket, Thailand. One thing about Phuket is that it has a very hot weather. So walking in the sunlight is a harder task than you might think!
Joud was walking in one of the famous markets of the city. One street was full of flower shops. Joud hates flowers, so he decided to go through this street while walking the minimum distance possible in sunlight.
Fortunately, some of the shops have big umbrellas placed in front of them, forming rectangular shadow spots.
Given the positions of these spots. What's the minimum distance that Joud has to walk in the sunlight in order to get to the end of the street?
Note that the street is a rectangular shape and Joud can start from any point at the start line and wants to reach any point at the end line of the street.
The first line of the input will contain T the number of test cases.
Each test case starts with three integers on a single line (0 < N ≤ 100), the number of rectangular spots, (0 < L ≤ 109), the length of the street, (0 < U ≤ 109), the width of the street.
Then N lines follow, each describes a rectangular spot and contains four integers (0 < h ≤ 109), the height of the spot ,(0 < w ≤ 109), the width of the spot , (0 ≤ d ≤ 109), the distance between the beginning of the street and the spot , (
). If k is equal to 1 it means that the spot is sharing a side with the right side of the street, otherwise it's sharing a side with the left side of the street. It's guaranteed that there is no overlapping between spots, but they might touch. See the figure below.
For each test case print one number rounded to exactly 6 places after the decimal point. The solution to the problem above.
2
1 200 100
10 50 50 0
4 200 100
20 10 10 1
80 20 20 0
20 90 120 0
30 8 150 1
190.000000
70.198039
The next figure shows a possible solution for the second sample.
The Wall is a colossal defence along the northern border of the seven kingdoms, defending the realm from the wildlings who live beyond. It is defended and held by the Sworn Brothers of the Night's Watch, and since the white walkers did not return for the past eight thousand years, the Night's Watch has mostly shifted its focus to preventing the wildlings from crossing south of the Wall. They divided it into security squarcs (a squarc is half arc half a square shape), namely into N by M squarcs, and employed two types of defences:
- N Barrels filled with burning oil or ice and stone to drop on attackers along the Y axis.
- M Pendulums suspended from a pivot in the horizontal centre of the wall on multiple heights, the first on zero the second on one and so on, in a way that they can swing along the X axis with a radius equals half of N in an arc-like way with tremendous force, brutally mauling anyone within its swinging one unit height arc.
These two types of defences are fixed and assigned to each squarc in order to defend it.
You are given a set of points representing the coordinates of the wildlings who are climbing the wall, no point lays outside or on the borders of any squarc, what is the minimum number of defences that you have to use in order to stop the wildlings and defend the seven kingdoms.
The first line contains one integer T, the number of test cases. Each test case starts with a single line containing three integers: ( 1 ≤ N ≤ 100) , ( 1 ≤ M ≤ 100), the number of squarcs along the x and the y axes and ( 1 ≤ P ≤ 10, 000), The next P lines each of which consists of two real numbers ( 0 < x < N), ( 0 < y < M + N / 2) describing the coordinates of the wildling.
For each test case, print on a single line, a single number representing the minimum number of defences that you have to use in order to stop the wildlings.
1
4 4 9
3.1 1.9
0.4 1.4
1.4 2.6
3.2 2.2
2.2 5.6
2.7 4.3
1.2 4.0
1.2 4.5
2.8 3.6
3
Maram and Marwa are an example of good friends. They know each other since they were in the kindergarten. One day, they went together to the movies after they bought two tickets for the famous movie "Avatar".
Since the movie is very exciting, the girls decided to get some Popcorn so they can enjoy the movie as much as possible. Unfortunately, There was only one packet left at the Popcorn corner at the theater. So Maram immediately ran and bought the packet before Marwa!
When the movie began, Maram started eating the Popcorn while Marwa sat and watched the movie sadly. So Maram decided to give Marwa some of her Popcorn. To be exact, she decided to give Marwa an amount of Popcorn as much as Marwa can carry in one hand.
Marwa knows that she can carry only M pieces in her hand, she is wondering, in how many ways can she pick the Popcorn pieces (all Popcorn pieces are unique). Can you help her?
The first line of the input contains T the number of the test cases. Each test is represented with two integers on a single line. ( 0 < N ≤ 20 ) the number of the Popcorn pieces in the packet, ( 0 < M ≤ N ) the number of pieces Marwa can carry in one hand.
For each test case print one line, the answer to Marwa's question.
2
5 3
4 2
10
6
Shopping with the wife is one of men's hardest marriage responsibilities. Nour is a good husband. So he goes out with his wife every Friday to "Damasquino" mall.
Damasquino is a very famous mall in Damascus. It has a very unique transportation method between shops. Since the shops in the mall are laying in a straight line, you can jump on a very advanced trampoline from the shop i, and land in shop (i + di) or (i - di) depending on the direction of the jump. Where di is a constant given for each shop. You can jump forward or backward only, and you can't land any where before the first shop or after the last shop in the mall.
There are N shops in the mall, numbered from 1 to N. Nour's wife starts her shopping journey from shop 1 and ends it in shop N. Unfortunately, Nour sometimes gets lost from his wife (the mall is very crowded on Fridays). So he wants to know for each shop, what is the minimum number of trampoline jumps he has to make in order to reach shop N and see his wife again!
The first line consists of one integer T, the number of test cases.
Each test case consists of two lines, the first line contains a single integer (2 ≤ N ≤ 105) the number of shops in the mall. The second line contains N integers. Where the ith integer (1 ≤ di ≤ N) is the constant described above for the ith shop.
For each test case, print N lines. The ith line should contain one integer, the minimum number of jumps needed to be made in order to reach shop N starting from shop i, or - 1 if it is impossible.
2
5
1 1 1 1 1
5
2 2 2 2 2
4
3
2
1
0
2
-1
1
-1
0
Large I/O files. Please consider using fast input/output methods.
Chessforces is coming into a great war. The Knights Alliance is aiming to attack the Bishops Alliance land, it is up to you to help bishops defending their homeland.
In order to defeat the attacking knights, bishops want to make their defense line as big as possible. Defense line is a set of bishops on the chessboard where each pair of bishops in this set satisfies OK relation. OK relation between bishop i and bishop j is satisfied if they are on the same diagonal and the number of squares on the diagonal path between i and j is at least equal to pi2 + pj2 + C, where pk is privacy distance for bishop k and it is given for each bishop on the board, C is a given constant. Note that the path between two bishops includes both bishops squares.
Given the coordinates of each bishop on the chessboard, help them to find the defense line with maximum number of bishops.
First line contains number of test cases T. Each test case contains one line with (0 < n ≤ 105) size of the chessboard edge, (0 < m ≤ 105) number of bishops and the constant (0 ≤ C ≤ 105) then m line follows, the ith line of them contains three integers: (1 ≤ ri, ci, pi ≤ n) where (ri,ci) is row number and column number of the ith bishop and pi is the privacy of the ith bishop.
Print a single integer, the size of the defense line with maximum number of bishops.
1
8 5 2
7 7 1
4 4 1
3 5 1
2 6 2
4 8 1
2
Large I/O files. Please consider using fast input/output methods.
First test case explanation, columns go from left to right and rows go up to bottom, bishops labeled with borders are included in the defense line.
Altanie is a very large and strange country in Mars. People of Mars ages a lot. Some of them live for thousands of centuries!
Your old friend Foki "The president of the Martian United States of Altanie" is the oldest man on Mars. He's very old no one knows how old he is! Foki loves children, so, he had (0 < K ≤ 106) children!
The government in Altanie decided to send a team of athletes to Venus. To participate in (0 < N ≤ 103) different game in the Galactic Olympics. So Foki told them to send his children instead!
Foki is in a big problem. How can he decide whom of his children is going to participate in which game, at the same time his children must participate in all the games and every one of his children get to participate in at least one game?
Note that in a certain arrangement, each one of Foki's children can participate in multiple games in the Olympics, but each game must be arranged to exactly one player.
Your job is to help Foki and answer his question: in how many way can he arrange his children to the games in Venus Olympics while satisfying the previous two conditions.
The first line of the input contains T the number of the test cases. Each test is represented with two integers on a single line. ( 0 < N ≤ 103 ) the number of the games in the Olympics, ( 0 < K ≤ 106 ) the number of Foki's children.
For each test case print one line contains the answer to Foki's question. Since the answer is very large. Print the answer modulo 109 + 7
1
3 2
6
A commando is a soldier of an elite light infantry often specializing in amphibious landings, abseiling or parachuting. This time our Commando unit wants to free as many hostages as it could from a hotel in Byteland, This hotel contains 10 identical floors numbered from 1 to 10 each one is a suite of 10 by 10 symmetric square rooms, our unit can move from a room (F, Y, X) to the room right next to it (F, Y, X + 1) or front next to it (F, Y + 1, X) and it can also use the cooling system to move to the room underneath it (F - 1, Y, X).
Knowing that our unit parachuted successfully in room 1-1 in floor 10 with a map of hostages locations try to calculate the maximum possible hostages they could save.
Your program will be tested on one or more test cases. The first line of the input will be a single integer T. Followed by the test cases, each test case contains a number N (1 ≤ N ≤ 1, 000) representing the number of lines that follows. Each line contains 4 space separated integers (1 ≤ F, Y, X, H ≤ 10) means in the floor number F room Y-X there are H hostages.
For each test case, print on a single line, a single number representing the maximum possible hostages that they could save.
2
3
10 5 5 1
10 5 9 5
10 9 5 9
3
1 5 5 1
5 5 9 5
5 9 5 8
10
8
Engineers around the world share a lot of common characteristics. For example, they're all smart, cool and extremely lazy!
Asem is a computer engineer, so he is very lazy. He doesn't leave the house for weeks. Not even for a shisha with his best friends.
One day his mother insisted that he goes to the park to get some fresh air. Asem is a lazy but a very practical person. He decided to use the time spent on the way to the park to test his new device for detecting wireless networks in the city. The device is as much advanced as it's weird. It detects a network if the coverage area of the network is entirely inside the coverage area of the device. Both the coverage area of the wireless networks and Asem's device are circular shaped.
The path between Asem's house and the park is a straight line and when Asem turn on the device, it display one integer on its screen, the sum of the radiuses of the detected networks.
Given the coordinates of the center of the networks coverage area and their radiuses, what is the maximum number that could be displayed on the screen knowing that Asem can test the device anywhere in the street?
The first line of the input will contain T the number of test cases.
Each test case starts with two integers on a single line (0 < N ≤ 105), the number of wireless networks, (0 < M ≤ 109), the radius of the coverage area of Asem's device.
Then N lines follow, each describes a wireless network and contains three integers ( - 109 ≤ xi ≤ 109), the X coordinate of the center of the i'th network coverage area,( - 109 ≤ y ≤ 109), the Y coordinate of the center of the i'th network coverage area, (1 ≤ ri ≤ 109), the radius of the i'th network coverage area. Where the street is the X-axis here and Asem can test the device anywhere on it.
For each test case print one integer. The maximum number that could be displayed on the screen.
2
3 5
0 0 1
4 0 2
10 0 1
4 3
0 1 1
0 -3 1
10 1 1
0 -4 2
3
1
Large I/O files. Please consider using fast input/output methods.
The figure shows a possible solution for the first sample.
Whistle has bought a new car, which has an infinite fuel tank capacity.
He discovered an irregular country since it has n cities and there are exactly n - 1 roads between them, of course, all cities are connected. He is so much clever, he realized that the country is like a rooted tree of n nodes and node 1 is the root. Each city i has only one filling station by which he can fill his car's fuel tank in no more than Xi liter. Whistle liked the country very much, and he wants to know what the most attractive city in the country is. The attractiveness of the city i is defined by how much it’s reachable from other cities, in other words the attractiveness of city is the number of cities j that satisfies these condition:
- City j is in the subtree of city i (except for city i itself).
- Whistle will start at city j and will only fill his car’s fuel tank with Xj liters and never fill it again until he reach city i.
- Whistle should be able to reach city i with non-negative fuel.
He knows the length of every road and that 1 Km will take exactly 1 liter on any road.
As you know, Whistle is very clever, but he is not that good at programming, so he asked you to help him. He wants to know the attractiveness of each city, so that he can decide which city to live in.
The first line of input contains one integer T, the number of test cases.
The next line contains one integer (1 ≤ n ≤ 500, 000), The number of cities in the country.
The next line contains n integers (1 ≤ Xi ≤ 1, 000, 000, 000).
Each one of the next n - 1 line contains three integers A, B, C (1 ≤ A, B ≤ n and 1 ≤ C ≤ 1, 000, 000, 000), that means there is a road between city A and city B of length C.
For each test case, output a line containing n integers, the attractiveness of each city.
1
4
5 10 5 10
1 2 100
2 3 5
3 4 5
0 2 1 0
Large I/O files. Please consider using fast input/output methods.
Johnny got tired of math and came to Egypt to do some tourism. He has a list of Egyptian cities, numbered from 0 to N - 1. He starts his visit in Cairo (Cairo has number 0). Then he will choose the next city to visit at random from the list, say Alexandria, and then, after visiting Alexandria, he will randomly decide the next city to visit, maybe Giza, etc.
Although his decision is made at random, he is not equally likely to choose any city. More precisely, if he is currently in city number i, he will choose city number j as the next city to visit with probability P[i, j], where P is an NxN matrix of real numbers.
Also, all over Egypt, only M types of possible postcards are sold: Views of the Pyramids are one type, Alexandria beach landscapes another type, etc. The postcard types are numbered from 0 to M - 1. Whenever Johnny reaches a city, he sends a postcard to his parents, that he chooses at random among the M types of postcards. However, not all postcards have an equal chance to be chosen.
When Johnny reaches city number r, he will choose postcard type number s with probability C[r, s] where C is an NxM matrix. (For example, if he is in Giza, he's more likely to send a postcard with a view of the Pyramids).
During his stay in Egypt, Johnny will travel from city to city exactly K - 1 times, and hence he will send exactly K postcards. Please note that it is possible that he visits the same city twice: For instance, he may visit Cairo, then Alexandria, then Giza, then Alexandria again. However, he won't go back to the same city immediately after visiting it (in other words, P[i, i] = 0 for all i).
You can assume that any decision Johnny takes about which city to visit next or what postcard to send depends probabilistically only on the city he is currently in.
You know the type of each of the K postcards Johnny sent, as well as the matrices P and C. You are also given an integer Q, and you are asked to determine the probability that Johnny was in city Z when he sent his Qth postcard to his parents.
The first line of the input will consist of a single integer T, the number of test cases. Each test case will consist of the following: One line containing integers N, M, K, Q, Z where 1 ≤ N ≤ 20, 1 ≤ M ≤ 10, 1 ≤ K ≤ 15, 0 ≤ Q < K, and 0 ≤ Z < N, followed by N lines containing N real space-separated values, where the jth value on the ith line represents P[i,j]. followed by another N lines containing M real space-separated values, where the jth value on the ith line represents the value C[i,j].
Then a single line will follow, containing exactly K integers, the type of the K postcards that Johnny sent to his parents during his stay in Egypt, in the same order he sent them.
For each test case, a single real value, rounded to exactly 3 places after the decimal point, representing the probability that Johnny was in city Z just after he sent Q postcards to his parents.
1
3 3 3 2 1
0.00 0.75 0.25
0.10 0.00 0.9
0.1 0.9 0.00
0.2 0.3 0.5
0.1 0.01 0.89
0.2 0.3 0.5
0 1 2
0.889
The elements of arrays P and C are double values and contains no more than four places after the decimal point.