Description

You must have heard of the Knight's Tour problem. In that problem, a knight is placed on an empty chess board and you are to determine whether it can visit each square on the board exactly once.

Let's consider a variation of the knight's tour problem. In this problem, a knight is place on an infinite plane and it's restricted to make certain moves. For example, it may be placed at (0, 0) and can make two kinds of moves: Denote its current place as (x,y), it can only move to (x+1,y+2) or (x+2,y+1). The goal of this problem is to make the knight reach a destination position as quickly as possible (i.e. make as less moves as possible).

Input

The first line contains an integer T ( T < 20) indicating the number of test cases.

Each test case begins with a line containing four integer: fx fy tx ty(-5000<=fx,fy,tx,ty<=5000). The knight is originally placed at (fx, fy) and (tx, ty) is its destination.

The following line contains an integer m(0
Each of the following m lines contains two integer mx my(-10<=mx,my<=10; |mx|+|my|>0), which means that if a knight stands at (x,y), it can move to (x+mx,y+my).

Output

Output one line for each test case. It contains an integer indicating the least number of moves needed for the knight to reach its destination. Output "IMPOSSIBLE" if the knight may never gets to its target position.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You may not hear about Nubulsa, an island country on the Pacific Ocean. Nubulsa is an undeveloped country and it is threatened by the rising of sea level. Scientists predict that Nubulsa will disappear by the year of 2012. Nubulsa government wants to host the 2011 Expo in their country so that even in the future, all the people in the world will remember that there was a country named “Nubulsa”.

As you know, the Expo garden is made up of many museums of different countries. In the Expo garden, there are a lot of bi-directional roads connecting those museums, and all museums are directly or indirectly connected with others. Each road has a tourist capacity which means the maximum number of people who can pass the road per second.

Because Nubulsa is not a rich country and the ticket checking machine is very expensive, the government decides that there must be only one entrance and one exit. The president has already chosen a museum as the entrance of the whole Expo garden, and it’s the Expo chief directory Wuzula’s job to choose a museum as the exit.

Wuzula has been to the Shanghai Expo, and he was frightened by the tremendous “people mountain people sea” there. He wants to control the number of people in his Expo garden. So Wuzula wants to find a suitable museum as the exit so that the “max tourists flow” of the Expo garden is the minimum. If the “max tourist flow” is W, it means that when the Expo garden comes to “stable status”, the number of tourists who enter the entrance per second is at most W. When the Expo garden is in “stable status”, it means that the number of people in the Expo garden remains unchanged.

Because there are only some posters in every museum, so Wuzula assume that all tourists just keep walking and even when they come to a museum, they just walk through, never stay.

Input

There are several test cases, and the input ends with a line of “0 0 0”.

For each test case:

The first line contains three integers N, M and S, representing the number of the museums, the number of roads and the No. of the museum which is chosen as the entrance (all museums are numbered from 1 to N). For example, 5 5 1 means that there are 5 museums and 5 roads connecting them, and the No. 1 museum is the entrance.

The next M lines describe the roads. Each line contains three integers X, Y and K, representing the road connects museum X with museum Y directly and its tourist capacity is K.

Please note:

1

Output

For each test case, print a line with only an integer W, representing the “max tourist flow” of the Expo garden if Wuzula makes the right choice.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

On the planet Pandora, huge rocks are floating in the sky. Despite the beautiful scenery, these rocks bring some critical problem: they block the sunshine, and shade on the ground. Na'vi ("people" living on the planet) cannot grow plants in the shade because of the lack of sunshine. In order to predicate the amount of food they can get, they have to calculate the area of the shade.

Let’s assume the "sun" as a point-source of light, and the ground as a infinite flat plane. Also, to simplify this problem, assume all rocks are convex polyhedrons.

Now here is a mathematical problem. Given the position of the point-source of light, the position of a convex polyhedron and the position of an infinite plane, you are required to calculate the area of the shade. Please note that light travels in a strictly straight line and the light source and the convex polyhedron are on the same side of the plane. The light source is not placed in the convex polyhedron, nor on the polyhedron or on the plane.

Input

The input contains no more than 100 cases.

Each case contains several lines which are formatted as follows.

a b c d

n

x1 y1 z1

x2 y2 z2

......

xn yn zn

x0 y0 z0

a, b, c and d means that the plane is ax+by+cz=d. n means the number of vertex of the convex polyhedron. It is guaranteed that n is no more than 100. Following it are n lines. Each line contains three float numbers, indicating the position of a point which is a vertex of the polyhedron. The last line also contains three float numbers, which means the position of the point-source of light.

The input is ended by a=0, b=0, c=0 and d=0.

Output

For each case, if there is no shade on the plane, print “0.00”.

If the area of the shade is infinite, print “Infi”.

Otherwise, print out the area of the shade. Please round the result to two digits after the decimal point.

Hint

Here are some hints to help you implement rotation in 3-dimensional space.

Assume that there is a plane ax+by+cz=0 , and our task is to rotate the whole space so that the plane will be in the position z=0 .

As we all know, the normal vector of the plane is (a,b,c) , so after we rotate the space, the normal vector will be the z-axis. So we can only consider how to rotate the vector to the position .
We can divide the process into 2 steps. First step, rotate the normal vector to . Second step, rotate to . Then apply the two rotation steps on the whole space, we can rotate the plane to a given position.

It is easy to implement the two steps. In first step, the third number in the normal vector does not change, so this is like rotation in a 2-dimensional space. Similarly, we implement the second step.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Mr. Furion is a math teacher. His students are very lazy and they do not like to do their homework. One day, Mr. Furion decides to give them a special problem in order to see whether his students are talents in math or they are just too lazy to do their homework. The problem is:


Given an integer k, n integers m₁,m₂…m_n, and a formula below:

X₁ xor X₂ xor X₃… xor X_n = k

Please figure out that how many integral solutions of the formula can satisfy:

0<=X_i<=m_i (i=1…n)

Input

There are at most 100 test cases.

The first line of each test case contains two integers n and k. The second line of each test contains n integers: m₁,m₂…m_n. The meaning of n,k, m₁,m₂…m_n are described above. (1<=n<=50, 0<=k,m₁,m₂…m_n<=2³¹-1 )

The input is ended by “0 0”.

Output

You should output a integer for each test case, which is the number of solutions. As the number might be very large, you should only output the number modulo 1000000003.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In geometry the Fermat point of a triangle, also called Torricelli point, is a point such that the total distance from the three vertices of the triangle to the point is the minimum. It is so named because this problem is first raised by Fermat in a private letter. In the following picture, P0 is the Fermat point. You may have already known the property that:

Alice and Bob are learning geometry. Recently they are studying about the Fermat Point.

Alice: I wonder whether there is a similar point for quadrangle.

Bob: I think there must exist one.

Alice: Then how to know where it is? How to prove?

Bob: I don’t know. Wait… the point may hold the similar property as the case in triangle.

Alice: It sounds reasonable. Why not use our computer to solve the problem? Find the Fermat point, and then verify your assumption.

Bob: A good idea.

So they ask you, the best programmer, to solve it. Find the Fermat point for a quadrangle, i.e. find a point such that the total distance from the four vertices of the quadrangle to that point is the minimum.

Input

The input contains no more than 1000 test cases.

Each test case is a single line which contains eight float numbers, and it is formatted as below:

x₁ y₁ x₂ y₂ x₃ y₃ x₄ y₄

x_i, y_i are the x- and y-coordinates of the ith vertices of a quadrangle. They are float numbers and satisfy 0 ≤ x_i ≤ 1000 and 0 ≤ y_i ≤ 1000 (i = 1, …, 4).

The input is ended by eight -1.

Output

For each test case, find the Fermat point, and output the total distance from the four vertices to that point. The result should be rounded to four digits after the decimal point.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Aliens on planet Pandora also write computer programs like us. Their programs only consist of capital letters (‘A’ to ‘Z’) which they learned from the Earth. On
planet Pandora, hackers make computer virus, so they also have anti-virus software. Of course they learned virus scanning algorithm from the Earth. Every virus has a pattern string which consists of only capital letters. If a virus’s pattern string is a substring of a program, or the pattern string is a substring of the reverse of that program, they can say the program is infected by that virus. Give you a program and a list of virus pattern strings, please write a program to figure out how many viruses the program is infected by.

Input

There are multiple test cases. The first line in the input is an integer T ( T <= 10) indicating the number of test cases.

For each test case:

The first line is a integer n( 0 < n <= 250) indicating the number of virus pattern strings.

Then n lines follows, each represents a virus pattern string. Every pattern string stands for a virus. It’s guaranteed that those n pattern strings are all different so there
are n different viruses. The length of pattern string is no more than 1,000 and a pattern string at least consists of one letter.

The last line of a test case is the program. The program may be described in a compressed format. A compressed program consists of capital letters and
“compressors”. A “compressor” is in the following format:

[qx]

q is a number( 0 < q <= 5,000,000)and x is a capital letter. It means q consecutive letter xs in the original uncompressed program. For example, [6K] means
‘KKKKKK’ in the original program. So, if a compressed program is like:

AB[2D]E[7K]G

It actually is ABDDEKKKKKKKG after decompressed to original format.

The length of the program is at least 1 and at most 5,100,000, no matter in the compressed format or after it is decompressed to original format.

Output

For each test case, print an integer K in a line meaning that the program is infected by K viruses.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

“Farm Game” is one of the most popular games in online community. In the community each player has a virtual farm. The farmer can decide to plant some kinds of crops like wheat or paddy, and buy the corresponding crop seeds. After they grow up, The farmer can harvest the crops and sell them to gain virtual money. The farmer can plant advanced crops like soybean, watermelon or pumpkin, as well as fruits like lychee or mango.

Feeding animals is also allowed. The farmer can buy chicken, rabbits or cows and feeds them by specific crops or fruits. For example, chicken eat wheat. When the animals grow up, they can also “output” some products. The farmer can collect eggs and milk from hens and cows. They may be sold in a better price than the original crops.

When the farmer gets richer, manufacturing industry can be set up by starting up some machines. For example, Cheese Machine can transfer milk to cheese to get better profits and Textile Machine can spin cony hair to make sweaters. At this time, a production chain appeared in the farm.

Selling the products can get profits. Different products may have different price. After gained some products, the farmer can decide whether to sell them or use them as animal food or machine material to get advanced products with higher price.

Jack is taking part in this online community game and he wants to get as higher profits as possible. His farm has the extremely high level so that he could feed various animals and build several manufacturing lines to convert some products to other products.

In short, some kinds of products can be transformed into other kinds of products. For example, 1 pound of milk can be transformed into 0.5 pound of cheese, and 1 pound of crops can be transformed into 0.1 pound of eggs, etc. Every kind of product has a price. Now Jack tell you the amount of every kind of product he has, and the transform relationship among all kinds of products, please help Jack to figure out how much money he can make at most when he sell out all his products.

Please note that there is a transforming rule: if product A can be transformed into product B directly or indirectly, then product B can never be transformed into product A, no matter directly or indirectly.

Input

The input contains several test cases. The first line of each test case contains an integers N (N <= 10000) representing that there are N kinds of products in Jack’s farm. The product categories are numbered for 1 to N. In the following N lines, the ith line contains two real numbers p and w, meaning that the price for the ith kind of product is p per pound and Jack has w pounds of the ith kind of product.

Then there is a line containing an integer M (M <= 25000) meaning that the following M lines describes the transform relationship among all kinds of products. Each one of those M lines is in the format below:

K a₀, b₁, a₁, b₂, a₂, …, b_k-1, a_k-1

K is an integer, and 2×K-1 numbers follows K. ai is an integer representing product category number. bi is a real number meaning that 1 pound of product ai-1 can be transformed into bi pound of product ai.

The total sum of K in all M lines is less than 50000.

The input file is ended by a single line containing an integer 0.

Output

For each test case, print a line with a real number representing the maximum amount of money that Jack can get. The answer should be rounded to 2 digits after decimal point. We guarantee that the answer is less than 10¹⁰.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A new Semester is coming and students are troubling for selecting courses. Students select their course on the web course system. There are n courses, the ith course is available during the time interval (A_i,B_i). That means, if you want to select the ith course, you must select it after time Ai and before time Bi. Ai and Bi are all in minutes. A student can only try to select a course every 5 minutes, but he can start trying at any time, and try as many times as he wants. For example, if you start trying to select courses at 5 minutes 21 seconds, then you can make other tries at 10 minutes 21 seconds, 15 minutes 21 seconds,20 minutes 21 seconds… and so on. A student can’t select more than one course at the same time. It may happen that no course is available when a student is making a try to select a course

You are to find the maximum number of courses that a student can select.

Input

There are no more than 100 test cases.

The first line of each test case contains an integer N. N is the number of courses (0 < N <= 300)

Then N lines follows. Each line contains two integers Ai and Bi (0 <= A_i < B_i <= 1000), meaning that the ith course is available during the time interval (A_i,B_i).

The input ends by N = 0.

Output

For each test case output a line containing an integer indicating the maximum number of courses that a student can select.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Plain of despair was once an ancient battlefield where those brave spirits had rested in peace for thousands of years. Actually no one dare step into this sacred land until the rumor that “there is a huge gold mine underneath the plain” started to spread.

Recently an accident destroyed the eternal tranquility. Some greedy fools tried using powerful bombs to find the hidden treasure. Of course they failed and such behavior enraged those spirits--the consequence is that all the human villages nearby are haunted by ghosts.

In order to stop those ghosts as soon as possible, Panda the Archmage and Facer the great architect figure out a nice plan. Since the plain can be represented as grids of N rows and M columns, the plan is that we choose ONLY ONE cell in EACH ROW to build a magic tower so that each tower can use holy light to protect the entire ROW, and finally the whole plain can be covered and all spirits can rest in peace again. It will cost different time to build up a magic tower in different cells. The target is to minimize the total time of building all N towers, one in each row.

“Ah, we might have some difficulties.” said Panda, “In order to control the towers correctly, we must guarantee that every two towers in two consecutive rows share a common magic area.”

“What?”

“Specifically, if we build a tower in cell (i,j) and another tower in cell (i+1,k), then we shall have |j-k|≤f(i,j)+f(i+1,k). Here, f(i,j) means the scale of magic flow in cell (i,j).”

“How?”

“Ur, I forgot that you cannot sense the magic power. Here is a map which shows the scale of magic flows in each cell. And remember that the constraint holds for every two consecutive rows.”

“Understood.”

“Excellent! Let’s get started!”

Would you mind helping them?

Input

There are multiple test cases.

Each test case starts with a line containing 2 integers N and M (2 <= N <= 100,1 <= M <= 5000), representing that the plain consists N rows and M columns.

The following N lines contain M integers each, forming a matrix T of N×M. The j-th element in row i (T_ij) represents the time cost of building a magic tower in cell (i, j). (0 <= T_ij <= 100000）

The following N lines contain M integers each, forming a matrix F of N×M. The j-th element in row i (F_ij) represents the scale of magic flows in cell (i, j). (0 <= F_ij <= 100000）

For each test case, there is always a solution satisfying the constraints.

The input ends with a test case of N=0 and M=0.

Output

For each test case, output a line with a single integer, which is the minimum time cost to finish all magic towers.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Math Olympiad is called “Aoshu” in China. Aoshu is very popular in elementary schools. Nowadays, Aoshu is getting more and more difficult. Here is a classic Aoshu problem:


ABBDE __ ABCCC = BDBDE

In the equation above, a letter stands for a digit(0 – 9), and different letters stands for different digits. You can fill the blank with ‘+’, ‘-‘ , ‘×’ or ‘÷’.

How to make the equation right? Here is a solution:


12245 + 12000 = 24245

In that solution, A = 1, B = 2, C = 0, D = 4, E = 5, and ‘+’ is filled in the blank.

When I was a kid, finding a solution is OK. But now, my daughter’s teacher tells her to find all solutions. That’s terrible. I doubt whether her teacher really knows how many solutions are there. So please write a program for me to solve this kind of problems.

Input

The first line of the input is an integer T( T <= 20) indicating the number of test cases.

Each test case is a line which is in the format below:


s1 s2 s3

s1, s2 and s3 are all strings which are made up of capital letters. Those capital letters only include ‘A’,’B’,’C’,’D’ and ‘E’, so forget about ‘F’ to ‘Z’. The length of s1,s2 or s3 is no more than 8.

When you put a ‘=’ between s2 and s3, and put a operator( ‘+’,’-‘, ‘×’ or ‘÷’.) between s1 and s2, and replace every capital letter with a digit, you get a equation.

You should figure out the number of solutions making the equation right.

Please note that same letters must be replaced by same digits, and different letters must be replaced by different digits. If a number in the equation is more than one digit, it must not have leading zero.

Output

For each test case, print an integer in a line. It represents the number of solutions.

Sample Input  Download

Sample Output  Download

Tags

Discuss