Your objective is to plan a holiday trip from your house, given by 2D coordinates $$$(x_s , y_s)$$$ , to your travel destination, given by $$$(x_d , y_d)$$$. Being aware of the environmental impact of travel, you want to minimize the $$$\mathtt{CO}_2$$$-cost of your holiday, but you still want to keep the total number of kilometers traveled within a given budget $$$B$$$.

To aid you in planning, you have access to a map of $$$N$$$ stations, possibly linked by $$$T$$$ different modes of transportation (airplane, train, etc.) numbered $$$1,\ldots, T$$$. Each mode has a $$$\mathtt{CO}_2$$$-cost per distance unit $$$C_1 , \ldots , C_T$$$. You can travel by car from your home to the destination, from your home to any station, and from any station to the destination point, at a cost $$$C_0$$$ per distance unit. $$$C_0$$$ is always greater than any of $$$C_1, \ldots, C_T$$$. Each of the $$$N$$$ stations has coordinates $$$(x_i , y_i)$$$ for $$$i = 0,\ldots, N - 1$$$. Each station may be connected to some other stations via one or several of the $$$T$$$ modes. Each connection works both ways, so only one direction has to be listed. There can be multiple modes of transportation available between two stations. You can only travel between two stations via their connections using the available transportation modes (car travel is not allowed between stations).

The distance between two points $$$a$$$ and $$$b$$$ is the 2D distance between $$$(x_a , y_a)$$$ and $$$(x_b , y_b)$$$, rounded to the nearest integer above: $$$$$$ \mathop{dist}(a, b) = \left\lceil\sqrt{(x-a)^2+(x-b)^2}\right\rceil, $$$$$$ and the $$$\mathtt{CO}_2$$$-cost of travel between $$$a$$$ and $$$b$$$, using transport mode $$$i$$$ is: $$$$$$ \mathop{cost}(a, b, i) = C_i \times \mathop{dist}( a, b ). $$$$$$ Given two source–destination coordinates, a budget $$$B$$$ expressed in distance units, a list of transportation modes and their respective $$$\mathtt{CO}_2$$$ -costs, and the station network, your task is to compute the minimal $$$\mathtt{CO}_2$$$ -cost possible while traveling at most $$$B$$$ kilometers.

Charles's program works as follows. It first scans the whole colony, building the list of tags of the ants that are recognized. Then it assigns fresh tags to the new ants. To do so, the program simply picks the first natural number (i.e., nonnegative integer) that is not currently assigned to any ant, and so on.

Due to some glitches in the image recognition device and in the program, there are sometimes negative or very large numbers that appear in the input list. These are simply ignored by Charles's program.

Your job is to reimplement the part of Charles's program that finds a fresh tag to assign to a new ant.

A gene of their DNA is a sequence of bases. These genes operate on proteins, which are extremely long chains of amino-acids ($$$a - b - c - \ldots$$$). Amino-acids are either simple or complex (composed of two other amino-acids). Proteins always contain several billions of amino-acids.

Genes operate on proteins in the following way: the seven different bases (C, D, L, P, R, S, U) correspond to different transformations on the protein. The result of the operation of a gene on a protein is obtained as the combination of the individual transformations by each base of the gene: the first base of the gene transforms the input protein, the resulting protein is then transformed according to the second base of the gene, and so on. Life is not perfect and thus one of these transformations may fail, in which case the overall transformation fails. If, at any point in the transformation, the protein is reduced to a chain of three or fewer amino-acids (simple or complex) then the transformation fails.

The effect of each base is described in the following table where $$$X$$$ denotes the tail of the protein, while $$$a$$$, $$$b$$$, and $$$c$$$ are amino-acids (either simple or complex):

