# Mobile Yandeks.Blitz: parse tasks

In 2018, we held three Yandex Blitz competitions — machine learning, mobile development, and the frontend. The third competition was held quite recently - congratulations to the winners! In the meantime, we want to return to the second one, where tasks were proposed at the interface of algorithms and writing software for Android / iOS. Candidates for the position of a mobile developer in Yandex will benefit from the experience of solving such problems. Read detailed reviews of some of them. And if you did not participate in the Blitz, it is better to first try to solve them yourself .

## Task "Gas"

Input | Conclusion | Time limit | Memory limit |
---|---|---|---|

standard input or input.txt | standard output or output.txt | 15 seconds | 15 megabytes |

Nika is developing an application for top managers of a major gas company that will help them plan production.

The company considers n deposits that are removed from the line by d _{1} ... d _{i} ... d _{n} kilometers and can give v _{1} ... v _{i} ... v _{n} gas units. A separate license is sold for each deposit - licenses cost s _{1} ... s _{i} ... s _{n} .

To connect the field with the pipeline, you need to build pipelines. The company is assisted by a contractor who is able to lay m different types of pipes. The pipes differ from each other in length (l _{1} ... l _{i} ... l _{m} ) and price (p _{1} ... p _{i} ... p _{m} ). They can be combined with each other as you like.

The company has k coins and wants to get as much gas as possible.

How much can a company get if it gives the contractor optimal orders?

The pipeline may be longer than the distance from the field to the line.

#### Input format

The first line contains an integer k ≤ 10 ^{5} .

The second line contains an integer n ≤ 15.

The next n lines contain three integers d _{i} ≤ 100, v _{i} ≤ 100 and s _{i} ≤ 100.

Numbers are separated by a space.

The next line contains an integer m ≤ 15.

The next m lines contain two integers of each l _{i} ≤ 100 and p _{i} ≤ 100. The numbers are separated by a space.

#### Output format

The only line with the answer.

#### Examples

Input | Conclusion |

116 3 58 7 50 81 71 56 52 57 31 3 47 9 1 25 18 61 | 57 |

#### Parsing

To begin with, we will define the notation. Let there is a class of objects Deposit (deposit) with parameters$\$\; inline\; \$\; dd\_\; \{i\}\; \$\; inline\; \$$ (remoteness), $\$\; inline\; \$\; dv\_\; \{i\}\; \$\; inline\; \$$ (production) and $\$\; inline\; \$\; Ds\_\; \{i\}\; \$\; inline\; \$$(license cost). Indexing objects of this type will be variable i. There is also a Pipeliner object class with parameters$\$\; inline\; \$\; PPl\_\; \{j\}\; \$\; inline\; \$$ (the length of the pipe that the contractor can build) and $\$\; inline\; \$\; PPp\_\; \{j\}\; \$\; inline\; \$$(the price of this pipe), we index through j. The participants of the blitz many times had a question whether one kind of pipe could be used twice. It is assumed that there is not, and the given example clearly shows this. So according to the condition of this task, having accepted$\$\; inline\; \$\; D\_\; \{i\}\; =\; \{0,\; 1\}\; \$\; inline\; \$$ (choose a field or not) and $\$\; inline\; \$\; PP\_\; \{j\}\; =\; \{0,\; 1\}\; \$\; inline\; \$$ (choose contractor or not), you can create a linear programming problem:

$\$\; inline\; \$\; \backslash \; sum\; \backslash \; limits\_\; \{i\}\; D\_\; \{i\}\; *\; Dv\_\; \{i\}\; \backslash \; rightarrow\; max\; \backslash \backslash \; \backslash \; sum\; \backslash \; limits\_\; \{i\}\; D\_\; \{i\}\; *\; Ds\_\; \{i\}\; +\; \backslash \; sum\; \backslash \; limits\_\; \{j\}\; PP\_\; \{\; j\}\; *\; PPp\_\; \{j\}\; \backslash \; leq\; k\; \backslash \backslash \; \backslash \; sum\; \backslash \; limits\_\; \{i\}\; D\_\; \{i\}\; *\; Dd\_\; \{i\}\; \backslash \; leq\; \backslash \; sum\; \backslash \; limits\_\; \{j\}\; PP\_\; \{j\}\; *\; PPl\_\; \{j\}\; \backslash \backslash \; D\_\; \{\; i\}\; =\; \{0,\; 1\},\; PP\_\; \{j\}\; =\; \{0,\; 1\}\; \$\; inline\; \$$

