Lineup of the skybird fest.

You are the organizer of the first Global Chart Pop Concert (GCPC), and you want to find a good lineup for your festival to become a hit.

You have already gathered a list of $$$n$$$ bands that are available to perform at GCPC and a list of $$$m$$$ people that consider going to the festival. From a quick market analysis, you know that a person will only attend the festival if at least half of their favourite bands perform. And even if they attend the festival they still watch the performances of only their favourite bands at the festival. Luckily, you have also gathered the favourite bands of each of the $$$m$$$ people during your analysis. With this information, picking a good lineup might seem trivial, but there is one last catch. A band refuses to perform if less than $$$c$$$ fans are watching since nobody likes a boring crowd.

To avoid the GCPC becoming a flop, you need to ensure that the crowd for each performing band is large enough. Obviously, a festival without any band is a complete flop.

Bilbo Baggins is finally leaving the Shire! To celebrate his departure, Gandalf plans to set up a spectacular display of fireworks across the land.

The Shire has $$$n$$$ hobbit holes numbered $$$1$$$ to $$$n$$$, each of which is occupied by exactly one hobbit. Every hole $$$i \gt 1$$$ is connected by a lane directly to a unique hole $$$p_i$$$, with $$$p_i \lt i$$$, so that following the lanes always leads towards hole $$$1$$$, the town.

Illustration of the first sample.

Gandalf must place fireworks at a minimum number of hobbit holes so that every hobbit can see at least one firework. The fireworks have a visibility range $$$k$$$. A hobbit at hole $$$i$$$ can see a firework placed at hole $$$j$$$ if it is placed at their own hole, or if $$$j$$$ lies on the path from hole $$$i$$$ to the town and the number of lanes between $$$i$$$ and $$$j$$$ is strictly less than $$$k$$$.

An unusual game of tic-tac-toe.

Your friend watched some video about Connect Four and memorized the winning strategy for the starting player. What a loser! Whatever they are saying sounds about as relevant to your life as this paragraph is to the problem statement. Apparently, someone found a weak solution to Connect Four which can be compressed to just $$$150\,\textrm{kB}$$$ and requires no game tree search.

To get them off their high horse, you challenge them to a real game. You pull out a piece of A4 graph paper and explain: "We will take turns picking any unpicked cell. The first player to get three consecutive cells in any row, column, or diagonal wins. I will start." Your friend is barely listening, but this is not just regular tic-tac-toe: you are playing on the whole paper. Convert your winning advantage.

This is an interactive problem. Your submission will be run against an interactor, which reads from the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol:

There is no initial input as you make the first move.

On each of your turns, print one line with two integers $$$r$$$ and $$$c$$$ ($$$1 \le r \le 59$$$, $$$1 \le c \le 42$$$), the row and column of the cell you pick. The cell must not have been picked before.

After each of your moves, the interactor will respond with one line with two integers $$$r'$$$ and $$$c'$$$ ($$$0 \le r' \le 59$$$, $$$0 \le c' \le 42$$$).

• If $$$r' = c' = 0$$$, the interaction is over. This happens if you won on your last move, made an illegal move, or your friend can win with their next move. Your program should terminate immediately.
• Otherwise, $$$1 \le r' \le 59$$$ and $$$1 \le c' \le 42$$$. This means that your friend picked the cell in row $$$r'$$$ and column $$$c'$$$. It is guaranteed that neither player has picked this cell before. It is now your turn again, and the interaction continues from there.

The interactor is adaptive, so your friend's moves will depend on all previous moves.

Make sure you flush the standard output after every output. For example, you can use fflush(stdout) in C++, System.out.flush() in Java, sys.stdout.flush() in Python, std::io::stdout().flush() in Rust, and hFlush stdout in Haskell.

A testing tool is provided to help you develop your solution.

The temple of Apollon in Delphi. CC BY-SA 3.0 by Inkey on Wikimedia Commons

Have you ever been walking towards someone, dodged left only to see them do the same, and then entered an awkward shuffle to pass each other? Recently, a paper published at the Greek Commerce and Procurement Conference suggested that this may have already been a common problem in ancient Greece.

