GroupBlog

Problem A: Sokoban

Time Limit: 1 Sec Memory Limit: 512 MB
Submit: 17 Solved: 1
[ Submit][ Status][ Web Board]

Description

Sokoban is a very famous mini game. When Diao Fei was young, he liked to play this game very much. In the game, there is a little man who has to move many boxes to the warehouse. The game is playing in a 2D map, which consists of two types of grids: road grids and obstacle grids.

The rules to play Sokoban is showed below:

The game starts with an initial map. There will be a box or a warehouse in some road grids. And each road grid will have one box at most and one warehouse at most. The little man is in a road grid too, but this grid will not have any boxes or warehouses. Each time he can only move exactly one gird in one of four directions up, down, left and right. There are serval rules for moving:

▪If there is a road grid with no boxes in his moving direction, then he will go into the road grid.

▪If there is a road grid with a box in his moving direction, and the same direction to the road grid is also a road grid and with no boxes, then he will go into the road grid in direction, and the box will also move exactly one grid in the same direction.

▪If there is an obstacle grid in his moving direction, or there is a road grid with a box in his moving direction but the same direction to the grid is an obstacle grid or a road grid with a box, then he cannot move.

You should note that the obstacle grid and the warehouse will not move whenever during the game. And what’s more, any boxes or the man cannot move outside the map.

Then the goal of this game is to move all the boxes to warehouses. Which means you should move several times to get a situation that all the road grids which has a box will also have a warehouse, and vice versa. Your task is to calculate the minimum moving times to get the goal.

Input

The first line contains an integer T(T≤15), indicating the total number of test cases.

　　In each test case, the first line contains two integers N,M(1≤N,M≤5 ) indicating the game size is N rows and Mcolumns. Then N lines followed, each line contains exactly M characters indicating the game map. The character ‘*’ means the grid is an obstacle grid, other characters mean road girds. The character ‘.’ means the grid has nothing; The character ‘b’ means the grid has a box; The character ‘w’ means the grid has a warehouse; The character ‘+’ means the grid has both a box and a warehouse. The character ‘m’ means the little man when starting the game.

　　We promise that the number of boxes is equal to the number of warehouses, and it is no more than 8.

Output

For each test case, output the answer in one line. If the goal cannot be got, output -1.

Sample Input

3
3 3
w*w
b.b
.m.
3 5
++*++
+*m*+
++*++
1 3
bmw

Sample Output

6
0
-1

HINT

Problem B: A Hard Math Problem

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 280 Solved: 1
[ Submit][ Status][ Web Board]

Description

　　Giving two digits x,y and a positive integer k, does there exists any positive integer N which has exactly kdigits, consists of only two digits x,y and can be divided by 2k?

Input

　　The first line contains an integer T , indicating the total number of test cases. In Each test case, there is only one line contains three positive integers x,y(1≤x,y≤9) and k(1≤k≤50) as mentioned above. You can assume that x≠y.

Output

　　For each test case, output the answer in one line. If there are more than one answers, just output the minimum one. If there are no answers, output “Diao Ze MDZZ”(without quotes).

Sample Input

Sample Output

76
44
Diao Ze MDZZ

HINT

For the first test case, a 2-digit number which consists of digits 6, 7 and can divided by 22 is only 76.

For the second test case, 44, 48, 84, 88 are all the answers. But the minimum answer is 44.

For the third test case, 11, 13, 31, 33 all cannot divided by 21. So there are no answers.

[ Submit][ Status]

Problem C: The Same Color

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 989 Solved: 595
[ Submit][ Status][ Web Board]

Description

Diao Yang has many balls with different colors. Today he wants to divide his balls into two groups. But he does not know how to divide. Then Diao Ze gives him a suggestion: first you choose a ball and put it into the first group. Then from the second ball, if the color of the ball is same to the last ball you has chosen, then you put the ball into the other group. Otherwise you put the ball into the same group with the last ball. Diao Yang thinks it is OK.

Then the problem is, Diao Yang wants to know the product of the number of two groups’ balls. Can you help him?

Input

The first line contains an integer T, indicating the number of test cases.

In each test case, there are several lines, each line contains only one string with lowercas, indicating the color of the ball Diao Yang has chosen currently. Diao Yang will stop choosing when the string is equal to “END”. Note that the string “END” does not mean a color.

You can assume that there are at most 100 lines in each test case and each string has at most 10 letters.

Output

For each test case, output the answer in a line.

Sample Input

3
yellow
yellow
pink
red
red
green
END
blue
black
purple
purple
END
rose
orange
brown
white
END

Sample Output

9
3
0

HINT

In the first test case, the color of the first group’s balls are yellow, red, green, 3 balls in total. The color of the second group’s balls are yellow, pink, red, 3 balls in total too. So the product is 3×3=9.