It can be solved, for example, by the simplex method. However, according to the problem statement, we are required to return only the maximum production volume (that is, the value of the objective function) and it is not required to specify which fields and which contractors to select. Together with the limitations in the condition of the problem can be solved by dynamic programming, by constructing the table dp [length] [money], where length is the length of the pipeline, money is money. After correctly constructing the table, it is enough to find the maximum value in it, which will be the answer. The limitations of the problem of memory is enough to build.

## Task "Towers and AI"

Input | Conclusion | Time limit | Memory limit |
---|---|---|---|

standard input or input.txt | standard output or output.txt | 1 second | 64 megabytes |

Artyom is developing an artificial intelligence that plays a competitive mobile game. The rules of the game are simple.

Before the players there are n towers with height c _{1} ... c _{i} ... c _{n} . On his turn, a player can break one of the towers so that there will be several smaller towers. The players are afraid of getting tangled up in the towers, so they agreed on a restriction: after the separation, there should not be two towers of the same height. For example, a tower with a height of 7 can be divided into (1, 2, 4), but not into (1, 3, 3). Height is always an integer.

Loses the one who does not remain towers that can be destroyed.

Artem has a very smart friend who plays optimally - Artem's artificial intelligence is fighting him. To evaluate the work of AI, Artem needs to know whether the robot should win if both players act optimally. Help him with this.

The man always goes first. He will play with AI k games.

#### Input format

The first line contains an integer k <500.

Then follow k blocks of two lines each.

The first line of each block contains an integer 0 <n ≤ 50.

The second line of each block contains n integers 0 <c _{i} ≤ 50. Numbers are separated by spaces.

#### Output format

k lines, each of which contains the value true or false depending on whether a person wins the game.

#### Examples

Input | Conclusion |

2 one four 2 eleven | false false |

#### Parsing

The proposed tower game is a fair and equal game for two players, in which it is impossible to play a draw.

Consequently, the victory of a particular player in a game is determined by the state of the game and the order of moves of two players. For readers who are familiar with the theory of games, it is obvious that any of the equal games of two players is in fact equivalent to the game “him”, which means our game too.

Here is a brief description of the game ( refer to the source - go for it for detailed information):

There are several piles, each with several stones. In one move a player can take any non-zero number of stones from any one pile and throw them away. Accordingly, the loss occurs when there are no more moves, i.e. all the heaps are empty.

So, the state of the game "him" is uniquely described by an unordered set of positive integers. In one move, it is allowed to strictly reduce any of the numbers (if, as a result, the number becomes zero, it is removed from the set).

The solution to this game is to find the xor-sum of the size of the piles, and only if this amount is non-zero, can we definitely say that we are in a winning state.

Next comes the Spragg-Grande theorem, which says that the state U of any equal game of two players can be compared to a handful of them of size X. Once the function defining the display of the states of our game-game is found, the problem will be solved to solve it-game that is already known.

## Task “Rating Indication”

Input | Conclusion | Time limit | Memory limit |
---|---|---|---|

standard input or input.txt | standard output or output.txt | 1 second | 64 megabytes |

Galya is developing a feedback aggregator. She decided to mark the ratings of institutions with the help of seven-pointed stars.

The drawing system on an input receives a rectangle with height h and width w, the left upper corner of which is located at the point (x, y). The star should be drawn according to the following rules:

- The size of the star is determined by the width or height of the rectangle - the fact that it is smaller. (See pictures.)
- If one of the dimensions of the rectangle is larger than the corresponding dimension of the star, the star should be centered on that dimension.
- The star is turned upwards.

The drawing system expects the coordinates of the vertices of the star from the Gali code. Help Galet calculate them.

