Description

Mirko and Slavko have built a grand new pool in front of their weekend getaway.
The pool is an isosceles right triangle, with legs of length 250.

Everything was perfect, girls were coming, the DJ was coming, and the parties were wild.
But, a problem arose when they started serving food at the parties. Mirko is vegetarian, while Slavko thinks a party without sausages is no party at all. Therefore they had to divide the pool into two parts.
The pool is placed into a coordinate system (as in the figure above) and divided into two parts of equal area by a line segment with both endpoints on the edges of the pool.
Write a program that, given one endpoint of the dividing line segment, calculates the coordinates of the other endpoint.

Input

Each case contains two integers, the coordinates of one endpoint of the dividing line segment.
That point will be on one of the edges of the pool.

Output

Output the coordinates of the other endpoint, rounded to two decimal digits.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Last week Mister George visited Croatia. Since Mister George is a very important person, while he was in a street, the police disallowed entry to that street, but vehicles that entered the street before Mister George could continue driving.
While Mister George was visiting, Luka drove his truck around town. But because of some of the streets being closed off, he couldn't make his delivery in time and almost lost his job. Although it is late  now, he is wondering how he could have planned his delivery better i.e. what would have been the least time needed to make his delivery while Mister George was visiting. He knows the route mister George took.
The city is modeled with intersections and two-way streets connecting them. For each street, Luka knows how much time he needs to traverse it (mister George needs the same amount of time).
For example, if Mister George starts traversing a street during minute 10 and needs 5 minutes to exit it, this street will be blocked during minutes 10, 11, 12, 13 and 14. Luka can enter the street during minutes 9 and earlier, or 15 and later.
Write a program that calculates the least amount of time Luka needs to make his delivery, if he starts driving K minutes after the arrival of Mister George .

Input

For each case,the first line contains two integers N and M (2 ≤ N ≤ 1000, 2 ≤ M ≤ 10 000), the number of intersections and the number of streets. The intersections are numbered 1 to N.
The second line contains four integers A, B, K and G (1 ≤ A, B ≤ N, 0 ≤ K ≤ 1000, 0 ≤ G ≤ 1000).
These are, in order:
· The intersection where Luka starts;
· The intersection Luka must get to;
· The difference in starting times between mister George and Luka (Luka starts at intersection A exactly K minutes after mister George starts his route);
· The number of intersections on Mister George's route.
The third line contains G integers, the labels of intersections mister George will visit. Every pair of adjacent integers denotes a street he will traverse. That street will exist and Mister George will traverse every street at most once.
Each of the following M lines contains three integers A, B and L, meaning that there is a street between intersection A and B, and it takes L minutes to traverse. L will be between 1 and 1000.

Output

Output the least amount of time (in minutes) Luka needs to make his delivery.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In the nearby kindergarten they recently made up an attractive game of strength and agility that kids love.
The surface for the game is a large flat area divided into N×N squares.
The children lay large spongy cues onto the surface. The sides of the cubes are the same length as the sides of the squares. When a cube is put on the surface, its sides are aligned with some square. A cube may be put on another cube too.
Kids enjoy building forts and hiding them, but they always leave behind a huge mess. Because of this, prior to closing the kindergarten, the teachers rearrange all the cubes so that they occupy a rectangle on the surface, with exactly one cube on every square in the rectangle.
In one moving, a cube is taken off the top of a square to the top of any other square.
Write a program that, given the state of the surface, calculates the smallest number of moves needed to arrange all cubes into a rectangle.

Input

The first line contains the integers N and M (1 ≤ N ≤ 100, 1 ≤ M ≤ N2), the dimensions of the surface and the number of cubes currently on the surface.
Each of the following M lines contains two integers R and C (1 ≤ R, C ≤ N), the coordinates of the square that contains the cube.

Output

Output the smallest number of moves. A solution will always exist.

In the first example, it suffices to move one of the cubes from (1, 1) to (1, 2) or (2, 1).
In the third example, a cube is moved from (2, 3) to (3, 3), from (4, 2) to (2, 5) and from (4, 4) to (3, 5).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a list of rectangles and a list of points in the x-y plane, determine for each point which figures (if any) contain the point.

Input