In the second test case, the answer is 3×1=3 and in the third test case the answer is 4×0=0.

[ Submit][ Status]

Problem D: Robbing Red Packets

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 212 Solved: 2
[ Submit][ Status][ Web Board]

Description

Robbing red packets in mobile QQ is more and more popular. Diao Fei joins in many QQ groups, and likes to rob red packets very much.

Because of his fast hand speed, he can rob many red packets. But soon he noted that sometimes even if he robs the red packet earlier, he still gets little money. This makes him very unhappy. He thinks the reason is the rule for robbing red packets is unfair and he says the correct rule should be as follow:

Assume there is a red packet which will be distributed to N persons and the red packet has M yuan. To simplify the problem, we assume the smallest unit of each person’s amount of money is 1 yuan. Every person will get at least 1 yuan. So it is obviously that N should not be larger than M. When a person has robbed the red packet, the next person’s money should be randomly by system again. That is to say, if there are N persons robbing the red packet, the system will distribute randomly for N-1 times exactly. Diao Fei thinks this is very fair to the person who robs the red packet earlier. Now Diao Fei wants to know, in Diao Fei’s rule, what is the expectation of the money of the person to rob the red packet?

As Diao Fei is too lazy, he wants you to help him solve this problem.

Input

The first line contains an integer T(T≤50 ), indicating the total number of test cases. Each test case is a line with three integers N,M,K(1≤K≤N≤50, M≤500).

Output

For each test case, output the answer in one line. The answer should be rounded to 6 digits after decimal point.

Sample Input

Sample Output

1.500000
1.500000
1.039062

HINT

In the first test case, the first person has probability 1/2 to get 1 yuan or 2 yuan. So the expectation is 1/2×1+1/2×2=1.5

In the second test case, the expectation of the money of the first person is 1/3×1+1/3×2+1/3×3=2. If the first person get 1 yuan, then the second person has probability 1/3 to get 1 yuan or 2 yuan or 3 yuan. But if the first person get 2 yuan, then the second person only has probability 1/2 to get 1 yuan or 2 yuan. And if the first person get 3 yuan, then the second person can only get 1 yuan for full probability. So the expectation of the money of the second person is 1/3×(1/3×1+1/3×2+1/3×3)+1/3×(1/2×1+1/2×2)+1/3×1=1.5

[ Submit][ Status]

Problem E: Refraction

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 15 Solved: 3
[ Submit][ Status][ Web Board]

Description

As is known to all, when a light going from the air to a medium, the light will refract, and vice versa. In physics, we define the normal line as which is vertical to the dividing line of the air and the medium. The incident angle α1 is the angle between the normal line and the incident light and the refractive angle α2 is the angle between the normal line and the refractive light. The medium has a refractive index of value n. if the light goes from the air to the medium, the formula is , and if the light goes from the medium to the air, the formula will be . Note that even the incident angle is 90。, the refraction will still happen. You may get more information in the picture below:

Then in this problem the situation is not so easy. Consider a 2D plane full with air, and there is a circular medium, its center is x,y and its radius is r. Then there is a light going from the point P(xP,yP) to the original point O(0,0). Of course, if the light pass through the medium, it will be refracted. What’s more, the dividing line will be the tangent line of the circle which pass through the incident point. Then your task is to calculate the x-coordinate of the intersection point of the x axis and the light after all the refractions.

Input

The first line contains an integer , indicating the number of the test cases.

In each test case, there is only one line contains a float number n(n＞1) indicating the refractive index and 5 integers x,y,r,xP,yP, indicating the circular medium’s center is (x,y) and its radius is r, and the light is going from the point P(xP,yP). All the integers are in the range[-200, 200] and r is positive. And you can assume that the point P(xP,yP) is strictly outside the circular medium and is different with the original point O.

Output

For each test case, output the answer in one line. The answer should be rounded to 4 digits after decimal point. If after all the refractions the light will not be intersected with the x axis, output “bad light”(without quotes). If after all the refractions the light will be intersected with the x axis at infinite points, output “infinite”(without quotes).

Sample Input

6
1.6 8 0 5 -4 -3
1.2345 3 4 2 6 8
1.2345 0 0 1 0 2
1.2345 0 0 1 2 0
1.2345 3 -4 2 -1 -1

Sample Output

16.0000
0.0000
bad light
infinite
0.0000

HINT

Problem F: LCS

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 154 Solved: 28
[ Submit][ Status][ Web Board]

Description

Giving two strings consists of only lowercase letters, find the LCS(Longest Common Subsequence) whose all partition are not less than k in length.

Input

There are multiple test cases. In each test case, each of the first two lines is a string(length is less than 2100). The third line is a positive integer k. The input will end by EOF.

Output