To build a seven-pointed star, Galya takes the outer contour of a figure obtained by connecting the vertices of a regular heptagon through one. In the coordinate system, the X axis is directed from left to right, the Y axis from top to bottom. Gali’s program does not fall, having received incorrect widths and heights at the input.

#### Input format

The only line contains integers x, y, w and h, separated by spaces.

Example: the entry 150 0 50 100 denotes a rectangle 50 points wide, 100 points high and with an upper left corner at (150, 0).

#### Output format

The only line containing 28 numbers separated by spaces is the coordinates of the vertices of the star, starting from the top and further clockwise. Numbers should be rounded to integers. See an example of the output and an illustration of the problem before proceeding to the solution.

Example: the output of three points (1, 2), (3, 4), (5, 6) should look like this: 1 2 3 4 5 6.

#### Examples

Input | Conclusion |

0 0 100 100 | 50 1 65 21 90 21 85 45 100 64 78 75 72 99 50 88 28 99 22 75 0 64 15 45 10 21 35 21 |

#### Notes

The required accuracy is 10 significant digits.

Coordinate system: X axis is directed from left to right, Y axis from top to bottom:

- Expected vertex order:

Examples of entered stars:

#### Parsing

The solution of the problem is reduced to three stages: to build a reference star with the desired orientation in space, scale the resulting points, calculate and apply the offset.

**Building a star The**

easiest way is to build a star inscribed in a circle with a unit radius centered at the origin. The points of the outer vertices are calculated using trivial trigonometry, but with the internal tasks a little more difficult. They can be found in at least two ways. A simpler way is to find the intersections of the segments connecting the outer vertices. More difficult is to find a formula for calculating the radius of the inscribed circle from the radius of the circumscribed circle. The easiest way to do this is first, for example, for a 5-pointed star, and to generalize to N-terminal with an arbitrary gap between the connected vertices.

**Scaling**

In all the options given the size in which we need to enter the star. Thus, we need to scale the obtained points so that the distance from the leftmost to the rightmost does not exceed the specified width, and the distance from the highest to the lowest does not exceed the specified height. Take the scaling factors to bring the width and height to the desired values, and choose the smaller one. Since we prudently built a reference star with the center at the origin, it is enough to simply multiply the coordinates of each point by the selected coefficient.

**Offset The**

last **thing** remains: move our points so that the star is within the specified limits. The input data of all variants can be reduced to a bounding box with a given coordinate of the upper left corner. Everything is simple: we take the highest point of those obtained at the previous stage, we consider the difference of its y-coordinates with the y-coordinate of the upper left corner, and shift all points vertically by the obtained value. We proceed in the same way with the x-coordinate, just take not the highest point, but the leftmost one. The final touch is left: center the star in this rectangle.

Further actions depend on which coefficient we chose at the previous stage:

- if we scaled in height, we take the difference between the width of the rectangle and the distance from the leftmost to the rightmost point;
- if scaled in width, we take the difference between the height of the rectangle and the distance from the highest to the lowest point.

Divide the resulting value by 2 and shift the points along the corresponding dimension. Reply received.

## Task “Rotation and scaling of a circle”

Input | Conclusion | Time limit | Memory limit |
---|---|---|---|

standard input or input.txt | standard output or output.txt | 1 second | 64 megabytes |

Vika is developing a graphics editor for smartphones and tablets. She wants to allow the user to rotate the circle on the screen with two fingers and resize it, like this:

The figure rotates at the same angle as the segment that connects the fingers. The size of the figure changes in proportion to the length of the segment. First, the figure is rotated and then resized. Initially the circle has coordinates (x, y) and radius r. A list of touch events describing the user's gesture is given. Help Vika calculate the final coordinates of the center of the circle and its radius. The circle rotates about the point (a, b).

Description of the touch event contains finger id, coordinates and type of event. The first finger that the user has attached gets id 0, the second finger id 1, and so on.

Example:

0 337 490 ACTION_DOWN - this means that an ACTION_DOWN event occurred with the finger 0 at the point (337, 490).

Touch events are of the following types:

