Alice and Bob are playing a friendly game of ping pong. The game consists of several rounds. At the end of each round, exactly one player gets one point. The first player to 11 points wins. When that happens, the game immediately ends. Alice start serving the first round, then Bob serves for the next two rounds, then Alice serves twice, then Bob serves twice, and so on.

At any time in the game, the current score is written $$$X$$$-$$$Y$$$, where $$$X$$$ is the number of points of the player who is currently serving, and $$$Y$$$ is the number of points of the other player. This constant switching of the scores back and forth can be a little bit error-prone. Eve is the umpire, and she wrote down a log of the current scores at a few different times during the game. But since Eve is a bit unreliable, you worry that she wrote down the wrong scores. Write a program which, given the list of scores Eve wrote down, checks whether or not this list of scores can appear in an actual game.

Berry picking is hard work, but also a peaceful and relaxing experience. After a long day of picking, it is common to see nothing but berries once you close your eyes to sleep. As your mind drifts into unconciousness, the berries will start living their own life and create all kinds of absurd scenarios.

You are given a tree with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. Initially, there is one berry in each vertex. There is also one ant in each vertex, guarding the berries. When picking the berry at vertex $$$v$$$, all the ants that are on different vertices will walk one step towards $$$v$$$. The ants already at $$$v$$$ will stay where they are. Note that since the graph is a tree, there is always one unique path the ants will take.

Your goal is to pick all the berries in the tree. The ants are no danger to you as long as they stay separated. But if at any point all the $$$n$$$ ants end up in the same vertex, they will attack you. Find a permutation of the vertices, so that if you pick the berries in that order, all the ants will not end up in the same vertex.

Jonna is a university student who attends $$$n$$$ lectures every day. Since most lectures are way too simple for an algorithmic expert such as Jonna, she can only stay awake during a lecture if she is drinking coffee. During a single lecture she needs to drink exactly one cup of coffee to stay awake.

Some of the lecture halls have coffee machines, so Jonna can always make sure to get coffee there. Furthermore, when Jonna leaves a lecture hall, she can bring at most two coffee cups with her to the following lectures (one cup in each hand). But note that she cannot bring more than two coffee cups with her at any given time.

Given which of Jonna's lectures have coffee machines, compute the maximum number of lectures during which Jonna can stay awake.

You live in the Disc District of Flatland and work for the Nearest Convenient Plot Company (NCPC). Your job is to find the nearest convenient plot of land outside of the Disc District to build on.

The Disc District can be described as a disc on a plane with center $$$(0, 0)$$$ and some radius $$$r$$$. So a point is outside of the Disc District if the (Euclidean) distance from it to the origin is strictly larger than $$$r$$$. A point $$$(x, y)$$$ on the plane is a convenient plot if $$$x$$$ and $$$y$$$ are integers.

Your friend Cajsa had a graph with $$$n$$$ vertices, and she needed to find its shortest cycle. To do this, she just took a random sequence of vertices and luckily this happened to be a shortest cycle. "What are the odds?", she asked herself and wrote another program to calculate this probability.

To do this, Cajsa needed an algorithm to count the number of shortest cycles in a graph. She uses a homemade randomized algorithm that runs in $$$\mathcal{O}(1)$$$. But you suspect that this algorithm is incorrect, because surely it would have to consider every vertex of the graph (right?). You think that Cajsa's algorithm just prints random numbers that happen to be correct on some small graphs.

In response to these doubts, Cajsa generated a bunch of graphs, and challenges you to check that her answers are correct.

You are given an undirected graph with $$$n$$$ vertices and $$$m$$$ edges, and your task is to count the number of shortest cycles in it.

A cycle in a graph is a path of distinct vertices where, additionally, there is an edge between the first and last vertices of the path. Two cycles are considered distinct if they don't consist of the same set of edges. Thus the cycles $$$3, 1, 2$$$ and $$$3, 2, 1$$$ are the same, and the cycles $$$1, 2, 3$$$ and $$$2, 3, 1$$$ are considered the same.

You are on vacation in a foreign country. This country has a local football league, and you don't know any of the team names. However, you have found a table of all the results from this season, and next to every match is the concatenated names of the two teams that played.

There are $$$n$$$ teams in total, named $$$s_1, s_2, \cdots, s_n$$$. You are given the concatenation $$$s_i+s_j$$$ for every ordered pair $$$i \neq j$$$. Find the teams names $$$s_1, s_2, \cdots, s_n$$$. Team names must be nonempty, but they do not need to be distinct.

Gustav is studying to become an interpreter. In this line of work, knowing several languages is a must, and Gustav is already fluent in French, Mandarin, Nahuatl and even Finnish. But there is one language that Gustav struggles with: Norwegian. Before Gustav can graduate, he must complete the infamous Norwegian Conclusive Proficiency Check.