For each test case, output the length of the two strings’ LCS.

Sample Input

abxccdef
abcxcdef
3
abccdef
abcdef
3

Sample Output

4
6

HINT

In the first test case, the answer is:

abxccdef

abcxcdef

The length is 4.

In the second test case, the answer is:

abccdef

abc def

The length is 6

[ Submit][ Status]

Problem G: Array C

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 521 Solved: 87
[ Submit][ Status][ Web Board]

Description

Giving two integers and and two arrays and both with length , you should construct an array also with length which satisfied:

1.0≤Ci≤Ai(1≤i≤n)

and make the value S be minimum. The value S is defined as:

Input

There are multiple test cases. In each test case, the first line contains two integers n(1≤n≤1000) andm(1≤m≤100000). Then two lines followed, each line contains n integers separated by spaces, indicating the array Aand B in order. You can assume that 1≤Ai≤100 and 1≤Bi≤10000 for each i from 1 to n, and there must be at least one solution for array C. The input will end by EOF.

Output

For each test case, output the minimum value S as the answer in one line.

Sample Input

3 4 
2 3 4
1 1 1

Sample Output

HINT

In the sample, you can construct an array [1,1,2](of course [1,2,1] and [2,1,1] are also correct), and is 6.

[ Submit][ Status]

Problem H: Eat Candy

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 1331 Solved: 644
[ Submit][ Status][ Web Board]

Description

There is a box with infinite volume. At first there are n candies in the box. Then every second you will eat some candies, left half of candies (round down) in the box. Then add k candies into the box. How many candies there are in the box after 109+7 seconds?

Input

There are multiple test cases. In each test case, there are only one line contains two integers n,k(1≤n,k≤109+7)

Output

For each test case, output the answer in one line.

Sample Input

4 5
2 3

Sample Output

9
5

HINT

In the first test case:

1st second, 4->2, 2+5 = 7

2nd second, 7->3, 3+5 = 8

3rd second, 8->4, 4+5 = 9

4th second, 9->4, 4+5 = 9

…

1000000007th 9

So there are 9 candies in the box after 1000000007 seconds.

[ Submit][ Status]

Problem I: Catching Dogs

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 1109 Solved: 288
[ Submit][ Status][ Web Board]

Description

Diao Yang keeps many dogs. But today his dogs all run away. Diao Yang has to catch them. To simplify the problem, we assume Diao Yang and all the dogs are on a number axis. The dogs are numbered from 1 to n. At first Diao Yang is on the original point and his speed is v. The ith dog is on the point ai and its speed is vi . Diao Yang will catch the dog by the order of their numbers. Which means only if Diao Yang has caught the ith dog, he can start to catch the (i+1)th dog, and immediately. Note that When Diao Yang catching a dog, he will run toward the dog and he will never stop or change his direction until he has caught the dog. Now Diao Yang wants to know how long it takes for him to catch all the dogs.

Input

There are multiple test cases. In each test case, the first line contains two positive integers n(n≤10) andv(1≤v≤10). Then n lines followed, each line contains two integers ai(|ai|≤50) and vi(|vi|≤5). vi＜0 means the dog runs toward left and vi＞0 means the dog runs toward right. The input will end by EOF.

Output

For each test case, output the answer. The answer should be rounded to 2 digits after decimal point. If Diao Yang cannot catch all the dogs, output “Bad Dog”(without quotes).

Sample Input

Sample Output

6.00
0.25
0.00
Bad Dog

HINT

Problem J: Arithmetic Sequence

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 1771 Solved: 299
[ Submit][ Status][ Web Board]

Description

Giving a number sequence A with length n, you should choosing m numbers from A(ignore the order) which can form an arithmetic sequence and make m as large as possible.

Input

There are multiple test cases. In each test case, the first line contains a positive integer n. The second line contains n integers separated by spaces, indicating the number sequence A. All the integers are positive and not more than 2000. The input will end by EOF.

Output

For each test case, output the maximum as the answer in one line.

Sample Input

5
1 3 5 7 10
8
4 2 7 11 3 1 9 5

Sample Output

4
6

HINT

In the first test case, you should choose 1,3,5,7 to form the arithmetic sequence and its length is 4.

In the second test case, you should choose 1,3,5,7,9,11 and the length is 6.

[ Submit][ Status]

Problem E: Refraction

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 15 Solved: 3
[ Submit][ Status][ Web Board]

Description

Input

The first line contains an integer , indicating the number of the test cases.

Output

Sample Input

6
1.6 8 0 5 -4 -3
1.2345 3 4 2 6 8
1.2345 0 0 1 0 2
1.2345 0 0 1 2 0
1.2345 3 -4 2 -1 -1

Sample Output

16.0000
0.0000
bad light
infinite
0.0000