- ACTION_DOWN - the user has attached the first finger to the screen at a given point.
- ACTION_POINTER_DOWN - the user has put the second finger on the screen at a given point.
- ACTION_MOVE - the user has moved a finger to a given point.
- ACTION_POINTER_UP - the user moved the second finger to the specified point and released it.
- ACTION_UP - the user moved the first finger to the specified point and released it.
- ACTION_CANCEL - the user has interrupted the gesture.

#### Input format

The first line contains the numbers x, y and r, separated by spaces. The second line contains the numbers a and b, separated by spaces. The next few lines contain sequential touch events.

#### Output format

The only line with coordinates and radius. Numbers are separated by spaces.

#### Example

Input | Conclusion |

252 194 78 445,559 0 337 490 ACTION_DOWN 1 599 490 ACTION_POINTER_DOWN 1 576 564 ACTION_MOVE 1,552,590 ACTION_MOVE 0 407 375 ACTION_MOVE 1 505 615 ACTION_MOVE 1,482,620 ACTION_MOVE 0 477 360 ACTION_MOVE 1 435 616 ACTION_MOVE 1 411 607 ACTION_MOVE 0 547 386 ACTION_MOVE 1,364,548 ACTION_POINTER_UP 0 571 387 ACTION_UP | 831 704 73 |

#### Notes

When outputting a result, all floating-point values should be rounded to an integer value according to the rules of mathematical rounding.

#### Parsing

Despite the fact that the gesture seems complicated, it can be divided into two components: rotation and scaling. To rotate the shape, we need to calculate the rotation angle, which can be obtained using the following formula:

a = atan2 (prevTouchX2 - prevTouchX1, prevTouchY2 - prevTouchY1) - atan2 (currentTouchX2 - currentTouchX1, currentTouchY2 - currentTouchY1).

Having obtained the angle of rotation, you need to rotate the figure itself, which is reduced to the rotation of each point of the figure by the angle of rotation. After we turned the figure, it remains for us to scale it. Scaling of a figure is implemented rather trivially. It is necessary to remember the distance between the first and second fingers when receiving the ACTION_POINTER_DOWN event for the second finger, after which, tracking the distance between the first two fingers, we can calculate the coefficient by which the figure should be scaled.

## Task “Road construction”

Input | Conclusion | Time limit | Memory limit |
---|---|---|---|

standard input or input.txt | standard output or output.txt | 1 second | 64 megabytes |

In the mobile game, the main character builds a base on a distant planet. It starts from the perimeter - the towers connected by direct laser walls. The architects from headquarters send him a plan on which n towers are marked, having coordinates (x _{1} , y _{1} ) ... (x _{i} , y _{i} ) ... (x _{n} , y _{n} ). From the point of view of the base's defense, there is no point in putting three or more neighboring towers on one straight line. Staff architects, however, sometimes have towers in this way, so the player has to remove the extra intermediate towers himself.

Having finished with the perimeter, the hero begins to equip the base from the inside. He wants to build k roads between the towers - the road can connect any two not adjacent towers, but he cannot cross another road or wall. From one tower can go any number of roads.

The hero has p road robot. To choose the best road construction plan, the hero instructs them to go through all possible options. Robots begin to work simultaneously and time after time at the same time bring unique options for the location of roads. If, before the next iteration, it turns out that there are fewer unexplored options than robots, the extra robots are released and sent to the kitchen to prepare lunch. The remaining robots finish the last options and turn off.

If it turns out that you can pave the way outside the base, the hero declares the base unsafe and flies away from the planet.

How many robots will work in the kitchen?

#### Input format

The first line contains three integers 4 ≤ n ≤ 10 ^{7} , 1 ≤ k ≤ n and a prime number 105 <p <11 × 104. Numbers are separated by spaces.

The next n lines contain two integers each, 0 <x _{i} , y _{i} <109. The numbers are separated by spaces.

#### Output format

The only line with the answer. If the base is not secure, output −1.

#### Example 1

Input | Conclusion |

4 1 101363 0 0 ten eleven 0 1 | 101361 |

There are two ways to pave the only way: (0, 0) - (1, 1) and (1, 0) - (0, 1). They will deal with two robots, and the rest will go to the kitchen: p - 2 = 101 361.