Back then, there were $$$n$$$ merchant caravans that occasionally passed through the Thermopylae. When two caravans met while travelling in opposite directions, both would simultaneously choose to steer either cliffside or seaside. If they made different choices, they could safely pass each other. However, if both chose the same side, they had another opportunity to choose, repeating this process until they could safely pass. Caravans were unable to recognize each other from a distance and would each follow a deterministic strategy to decide which way to steer. Since steering seaside is much more dangerous, we say that the risk of a given strategy is defined as the total number of times it dictates to steer seaside. For example, a caravan may follow a strategy described by the sequence "cliffside, seaside, seaside, cliffside, seaside" and then only "cliffside" from then on. This strategy has a risk of $$$3$$$.

The caravans convened at the oracle in Delphi to ask for advice on which strategies they should each adopt, but this went about as well as could be expected. Rather than helping, the oracle rattled off $$$m$$$ prophecies of the following form: When caravans $$$u$$$ and $$$v$$$ meet, they will awkwardly steer in the same direction exactly $$$t$$$ times before safely passing each other by steering in opposite directions on their $$$(t + 1)$$$th attempt.

The real strategies were lost to history, but you wonder how risky they must have been. You think it is unwise to go against the oracle (this has ended poorly in the past) and want to minimize the overall risk, defined as the sum of the risks of all individual strategies.

Map of the square and stationary earth. Public Domain by Prof. Orlando Ferguson on Wikimedia Commons

You are the famous explorer Christopherus Columb and unlike most of your contemporaries you know that the earth and the world is flat and a perfect square. While others dreamfully deluded themselves with the fanatic heliocentric gospel that the earth orbits the sun, you in your superior wisdom discerned the higher truth of egocentrism: you alone remain, naturally, at the center of the world.

The only lifetime achievement remaining, worthy of your name, is to determine the exact area of the world. You cannot sail to the edge of the world yourself, as the world moves along with you such that you continue to be the center of the world. Therefore, you have to send your subordinates. They sail in a straight line direction chosen by you, starting at the center of the world. After their return, they will report the distance from you to the edge of the world in that direction.

As most crew members have been lured away by the heretic masses, there are only enough crew members left to operate a single ship. Knowing that there is barely enough time to send this ship out twice, are you wise enough to determine the area of the world?

Visualization of the two test cases used for the sample interaction. In the second sample (right), the ship is first sent in direction $$$(1, 2)$$$, where it finds the edge of the world at $$$\approx (1.33, 2.67)$$$, reporting distance $$$\approx 2.98$$$. Then the ship is sent again in direction $$$(1, 1)$$$, finding the edge at $$$(2, 2)$$$, reporting distance $$$\approx 2.83$$$.

Note that the rotation of the world square can be arbitrary, and the corner coordinates of the world do not have to be integer.

This is an interactive problem. Your submission will be run against an interactor, which reads from the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol:

The interactor first sends one line with an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$), the number of test cases.

For each test case, you can ask at most two queries.

For every query, output "? $$$x$$$ $$$y$$$" ($$$0 \leq \left| x \right|$$$, $$$\left| y \right| \leq 50, (x, y) \neq (0, 0)$$$), where $$$x$$$ and $$$y$$$ are integers, and $$$(x, y)$$$ is the direction you send a ship to.

The interactor will respond to each query with one line containing a real value $$$d$$$ ($$$0 \lt d \leq 50$$$), the distance the ship reported. This distance $$$d$$$ is given with exactly $$$10$$$ decimal places, and has an absolute and relative error of at most $$$10^{-7}$$$.

After up to two queries, you should output "! A", where $$$A$$$ is an integer, the area of the square. It is guaranteed that the square always has a positive integer area.

The interactor is not adaptive: the borders of the world are fixed before the first query.

Make sure you flush the standard output after every output. For example, you can use fflush(stdout) in C++, System.out.flush() in Java, sys.stdout.flush() in Python, std::io::stdout().flush() in Rust, and hFlush stdout in Haskell.

A testing tool is provided to help you develop your solution.

Picture of a GCPC courier. They are extremely discreet.

Got a job for you. This shady business called Guaranteed Clandestine Private Couriers is trying to hide something. Their public filings and tax records are spotless. As clean as a doctor's hands just before surgery. And you know what that means. They had dirt to scrub off, I'm sure of it. Got my hands on one of their drivers' delivery schedules. You know, a list of tasks to discreetly pick up and deliver an item. I bet we find something off with the schedule. Maybe an item that is picked up but never delivered. Maybe a delivery of something with no records where it came from. Heck, they might even list an item for some task long after the item has been delivered to keep the actual cargo off the books. Anyway, find out if the schedule is legit. If each item mentioned in the schedule is picked up and delivered exactly once, then the guy who cooks their books must be a genius. Guess they are paying him well. Speaking of, this one's double your regular fee. Half upfront for your discretion and the rest when I have your report. Don't call unless you're done!