There will be n( <=10) rectangles descriptions, one per line. The first character will designate the type of figure (``r'' for rectangle). This character will be followed by four real values designating the x-y coordinates of the upper left and lower right corners.

The end of the list will be signalled by a line containing an asterisk in column one.

The remaining lines will contain the x-y coordinates, one per line, of the points to be tested. The end of this list will be indicated by a point with coordinates 9999.9 9999.9; these values should not be included in the output.

Points coinciding with a figure border are not considered inside.

Output

For each point to be tested, write a message of the form:

Point i is contained in figure j
for each figure that contains that point. If the point is not contained in any figure, write a message of the form:
Point i is not contained in any figure
Points and figures should be numbered in the order in which they appear in the input.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A popular card game called ``fortune" is getting popular in country X. Fig. 1 shows one of the cards. In each card, a positive integer number (20 in the figure) is listed as the address of the card. A symbol is drawn beside the address. There are five kinds of symbols, which are listed below the card. For convenience, let each symbol be represented by an English letter from `A'-`E'. The bottom of a card contains another number called ``next fortune number."

Figure 1: A sample fortune card and symbols.
In a set of fortune cards, many cards can have same address; that is, address 20 is not limited to appear only in one card. However, there will be no cards that are identical, i.e., no two cards with same address, symbol, and next fortune number.

The fortune card game is played as follows. A player starts with cards that have address 1. The goal of the game is trying to complete a ``spell" that is composed by the symbols. For example, let a spell be ``BADDAD". In the first move, the player will look for cards that have address 1 with a star symbol (which matches `B' in the spell). The next fortune numbers of these cards are the new addresses for the next move. The player can select one card to advance to a new address x. The selected card is then put back to the cards for next move but the fortune number is written down.

Let the example be continued. In the next move, the player needs to look for the cards that have new address x with the cross symbol (which matches the second `A' in the spell). Again, the player selects one card to advance to another new address. This procedure continues until the spell ``BADDAD" is completed. Once the player completes a spell, he wins a score by adding all the next fortune numbers of the selected card, which have been written down.

Given a spell and a set of fortune cards, please output the maximum score that can be played in this card game.


Technical Specification


N - the number of test cases, N10 .
C - the number of cards, C800 .
L - the length of a spell, L150 .

Input

Test data begins with an integer N which is the number of test cases. Each test case begins with an integer C , which is the number of cards. Following the number C is C lines of card information. Each card is represented by (Address Symbol NextF ortuneNumber). The address and next fortune number are between 1 and 800. The symbols are capital letters from `A' to `E'. The last line of a test case is a spell. The spell is a string composed by capital letters from `A' to `E'. The length of the spell (L ) is less than 150.

Output

For each test case, please output the maximum score that can be collected for each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are going on a long trip. Initially, you stay at hotel 0. Along the way, there are n hotels. The only place you are allowed to stop are at these hotels. The distance from hotel i - 1 to hotel i is ai . You can choose which of the hotels you stop at. You must stop at the final hotel, which is your destination.

You would ideally like to travel 100 kilometers a day. However, this may not be possible. It depends on the spacing of the hotels. There is no limit on the distance you traveled in a day. If you travel x kilometers during a day, the penalty for that day is (x - 100)2 . You want to plan your trip so as to minimize the total penalty -- that is, the sum, over all travel days, of the daily penalty. Write a program to determine the optimal sequence of hotels at which to stop.

Input

The input file contains a set of test data. Each test data consists of two parts. The first part is the number of hotels n . The second part is a sequence of n integers a1, a2,..., an . Each ai is the distance between hotel i - 1 and hotel i . Assume that 0 < ai < 200 . They may be written in many lines. Assume that n < 1000 , and n = 0 signals the end of the test data.

Output

The first line of the output is the minimum penalty p . The second line of the output is the indexes of the hotels to stop at. If the solution is not unique, print the one with fewer stops. If there are more then one solutions with the same number of stops, print the one which is the lexicographically smallest one. For example (1 2 4) < (1 3 4) . Print 30 stops in each line, except the last line which may contain less stops. Print a blank line between datasets.

Sample Input  Download

Sample Output  Download

Tags

Discuss