#### Example 2

Input | Conclusion |

4 1 101363 ten 20 0 1 12 | -one |

Here you can build a road between (1, 0) - (0, 1), and this is outside the base. The hero recognizes the base as unsafe, the answer is −1.

#### Example 3

Input | Conclusion |

4 1 101363 0 0 ten 20 0 1 | 101363 |

The towers (0, 0), (1, 0) and (2, 0) stand on one straight line, so the hero will not build the middle tower (1, 0). There is no way to build a road, so all robots will immediately go to the kitchen: p = 101 363.

#### Parsing

We divide the solution of the problem into three steps.

The first step is for the input dataset of the vertices, determine whether the polygon is convex, and if so, how many real vertices it has. A polygon is convex if all its vertices are located on the same side of the line carrying any edge. For each triple of adjacent vertices$\$\; inline\; \$\; (x\_\; \{i-1\},\; y\_\; \{i-1\}),\; (x\_\; \{i\},\; y\_\; \{i\}),\; (x\_\; \{i\; +\; 1\},\; y\_\; \{i\; +\; 1\})\; \$\; inline\; \$$ construct a pair of vectors $\$\; inline\; \$\; ab\; =\; ((x\_\; \{i-1\},\; y\_\; \{i-1\}),\; (x\_\; \{i\},\; y\_\; \{i\}))\; and\; bc\; =\; ((x\_\; \{i\},\; y\_\; \{i\}),\; (x\_\; \{i\; +\; 1\},\; y\_\; \{i\; +\; 1\}))\; \$\; inline\; \$$, and calculate the sign of the expression ab.x *bc.y - bc.x* ab.y. If the expression is 0, then the vertices lie on one straight line and, by the condition of the problem, the tower standing at the middle vertex disappears, reducing the total number of towers. If for all triples of vertices the sign of the product is 0 or is always the same, then go to the second step, if not, we consider the base unsafe and print the answer -1.

The second step. The number of ways to construct k disjoint diagonals inside a convex N-gon is equal to$\$\; inline\; \$\; V\; =\; 1\; /\; (k\; +\; 1)\; \{N-3\; \backslash \; choose\; k\}\; \{N\; +\; k-1\; \backslash \; choose\; k\}\; \$\; inline\; \$$, we need to calculate the expression p - V mod p, where p is simple.

Imagine N! as$\$\; inline\; \$\; a\; *\; p\; ^\; e\; \$\; inline\; \$$, where the greatest common divisor is a, and p gcd (a, p) = 1.

$\$\; inline\; \$\; \{n\; \backslash \; choose\; r\}\; =\; (n!)\; /\; (r!\; (nr)!)\; =\; a\_\; \{1\}\; *\; p\; ^\; \{e\_\; \{1\}\}\; /\; a\_\; \{2\}\; *\; p\; ^\; \{e\_\; \{2\}\; \}\; *\; a\_\; \{3\}\; *\; p\; ^\; \{e\_\; \{3\}\}\; =\; (a\_\; \{1\}\; /\; a\_\; \{2\}\; *\; a\_\; \{3\})\; *\; p\; ^\; \{e\_\; \{1\}\; -e\_\; \{2\}\; -e\_\; \{3\}\; \}\; \$\; inline\; \$$

If a $\$\; inline\; \$\; e\_\; \{1\}\; -e\_\; \{2\}\; -e\_\; \{3\}>\; 0\; \$\; inline\; \$$therefore, the expression is completely divided by p and the answer in the problem is the number p.

For the occasion $\$\; inline\; \$\; e\_\; \{1\}\; -e\_\; \{2\}\; -e\_\; \{3\}>\; 0\; \$\; inline\; \$$ = 0 the answer is $\$\; inline\; \$\; a\_\; \{1\}\; /\; a\_\; \{2\}\; *\; a\_\; \{3\}\; \$\; inline\; \$$ mod p.

When calculating we take into account that a *b mod p = (a mod p)* (b mod p) mod p, and$\$\; inline\; \$\; k\; ^\; \{-\; 1\}\; \$\; inline\; \$$ mod p = $\$\; inline\; \$\; (k)\; ^\; \{p-2\}\; \$\; inline\; \$$ mod p for simple p.