This exam consists of $$$n$$$ yes/no questions. Answering correctly gives $$$+1$$$ point, answering incorrectly gives $$$-1$$$ point, and not answering gives $$$0$$$ points. To pass the exam, at least $$$k$$$ points are needed. For each question, Gustav has a guess that he knows is correct with probability $$$p_i$$$ ($$$0.5 \leq p_i \leq 1$$$). Note that $$$p_i \geq 0.5$$$, because otherwise guessing the opposite would be better.

What is the maximum possible probability of passing the exam, assuming we carefully choose which questions to answer and which ones to leave unanswered? Note that unlike a programming contest, the exam does not have instant feedback. So Gustav will answer the questions, hand in his answers, and only later be told the results.

Sweden may not have a particularly impressive mountain range compared to other NCPC countries such as Norway and Iceland, but at least it beats the flatlands of Denmark. The situation is not so clear when comparing other member countries though. For example, is Estonia more mountainous than Lithuania (Yes, but not by much! The highest point in Lithuania is Aukštojas Hill, $$$293.84$$$ meters above sea level, while Estonia has the highest peak in the Baltics: Suur Munamägi is $$$318$$$ meters above sea level.)? To settle this question, you want to determine which of the two countries has the most impressive mountain peak.

A mountain range is defined by sampling the heights $$$h_i$$$ of $$$n$$$ equidistant points. Within a mountain range, we call a triple of indices $$$1 \le i \lt j \lt k \le n$$$ a peak if $$$h_i \leq \cdots \leq h_j \geq \cdots \geq h_k$$$. The height of a peak is defined as the smaller of $$$h_j - h_i$$$ and $$$h_j-h_k$$$.

Given a mountain range, can you find the height of its highest peak?

It is a harsh and cold winter, in a town consisting of $$$n$$$ houses. Everybody is asleep in the early morning hours. The snow lies deep on the ground, except on the $$$m$$$ roads that connect some pairs of houses. Only Thomas is awake.

Thomas the mailman needs to deliver mail to each of the $$$n$$$ houses in the town. The houses are numbered from $$$1$$$ to $$$n$$$. Thomas will start in his own house (house $$$1$$$), and then visit all the other houses in some order. He can use a bicycle to get between two houses connected by a road, and he can use skis if there is no road between the houses. But it is not possible to use skis on roads and the bicycle outside of roads. Switching between bicycle and skis is tedious, so Thomas would like to do this at most once.

Your task is to find an ordering $$$a_1, a_2, \cdots, a_n$$$ of the $$$n$$$ houses so that $$$a_1 = 1$$$, and there is at most one index $$$i$$$ ($$$2 \leq i \leq n-1$$$) such that either

1. $$$a_{i-1}$$$ and $$$a_i$$$ are connected by a road, but $$$a_i$$$ and $$$a_{i+1}$$$ are not, or
2. $$$a_{i-1}$$$ and $$$a_i$$$ are not connected by a road, but $$$a_i$$$ and $$$a_{i+1}$$$ are.

You are MALL-E, the mall scooter scooper robot. Your job is to fetch all the misplaced mall scooters at the end of the day and return them to the scooter depot. The mall is an infinite grid, containing $$$n$$$ scooters that need to be returned. You can move in one of four directions: up, down, left, or right, and each move takes one second. If you move to a location that contains a scooter, that scooter moves to the next location in the same direction you were moving. If a scooter moves into a location that contains another scooter, the same thing happens, so there is never more than one scooter at each location and you never occupy the same location as a scooter. If a scooter moves to the scooter depot, it disappears. However, the robot can freely move over the scooter depot.

The mall will soon open. You need to find a way to get all the scooters to the depot in at most $$$10^5$$$ seconds.

Katrín and her friends are university students, and they go to a seminar every week. At the start of each seminar, the professor divides the students into groups randomly. Katrín and her friends dislike random groups, they want to form a group together so they can chat with each other and not get to know the other students. The professor has a secret string $$$S$$$ consisting of $$$n$$$ characters on their computer. This string acts as a seed for the random group generation. When generating groups, a program manager is ran with a substring of $$$S$$$ as input. But sometimes, the professor mistypes and writes manacher instead. This will indicate that the substring is a palindrome. Maybe Katrín can use this information to predict what the group division will look like?

There is a secret string $$$S$$$ with $$$n$$$ characters in an unknown alphabet. You are given $$$q$$$ queries of two types.

• 1 l r: This means that the substring of $$$S$$$ at indices $$$l$$$ through $$$r$$$ is a palindrome.
• 2 a b x y: This means that you should determine whether the substring at indices $$$a$$$ though $$$b$$$ is equal to the substring at indices $$$x$$$ through $$$y$$$, given the information in the previous queries.