After an extremely tiring day at work, Tessa arrived home to find her husband waiting proudly at the door. With a huge smile on his face, he announced that he had planted all her flowers in the garden. Grateful that her husband had taken some work off her shoulders, she went straight out to the garden. Her relief lasted exactly until she reached it.

While he did indeed manage to plant all of her flowers around the edge of the garden, unfortunately, the arrangement was very wrong. Roses stood where the orchids should have been. Hyacinths, dahlias, and chrysanthemums were scattered among the hydrangeas. The whole garden looked as though a toddler had planted them.

Tessa stared at the numbered tags still tied to the stems. She had arduously labelled every single flower with non-decreasing labels from left to right of the intended order. Flowers of the same species had matching tags since the order within one type of flower did not matter.

Her husband followed her gaze to the labels, shrugged, and said he thought that they were price tags and had not paid any attention to them ...

Visualization of the second sample answer.

Sighing, she settled down and decided to fix this mess. Since the flowers were still very young and delicate, she cannot just dig out some of the flowers, rearrange them, and then plant them back. Instead, she can do the following operation:

• She chooses an integer $$$m$$$ and a sequence of $$$m$$$ distinct integers $$$p_1, \dots, p_m$$$.
• First, she picks the flower at position $$$p_1$$$ and moves it back into a flowerpot.
• Then, she repeatedly chooses the flower at position $$$p_i$$$ ($$$i \geq 2$$$), and moves it to the now empty position $$$p_{i-1}$$$ of the previous flower.
• Finally, after $$$m-1$$$ iterations of the previous step, she finishes the operation by replanting the potted flower at the remaining empty position $$$p_m$$$.

Determine the minimum number of operations Tessa has to do to fix the arrangement, and output one possible sequence of these operations.

Hitster is a tabletop game about placing songs into an ordered timeline by guessing their release year. As a longtime member of the Companionless Playing Card Games (CPCG) association, Harper has access to a single-player variant of Hitster. The rules are similar to regular Hitster. Harper starts with an empty timeline. In each round of the game, she draws a card which contains only a QR code on its front. She scans the QR code to listen to the song and afterwards guesses the release year of the song. Afterwards, she turns the card to reveal the song's true release year. Suppose that the true year is $$$a$$$ and she guessed $$$b$$$. If Harper's timeline does not yet contain a song with a true release year that is strictly between $$$a$$$ and $$$b$$$, she adds the card to her timeline.$$$^{\text{∗}}$$$ Otherwise, she discards the card.

Harper just had a lengthy playthrough of the entire deck of $$$n$$$ cards. Despite her thorough knowledge of music, her final timeline is shorter than she expected. Playing a second time now would be boring because Harper remembers the correct year of all the songs, along with her not-so-correct guesses.$$$^{\text{†}}$$$ Surely, she was just unlucky with the order in which she drew the cards, she thinks. To confirm her suspicion, Harper turns to probability theory. Suppose that the same cards are presented in an order drawn uniformly at random from the set of all $$$n!$$$ permutations. What is the expected length of Harper's final timeline if she repeats her guesses from her last playthrough for all of the $$$n$$$ songs?

Visualization of a playthrough of the game with the cards of Sample 3 presented in the order of the input. Harper's timeline is shown at the bottom. After the third round, her final timeline contains two cards. The top right of each round shows the back of the card, which Harper cannot see before making her guess.

You recently started to go running in your free time. You got the shoes, you got the tracking app, and you even picked up your first injury a couple of days ago. Overall, you are really starting to like this new hobby of yours.

So far, your training routine was to run from your office to your home along the streets of your town. The town consists of $$$n$$$ intersections, numbered from $$$1$$$ to $$$n$$$, which are connected by $$$m$$$ bidirectional streets of equal length. Your office is located at intersection $$$1$$$, and your home is at intersection $$$n$$$.

As the computer scientist you are, you were of course following a shortest path. However, studies indicate that you should not just train to complete the same route in a faster time, but also to complete longer routes. Given that the last time you experimented with new training methods did not go so well, you want to take this new approach slowly. Therefore, you are looking for a route from your office to your home that is exactly one street longer than your current route. To keep the run interesting, you also want to avoid visiting any intersection more than once. Determine whether such a new training route exists.