The third step. To calculate the expression$\$\; inline\; \$\; e\_\; \{1\}\; -e\_\; \{2\}\; -e\_\; \{3\}\; \$\; inline\; \$$imagine n! as 1 *2* ... *p* (p + 1) *...* 2p *(2p + 1)* ..., with (p + 1) *...* (2p-1) mod p = 1 *2* ... (p-1 ) = (p-1)! .. Total, n mod p = ($\$\; inline\; \$\; (p-1)!\; ^\; k\; \$\; inline\; \$$*k* (n mod p)! mod p, where k = floor (n / p).

## Task “Super Simple Scheduler”

Input | Conclusion | Time limit | Memory limit |
---|---|---|---|

standard input or input.txt | standard output or output.txt | 10 Seconds | 224 megabytes |

There are n tasks that need to be performed on the processor of the smartphone. Their execution requires t _{1} ... t _{i} ... t _{n} time units, and by the beginning of the d _{i} -th time unit, the i-th task must be completed.

In order to be in time, tasks can be performed in several streams, however, each new thread creates an increasing load on the battery. In the first stream, a unit of energy is consumed per unit of time, in the second stream - one and a half units of energy, in the third stream - another 1.5 times more than in the second, and so on.

Tasks can be split into units of time: first, partially perform one, then move on to another, then return to the first. At the same time to perform different pieces of the task in different threads can not.

Scheduler receives tasks one by one; having received the task, he immediately allocates time slots for it. After the task is distributed, the scheduler cannot transfer it to other slots.

How much energy will be required to complete all tasks, if you distribute them optimally?

#### Input format

The first line contains an integer 1 <n ≤ 3 × 10 ^{3} .

The next n lines contain two integers of each 0 ≤ t _{i} ≤ 10 ^{4} and 0 ≤ d _{i} ≤ 10 ^{4} . Numbers are separated by spaces.

#### Output format

The only line with the answer. Accuracy - eight decimal places.

#### Example

Input | Conclusion |

five 2 2 eleven 3 4 1 10 12 | 10.25000000 |

#### Parsing

Since according to the condition of the problem it is enough for us to count only the amount of energy consumed, we can use the solution by counting the amount of energy consumed for each unit of time. When planning a task, we take the minimum value of the energy consumed by k = 1 and, starting from the deadline of the task, we iterate over all the slots of the time interval.

If the slot power consumption value is less than the coefficient (k) value and this time slot was not used when scheduling a task, then we occupy this slot to complete the task by increasing the slot coefficient by k. repeat the time slots, starting with the deadline and until the task is fully planned. Upon completion of the planning of all tasks, it remains only to calculate the total energy consumption, adding up the obtained coefficients of each unit of time.

## Task "Destructible Objects"

Input | Conclusion | Time limit | Memory limit |
---|---|---|---|

standard input or input.txt | standard output or output.txt | 2 seconds | 64 megabytes |

In a 2D game, you can destroy objects. The game is under development, so far everything has been done very simply: the object being destroyed is an n-gon with vertices at the points (x _{1} , y _{1} ) ... (x _{i} , y _{i} ) ... (x _{n} , y _{n} ). The algorithm takes a concave vertex with the smallest number and connects it with the nearest non-neighboring vertex, so that the length of the connecting segment is minimal. Then the same is done with the resulting polygons. Everything repeats until only convex polygons remain - these are the fragments that the player will see.

For example, there is a polygon with vertices [0 1 2 3 4], and vertex 1 is concave and vertex 3 is closest to it. The algorithm connects vertices 1 and 3, obtaining figures with vertices [1 2 3] and [0 1 3 4].

The algorithm conducts the connecting segments so that they lie entirely inside the polygons. Vertices with an unfolded angle between the ribs are equated to convex. If it is possible to construct a segment to several equidistant vertices, the algorithm chooses the one that has a smaller number.

What is the sum of the lengths of all segments constructed to destroy an object?

#### Input format

The first line contains an integer n ≤ 500. The next n lines contain two integers x and y. Numbers are separated by spaces.

#### Output format

The only line with the answer. Accuracy - six decimal places.

#### Example 1

Input | Conclusion |

four 100 100 200,100 200 200 100 200 | 0.000000 |

#### Example 2

Input | Conclusion |

6 167 84 421 84 283,192 433,298 164 275 320 133 | 326.986753 |

#### Parsing

The main difficulty of the task is to determine whether the segment lies between two vertices inside the polygon. After solving this problem, the stated conditions of the problem can be performed “head on” with a complete enumeration of all variants of connections: the execution time limits and the number of vertices are rather soft. Minor moment: the definition of convex and concave vertices, as well as the direction of the traversal (whether the vertices are set clockwise or counterclockwise) is easily resolved using the skew product of vectors.

The question is, is the segment inside the polygon? A necessary condition is the absence of intersections between the segment and any other side of the polygon (with the exception of the sides adjacent to the vertices that are the ends of the segment). However, this condition is not sufficient: it is easy to come up with a figure in which the segment connecting the two vertices will be outside and not intersect its sides. Therefore, if the necessary condition is fulfilled, we need to determine whether any point of this segment (with the exception of the end points) is inside the polygon. This can be done with the help of the so-called even-odd rule: start an invisible ray from this point and count the number of its intersections with the sides of the polygon. If the number of intersections is odd, then the point (and the whole segment) lies inside the polygon, otherwise it is outside.

This problem, of course, has pitfalls - it would not be offered in the final round if the solution was simple and obvious. Here are the difficulties that can be encountered in implementation (the list, of course, can be continued):

- Determination of neighboring vertices (when passing through the zero index);
- Parallel straight lines: the case when either side partially or completely coincides with the considered segment;
- Rounding errors (in the general case, floating-point numbers should be compared with an accuracy of a certain value, in our case, passing the tests was enough for 10e-5 or more accurate);
- In the implementation of the even-odd rule, the case of passing the ray through the vertex;
- In the case of the passage of the beam through the top there is another pitfall: when the beam passes through the top with an angle of 180 degrees between the sides and coincides with these sides.

## “DNA” task

Input | Conclusion | Time limit | Memory limit |
---|---|---|---|

standard input or input.txt | standard output or output.txt | 8 seconds | 128 megabytes |

The corporation of good developed a device that instantly identifies people by genotype. A person touches a finger with a special sensor, and the device takes a specific fragment of its DNA and searches for sequences in this fragment that are stored in the database. An example of a DNA fragment and n different sequences is given. Make a list of the substrings that the device will find. Four letters are found in DNA: A, T, G, and C. The desired sequences may overlap. The sequence cannot completely coincide with the beginning of another sequence.

#### Input format

The first line contains an integer n. The following n lines contain one DNA sequence. The last line contains the tested DNA fragment. The total amount of input data does not exceed 6-10 ^{6} characters.

#### Output format

On each line of the output, write one occurrence of the sequence in the fragment to be checked. Specify the starting position number and the substring itself. Separate one from the other with a space. The numbering of letters in the DNA fragment begins with one. Output sorted by starting position number. Be sure to look at the examples before embarking on a task.

#### Example

**Enter** (copy the snippet to any editor to see it entirely):

5

TTT

GAAGCT

CAAT

AGA

AGGCA

CTTTCAGAATCATGACCTGCACGGCAAAGAGACGCTTATTATGGAGCTCGACATGGCAATAACGCGACGAATCTACGTCACGACGAGAATAGTGTAAACGAAGCTGCTGACGGCGGAAGCGTCAAAGGGGTCTGTGAATTGTTATTCGCGAAAAACATCCGTCCCCGTGGGGGATAGTCACCGACGCCGTTTTATAGAAGCCTAGGGGAACAGGTTGGTTTAACTAGCTTAAGAAAGTAAATTCTGGGATTATACTGTAGTAATCACTAATTTACGGTGAGGGTTTTATGGCGGATCTTTACAAATTCAAGCCAGGTGATTTCAACAAATTTTGCTGACGATTTAGGCGCACTATCCCCTAAACTACAAATTAGAAAATAGCGTTCCTTGACGGCTAGAATTACCTACCGGCCTCCACCATACCTTCGATATTCGCGCCCACTCTCCCATTAATCCGCACAAGTGGATGTGATGCGATTGCCCGCTAAGATATTCTAACGTGTAACGCAGATGAGTATTCTACAGAGTTGCCGTACGCGTTGAACACTTCACGGATGATAGGAATTTGCGTATAGAGCGTGTCATTGAGGGGTTATACACCCGTAGACTACAACGGGCCCGGCTCAATCAGAACTCGAGTGCCTTGAATAACATACTCATCACTAAACATTCTCAACAGTCAATCGAGCAAGTCCATTATCAACGAGTGTGTTGCAGTTTTATTCTCTCGCCAGCATTGTAATAGGCACTAAAAGAGTGATGATAGTCATGAGTGCTGAGCTAAGACGGCGTCGGTGCATAGCGGACTTTCGGTCAGTCGCAATTCCTCACGAGACCCGTCCTGTTGAGCGTATCACTCTCAATGTACAAGCAACCCGAGAAGGCTGTGCCTGGACTCAACCGGATGCAGGATGGACTCCAGACACGGGGCCACCACTCTTCACACGTAAAGCAAGAACGTCGAGCAGTCATGAAAGTCTTAGTACCACGTGCCATCT

**Conclusion**:

2 TTT

6 AGA

28 AGA

30 AGA

57 CAAT

86 AGA

100 GAAGCT

190 TTT

191 TTT

196 AGA

219 TTT

232 AGA

271 TTT

284 TTT

285 TTT

298 TTT

320 TTT

330 TTT

331 TTT

342 TTT

373 AGA

397 AGA

488 AGA

509 AGA

524 AGA

565 TTT

574 AGA

605 AGA

625 CAAT

630 AGA

681 CAAT

718 TTT

719 TTT

744 AGGCA

754 AGA

784 AGA

808 TTT

821 CAAT

833 AGA

861 CAAT

879 AGA

921 AGA

955 AGA

#### Parsing

This is the last task in the final, but not the last in complexity. The solution of the problem was reduced to finding patterns in the line in the most optimal way - for example, using the Aho-Korasik algorithm. The algorithm builds a finite state machine, which then passes the search string. The machine receives in turn all the characters in the string and moves along the corresponding edges. If the machine has reached the end position, the corresponding dictionary line is present in the search bar.

The whole difficulty was that it was necessary to find such a solution for the line.

## “QR Quest” task

Input | Conclusion | Time limit | Memory limit |
---|---|---|---|

standard input or input.txt | standard output or output.txt | 1 second | 64 megabytes |

#### Input format

The first line contains a single integer t, denoting the number of test cases. The next t lines contain eight integers n _{i} separated by spaces.

#### Output format

t lines, each of which contains one integer.

#### Example 1

Input | Conclusion |

four 8 10 1 9 2 6 7 8 14 2 0 11 10 4 1 0 6 6 4 1 10 0 11 6 11 4 3 4 14 8 12 5 | 0 13 15 five |

#### Example 2

Input | Conclusion |

four 9 10 6 2 12 11 7 2 3 10 1 14 13 13 1 1 6 8 8 5 3 2 6 4 5 11 5 5 3 1 10 7 | 3 9 2 7 |

#### Parsing

We left this bonus task for the most inquisitive, because we still had to think about the solution technique. QR code allowed to follow the link to the document containing three tables of values. With these values it was required to carry out some manipulations.

A total of eight numbers were input - the coordinates of the cells in these tables, that is, 4 pairs with the coordinates of a column and a row. It was necessary to guess which operation was performed with these cells and from which table the extra cell.

By simple manipulations it was possible to make sure that it is the xor sum for the four cells of tables A, B and C, addressed by the indices a _{0} ... a _{7} :

R = A [a _{0} , a _{1} ] ^ B [a _{2} , a _{3} ] ^ B [a _{4} , a _{5} ] ^ C [a _{6} , a _{7} ].