Russian Code Cup 2013: analysis of the tasks of the first qualification round

Time limit - 1 second
Memory limit - 256 megabytes
Now preparations are being made for the upcoming Olympics in Gnomland. The gnome-brigadier was given the task of building fields for playing hurtball, Jordanball and Medveball. Each field is a rectangle. In accordance with the rules of the game, the fields must be located so that their sides are parallel to the north-south and west-east directions.
Land in Gnomland is very expensive, so game organizers want to spend as little money as possible on buying land. Since the Hertball, Jordanball and Medwebol competitions will be held at different times, the fields may overlap.
Help the dwarves find the minimum area that three fields can occupy after construction.
One of the possible optimal field layouts in the first example is shown in the figure.

Input format
Input data contains no more than 1000 lines, each of which contains a description of three fields - six natural numbers, each of which does not exceed 10000.
The first and second numbers indicate the sizes of the first field, the third and fourth - the sizes of the second field, fifth and the sixth is the size of the third field.
The input ends with a string of six zeros. This request does not need to be processed.
Output format
For each set, print a number - the minimum area that three fields can occupy.

Time limit - 2 seconds
Memory limit - 256 megabytes
Once, Sergey Sergeevich told students the algorithm for constructing trapezoid cards. As a warm-up, he gave them the task of trapeze. He drew n segments on the board. The length of the ith segment is ai. Students are required to find the number of different sets of four segments from which you can make an isosceles trapezoid of non-zero area.
Recall that an isosceles trapezoid is a quadrangle, the two opposite sides of which are parallel, and the other two are equal. An example of an isosceles trapezoid is shown in the figure.

Two sets are considered different if there is a segment belonging to the first set and not belonging to the second. The numbers of the taken segments in each set should be pairwise different.
Help students find the number of such sets.
Input format
The first line contains the number t - so many times Anton gave his students this task. The following 2t lines contain descriptions of all tasks.
The description of each task consists of two lines. The first line of the description contains the number n - the number of segments drawn on the board. The second line of the description of the problem gives n integers ai - their lengths (4 ≤ n ≤ 5000, 1 ≤ ai ≤ 108 for all i from 1 to n).
The total number of all segments in all tasks does not exceed 5000.
Output format
For each task in a separate line print one number - the desired number of sets.

Time limit - 2 seconds;
Memory limit - 256 megabytes.
The chemical element muran discovered in 2345 is very radioactive. Improper handling of muran can lead to unpredictable consequences, therefore, special care must be taken when using it, storing and transporting it.
There are many different isotopes of murano, each of which is characterized by one natural number - its atomic mass. During long-term storage together any pair of isotopes, the sum of the masses of which is equal to one of k “critical numbers”, this pair of isotopes reacts and an explosion occurs. It is known that all critical numbers are non-negative powers of two.
In the Flatland nuclear laboratory, samples of murano are stored in two special warehouses. Scientists managed to get n different isotopes of muran, the masses of which are numbers from 1 to n. Now you need to distribute the isotopes in the warehouses for storage. Safe methods of storage are those in which each isotope is stored in exactly one warehouse, and any two different isotopes, the sum of the masses of which is equal to one of the “critical numbers”, are stored in different warehouses.
Help scientists figure out how many different safe ways to store Mluran.
Input format The input
to the task contains several test suites. The description of each set consists of two lines.
The first line of the description contains two integers n and k (1 ≤ n ≤ 1018, 1 ≤ k ≤ 61) - the number of isotopes that need to be stored, and the number of “critical numbers”. The next line contains k different natural numbers, each of which is a power of two and does not exceed 2n - critical numbers. Critical numbers are separated by spaces.
The number of data sets in each test does not exceed 10000. The last line of the test contains two zeros.
Output format
For each test set on a separate line print the number of safe methods for storing all isotopes in two warehouses, taken modulo 109 + 7.

Time limit - 2 seconds
Memory limit - 256 megabytes
After the recent fall of a meteorite in the Urals, many governments have thought about protecting the Earth from asteroids. For this, the International Anti-Meteorite Agency (MAMA) was created, in which the best scientists in the field of astrophysics were invited.
For several weeks, scientists have found that n asteroids fly in the immediate vicinity of the Earth, and if the asteroid is strictly greater than R from the Earth, then it does not pose a danger to it. For simplicity, scientists suggested that all asteroids near the Earth fly in a straight line, and determined their position and velocity vector at zero time. Now, scientists want to learn how to respond to queries about how many asteroids pose a danger to the Earth at some point in time.
For convenience, we introduce a rectangular Cartesian coordinate system. Let the Earth have coordinates (0, 0, 0). All asteroids and the Earth are considered material points in space.
Several queries were asked about specific points in time. For each of them, it is required to determine how many asteroids at this moment pose a danger to the Earth.
Input format
The first line contains two integers n and R (1 ≤ n ≤ 100000, 1 ≤ R ≤ 106) - the number of asteroids and the radius of the danger zone.
Each of the next n lines contains six integers xi, yi, zi, vxi, vyi and vzi (−106 ≤ xi, yi, zi ≤ 106, −100 ≤ vxi, vyi, vzi ≤ 100) - the coordinates that specify the initial position and velocity vector of the i-th asteroid. It is guaranteed that the velocity vector is not equal to 0.
The next line contains a single integer m (1 ≤ m ≤ 100000) - the number of times that scientists are interested in.
Each of the next m lines contains one integer ti (0 ≤ ti ≤ 107) - a point in time that interests scientists.
Output format
For each moment in time, print a single integer - the number of asteroids that are in the danger zone.

Time limit - 2 seconds
Memory limit - 256 megabytes The
year 2112 was drawing to a close, and you, together with a small team of like-minded people, decided to go in search of treasures in one abandoned country. The cities of this country are connected by roads along which you can move in both directions. You know that the inhabitants of this country loved to bury their treasures along these roads. Therefore, you want to drive along all the roads of this country and find buried treasures. You need to make an effective travel plan in advance. To do this, choose a city from which to start your journey. Then, moving along the roads, visit some more cities. The plan drawn up is called effective if each road will be visited by you exactly once.
Planning is complicated by one fact. Some pairs of cities are connected by teleporters. For example, if the city A and the city B are connected by teleport, then, having arrived on a road to the city A, you will immediately teleport to the city B and can continue driving only along the roads that are connected to the city B. Similarly, if you came by the road to city ​​B, then immediately teleport to city A and continue on the roads that are connected to city A.
Each city can be teleported to no more than one other city. You need to make an effective travel plan.
Input format
The input contains a description of several tests. Each test has the following structure. The first line contains three integers n, m, k (1 ≤ n ≤ 105, 1 ≤ m ≤ 105, 0 ≤ k ≤ 105) - the number of cities, the number of roads and the number of teleporters. The next m lines contain two different numbers - the numbers of cities that are connected by the next road. Next, k lines contain two different numbers that describe pairs of cities that are connected by teleporters.
There can be several roads between two cities. No city is connected by a road with itself. No city is teleported to itself. Any city is teleported to no more than one other city.
It is guaranteed that the total number of cities in all tests does not exceed 105. Similarly, the total number of roads and the total number of teleporters also do not exceed 105. The last line of input contains three zeros. They do not need to be processed.
Output format
For each data set, output the answer in the following format: if an effective visit plan cannot be drawn up, print No. in a single line. Otherwise, in the first line print Yes, and in the second - m numbers indicating the road numbers. Roads should be displayed in the order in which they must be visited. Roads are numbered from one in the order in which they are given in the input. For each test, roads are numbered independently.