$$$$$$ \begin{array}{c r l} \hline \text{base} & \text{input protein} & \text{output protein} \\ \hline \textbf{C} & a-X & a-a-X\\ \textbf{D} & a-X & X\\ \textbf{L} & a-X & \left\{\begin{array}{l l} b-X & \text{if $a$ is the complex amino-acid $\langle b, c\rangle$} \\ \text{fail} & \text{if $a$ is a simple amino-acid} \end{array}\right. \\ \textbf{P} & a-b-X & c-X \text{ where $c$ is the complex amino-acid $\langle a, b\rangle$}\\ \textbf{R} & a-X & \left\{\begin{array}{l l} c-X & \text{if $a$ is the complex amino-acid $\langle b, c\rangle$} \\ \text{fail} & \text{if $a$ is a simple amino-acid} \end{array}\right. \\ \textbf{S} & a-b-X & b-a-X\\ \textbf{U} & a-X & \left\{\begin{array}{l l} b-c-X & \text{if $a$ is the complex amino-acid $\langle b, c\rangle$} \\ \text{fail} & \text{if $a$ is a simple amino-acid} \end{array}\right. \\ \hline \end{array} $$$$$$

For example, the gene PSDSPCRPSDUL transforms a protein like this:

• the input protein is $$$a - b - c - d - e - f - \ldots$$$
• then applying the rule for the first P produces: $$$\langle a, b \rangle - c - d - e - f - \ldots$$$
• then applying the rule for S produces: $$$c - \langle a, b \rangle - d - e - f - \ldots$$$
• then D gives: $$$\langle a, b\rangle - d - e - f - \ldots$$$
• then S gives: $$$d - \langle a, b\rangle - e - f - \ldots$$$
• then P gives: $$$\langle d, \langle a, b\rangle \rangle - e - f - \ldots$$$
• then C gives: $$$\langle d, \langle a, b\rangle \rangle - \langle d, \langle a, b\rangle \rangle - e - f - \ldots$$$
• then R gives: $$$\langle a, b\rangle - \langle d, \langle a, b\rangle \rangle - e - f - \ldots$$$
• then P gives: $$$\langle \langle a, b\rangle , \langle d, \langle a, b\rangle \rangle \rangle - e - f - \ldots$$$
• then S gives: $$$e - \langle \langle a, b\rangle , \langle d, \langle a, b\rangle \rangle \rangle - f - \ldots$$$
• then D gives: $$$\langle \langle a, b\rangle , \langle d, \langle a, b\rangle \rangle \rangle - f - \ldots$$$
• then U gives: $$$\langle a, b\rangle - \langle d, \langle a, b\rangle \rangle - f - \ldots$$$
• and finally L gives: $$$a - \langle d, \langle a, b\rangle \rangle - f - \ldots$$$

You are given two genes, and you must decide whether they are equivalent. Two genes are equivalent if for every input protein composed of at least one billion of simple amino-acids, either the application of both genes produces the same output protein, or both applications fail.

An artist prepared a pixel art drawing for depicting animals in black and white. These drawings should be displayed on a gigantic pixelated, rectangular screen, with $$$K$$$ rows (ordered from $$$0$$$ to $$$K - 1$$$, from top to bottom) and $$$L$$$ columns (ordered from $$$0$$$ to $$$L - 1$$$, from left to right): displaying drawings on such screens is your job.

When you initialize the screen, it displays only white pixels. Then, its pixels should be controlled individually by switches, and pressing the switch of a pixel $$$P$$$ ought to change the color of $$$P$$$, either from black to white or from white to black. However, the screen has a defect: pressing the switch of the pixel $$$P$$$ also changes the color of those pixels that have an edge in common with $$$P$$$, i.e., those pixels that are adjacent horizontally or vertically (but not diagonally). Yet, it might still be possible that, by adequately choosing which switches you press, even this defective screen can display the drawing you were handed.

Can you manage to display that drawing? If yes, which set of switches should you press?

During summer, the ice around the islands melt and the islands become too small to host all the birds. Some penguins live on the icebergs floating around. For her study, Tania needs to measure the area of those icebergs.

Using satellite imagery and image recognition, Tania has obtained a map of the icebergs and your goal is to measure their area. The island studied by Tania is quite small and the Earth can locally be approximated as a flat surface. Tania's map thus uses the usual 2D Cartesian coordinate system, and areas are computed in the usual manner. For instance, a rectangle parallel to the axes defined by the equations $$$x_1 \le x \le x_2$$$ and $$$y_1 \le y \le y_2$$$ has an area of $$$( x_2 - x_1 ) \times (y_2 - y_1 )$$$.

In Tania's representation, an iceberg is a polygon represented by its boundary. For each iceberg, Tania has noted the sequence of points $$$p_1,\ldots, p_k$$$ defining the border of the iceberg. The various icebergs never touch each other and they never overlap. Furthermore, the boundary $$$p_1, \ldots , p_k$$$ of an iceberg is always a "simple" polygon, i.e. no two segments in $$$[ p_1 ; p_2 ], \ldots, [ p_k ; p_1 ]$$$ cross each other.

Animals are waiting in a line, in a quarantine zone, before they can enter a hunting-free area, where they will find an easier life.

When entering the quarantine zone, animals have to check in with a guard. The guard writes down the animal species, and then the animal is allowed to join the end of the line, in the last position. At the other end of the line, animals have to check out: when the animal in the first position in the line is finally allowed to enter the hunting-free area, another guard writes down the animal species. Thus, each guard maintains a list of animal species, written down in the chronological order in which the animals have checked in or out. A total of $$$N$$$ animals, representing $$$S$$$ species, have checked in (and, therefore, checked out).

However, animals may enter the waiting line and leave it in different orders. Indeed, some animal species are friends with each other, and thus two animals from such species, if they occupy adjacent places in the line may accept to switch their places.

You have a list of those pairs of animal species that may accept to switch their places when being in adjacent positions in the line: this list contains L pairs. You were handed out the check-in list maintained by the first guard. Depending on which animals decided to switch places, several check-out lists might be possible. Among all those possible lists, which one comes first in alphabetical order?

As a very first test to decide if this is indeed a good pseudo-random number generator, Donald wishes to count the number of even values produced by this sequence, in order to check whether this is close enough to $$$50\%$$$. Your help will be welcome.

Douglas is asking for your help to estimate the total number of rats in his area. Looking up in your statistics textbook, you propose using the Chapman estimator $$$\widehat{N}$$$, given by: $$$$$$ \widehat{N} = \left\lfloor \frac{(n_1+1)(n_2+1)}{n_{12}+1} -1\right\rfloor $$$$$$ where $$$\lfloor x\rfloor$$$ is the floor of a real number $$$x$$$, i.e., the closest integer less than or equal to $$$x$$$.

He tells you that these trees are very peculiar. First, they are flat: one of their sides is facing south and the other is facing north. Second, when one of their branches splits, it splits in exactly two sub-branches, which go in two opposite directions: one goes towards the west and the other goes towards the east. All in all, such a tree can be very easily represented as a binary tree such as computer scientists are used to. (Mathematically, a binary tree is either the empty tree or an internal node with exactly two children, which are themselves binary trees.)

As a great programmer, you get excited as soon as you hear about binary trees. Darwin continues his explanations: in such a tree, branches are either horizontal or go up. Still obsessed by binary trees, you figure out that this corresponds to saying that, in the binary tree representation, if internal nodes are labelled by the elevation (distance from the ground) of the corresponding branch split, then the label of a non-root node is always larger than or equal to the label of its parent. Empty trees are not labelled.

While you find this property rather boring and not very interesting, Darwin goes on and tells you a really astonishing and subtle fact he recently discovered about his favorite species of trees. After a lengthy discussion with Darwin, you finally understand that this property can be simply expressed in the binary tree representation. Namely, if one does an inorder traversal of the labeled binary tree of any tree of that species, the resulting sequence of elevations is always the same! (The inorder traversal of the empty tree is the empty sequence and, if a tree is not empty, its inorder traversal is the concatenation of the inorder traversal of the left sub-tree, followed by the label of the top node, followed by the inorder traversal of the right sub-tree.)

After having heard the impressive research results of your friend, you urge him to elaborate on the methodology he uses to count the varieties of this particularly surprising species. This leads him to reveal the hypothesis he is currently working on: every tree of a given variety is represented by the same binary tree, which uniquely identifies that variety. Moreover, every labeled binary tree verifying the conditions above indeed corresponds to an existing variety. Darwin believes that some kind of mathematical tool could then be used to count the varieties, but he has not enough mathematical background to do so.

Now that you are really impressed by Darwin's work, it is your turn: impress him by writing a program that counts the number of varieties of that species.

Kiara does not know the real graph $$$\mathcal{G}$$$ governing the flight of these birds but, in her previous field study, Kiara has collected data from the journey of many birds. Using this, she has devised a graph $$$\mathcal{P}$$$ explaining how they move. Kiara has spent so much time watching them that she is confident that if a bird can fly directly from $$$a$$$ to $$$b$$$, then she has witnessed at least one such occurrence. However, it is possible that a bird flew from $$$a$$$ to $$$b$$$ to $$$c$$$ but she only witnessed the stops $$$a$$$ and $$$c$$$ and then added $$$( a, c )$$$ to $$$\mathcal{P}$$$. It is also possible that a bird flew from $$$a$$$ to $$$b$$$ to $$$c$$$ to $$$d$$$ and she only witnessed $$$a$$$ and $$$d$$$, and added $$$(a, d)$$$ to $$$\mathcal{P}$$$ , etc. To sum up, she knows that $$$\mathcal{P}$$$ contains all the edges of $$$\mathcal{G}$$$ and that $$$\mathcal{P}$$$ might contain some other edges $$$(a, b)$$$ for which there is a path from $$$a$$$ to $$$b$$$ in $$$\mathcal{G}$$$ (note that $$$\mathcal{P}$$$ might not contain all such edges).

For her next field study, Kiara has decided to install her base next to a given tree $$$T$$$. To be warned of the arrival of birds on $$$T$$$, she would also like to install detectors on the trees where the birds can come from (i.e. the trees $$$T'$$$ such that there is an edge ( $$$T', T$$$) in $$$\mathcal{G}$$$ ). As detectors are not cheap, she only wants to install detectors on the trees $$$T'$$$ for which she is sure that $$$( T', T)$$$ belongs to $$$\mathcal{G}$$$.

Kiara is sure that an edge $$$(a, b)$$$ belongs to $$$\mathcal{G}$$$ when $$$(a, b)$$$ is an edge of $$$\mathcal{P}$$$ and all the paths in $$$\mathcal{P}$$$ starting from $$$a$$$ and ending in $$$b$$$ use the edge $$$(a, b)$$$. Kiara asks you to compute the set $$$S( T )$$$ of trees $$$T'$$$ for which she is sure that $$$(T', T)$$$ is an edge of $$$\mathcal{G}$$$.

In order to kill time, you devised a little game. The wetland is represented by an $$$N \times N$$$ grid made of 3 types of squares: firm ground, wet zone, and protected zone.

Connected wet zone squares form wet areas, which are maximal sets of wet zone squares such that we can go from any square of the area to any other square of the area by a path of connected wet zone squares. Two squares are considered connected when they share one edge, so that squares not on the border of the grid are connected to 4 other squares. Each wet area must be connected to both the left and right sides of the grid, and does not contain more than $$$2N$$$ wet zone squares. Two wet zone squares that belong to two different wet areas will always be at distance at least 3 from each other, the distance being counted by moving horizontally or vertically on the grid. For example, in the two examples below, the blue squares are at distance 3 from one another.

One after the other, you and your friend will each take turns placing a camera on the wetland with the following constraints:

• The camera must be on a firm ground square.
• The camera must be adjacent to a wet zone square so that you can take bird photos.
• The camera must not be on a protected zone square.
• There cannot be two cameras on the same square.
• No two cameras adjacent to the same wet area can be adjacent (again, the notion of adjacency means sharing an edge).

The first player who cannot place a camera anymore loses the game. Assuming both players play optimally, will the first player win or lose?