Visualization of a possible new training route in the first sample.

Patrol pair with shield and spear. Public Domain on publicdomainvectors (edited).

Arya, the Commander of Gil'ead, has received $$$2 \cdot n$$$ new recruits. Since the Gil'ead City Protectorate Council has mandated more patrols, she intends to pair them into $$$n$$$ pairs to patrol the area. To maximize the effectiveness of a patrol pair in the modern era, it should consist of one shield bearer and one spear carrier.

Each recruit $$$i$$$ has shield-defense skill $$$d_i$$$, and spear-attack skill $$$a_i$$$. While skilled usage of their respective tool is important, one should never neglect the effectiveness of strong synergy. Because of long-standing rivalries between cities, strong bonds have formed within each city. With enough discipline, Arya is sure that there will not be any bad blood within a pair, but if both are from the same city, they will synergize exceptionally well.

The total fighting strength of a pair is the sum of the shield-defense skill of one, the spear-attack skill of the other, and if both recruits are from the same city $$$c$$$, also a synergy bonus of $$$c$$$.

Determine the maximum sum of fighting strength over all pairs that Arya can achieve with optimal pairing.

A cow. CC BY-SA 3.0 by Kim Hansen on Wikimedia Commons

Farmer Kiki has $$$42$$$ cows. Their field can be thought of as a grid where each cell is a square with a side length of one metre. According to strict regulations of the German Cow Perimeter Conglomerate, the cows must graze on a fenced area that is exactly $$$a$$$ square metres large.

Unfortunately, Farmer Kiki's supplier messed up their order of fence pieces. Instead of mostly straight fence pieces and just a few corner fence pieces, they only received an enormous amount of corner fence pieces. There are even more pieces than would fit on the field. One corner fence looks like this:

....
.O#.
.#..
....

Here 'O' denotes the center of the fence, '#' denotes the sides of the fence, and '.' denotes empty space.

Farmer Kiki can rotate and move each corner fence grid-aligned. How may they place them such that there is a side-connected component of exactly $$$a$$$ empty cells that is surrounded by fence pieces? More exactly, for each interior cell of that component all four orthogonal neighbours have to either also be an interior empty cell or part of a fence piece.

Farmer Kiki's field is $$$100 \times 100$$$ cells large and they cannot place any fence piece outside this area.

Two valid and one invalid construction for the first sample with fenced area $$$4$$$. The left construction represents the given sample answer. On the right, the four interior cells are not side-connected.

Ornament from a 1923 magazine. Public domain on Wikimedia Commons by an anonymous author.

Hannah's favourite leisure activity is to write poems. She particularly likes to write about the small things in everyday life and about neat patterns. For example, she enjoys to write poems utilizing palindromes, since her name is also one! A palindrome is a string which is equal to its reverse, ignoring the letter cases.

However, she would like to introduce a small twist. In the grocery store, she was in the fruit section. When she was about to take a banana, she realized the word consists of the letter 'b', followed by the palindrome 'anana' of length 5. Her whole life, she has played around with palindromes, but never with words containing them.

At home, she immediately started to think of interesting words containing palindromes. Given two lengths $$$n$$$ and $$$k$$$, she would like to find a method that constructs a string of length $$$n$$$, whose longest palindromic substring is of length $$$k$$$. A substring of a string $$$s$$$ is a sequence of consecutive characters of $$$s$$$.

For now, she does not care about whether the string this method provides is an actual word in the dictionary, and any string will suffice.

Mia and Mark both own a chandelier, each of which has $$$n$$$ candleholders. After the installation, Mia wonders whether she can hide a part of the room behind a vertically placed mirror for a magic trick. Of course, the mirror should be placed such that Mark would not notice its existence. She believes that she can ensure that Mark will not be able to see her or himself in the mirror, and that she can use clever lighting to hide any possible weirdness resulting from mirroring the room's walls. What worries her most are the chandeliers. Mark knows the precise positions of all the candleholders and would immediately notice if the chandelier in the mirror looked different from the chandelier behind the mirror he expects to see. Naturally, all candleholders of one chandelier should lie on one side of the mirror, and all candleholders of the other chandelier on the other side.

Illustration of the third sample.