You take your laptop out and try to plug it in when you notice that the only socket is already in use. Your friends smirk and reply: "No socket for you, no training for us". Their smirks quickly fade as you pull out a power strip, unplug the charger from the socket, and plug it back into the power strip. Now, there is enough space for your charger as well.

Figure A.1: Illustration of Sample Input 2. The first six chargers can be plugged in as shown. Note that this is not the only possible solution. However, it can be shown that it is impossible to plug in all seven chargers.

However, as soon as more sockets are available, your friends suddenly take out more devices that need to be charged. You realize that you will not get them to train like this, so you decide to trick them into solving a problem instead.

Your power strip comprises a row of $$$s$$$ sockets, and each socket is $$$3\ \text{cm}$$$ in diameter. Furthermore, as you examine the chargers, you notice that they all have integer lengths. The plug of each charger is always on one of the two ends, and each charger can only be used in two orientations. Chargers cannot overlap, but can touch, and can extend beyond the end of the power strip as long as they are plugged in to a socket. Now you challenge them to charge as many devices as possible. This is visualized in Figure A.1. Hoping that this allows them to avoid the training, your friends agree to write a program to solve this.

Bob the Builder is tired of building tiny houses and paving narrow roads, and he strives for something bigger. The new job given to him by a very eccentric client is exactly what he needs: He is tasked with building a wall of a certain width that is infinitely high! His client assured him that he does not need to worry about the building material, and that an infinite supply of various kinds of bricks has already been ordered for him. Of course, building a stable wall takes very careful planning, especially if it is supposed to be infinitely high. In particular, a wall is only stable if no two gaps between bricks in consecutive rows end up directly above each other, as shown in Figure B.1. Bob knows from his long-time experience that if it is possible to build such a wall, then it can be done by alternating just two row configurations.

Figure B.1: On the left, we see an unstable wall using the brick types of Sample Input 1. On the right, we see a stable wall using the same brick types. Note that even though only two rows of the wall are shown, it is possible to build an infinitely high wall by repeating these two row configurations.

Bob is terribly excited about the new job and quickly goes to work. Given the types of bricks available, is it possible to build a stable wall of width exactly $$$w$$$ and infinite height? If yes, how should Bob build it using only two alternating row configurations?

A family playing Musical Chairs. CC BY-SA 3.0 by Artaxerxes on Wikimedia Commons

In a deterministic version of Musical Chairs, there are $$$n$$$ chairs placed in a circle.

The chairs are numbered from $$$1$$$ to $$$n$$$ in clockwise order. Initially, the $$$i$$$th player sits on the $$$i$$$th chair. During the game, the game master gives commands to all players at once.

The first type of command tells each player to move $$$x$$$ chairs farther in clockwise order, so they must move from chair $$$i$$$ to chair $$$i+x$$$.

The second type of command tells each player to move from chair $$$i$$$ to chair $$$i\cdot{}x$$$. Both these calculations are done modulo $$$n$$$, where a remainder of $$$0$$$ corresponds to chair $$$n$$$.

If two or more people want to move to the same chair, then the player needing to travel the least in clockwise direction to reach the chair gets to take the seat, and the other players trying to reach the same chair are out of the game. This is illustrated in Figure C.1, where the larger circles represent the chairs and their numbers are written on their inside. The smaller circles represent the players. The next command (* 10) tells player $$$10$$$ (now on seat $$$11$$$) and player $$$4$$$ (now on seat $$$5$$$) to move to chair $$$2$$$. However, since player $$$10$$$ needs to travel less, this player gets to take the seat. Note that the other $$$10$$$ players will also move to some other chairs, but this is omitted from the figure for the sake of readability.

Figure C.1: Illustration of Sample Input 1 at the fourth command, where players $$$4$$$ and $$$10$$$ need to move to chair $$$2$$$. Because player $$$10$$$ needs to travel less in clockwise direction, this player gets to take the seat.

The jury wasted most of their free time designing this game and now need to go back to work. Fortunately, the game is deterministic, so you can play the game without the help of the jury.

You do not need to know the original game, but you can try to play it after the contest is over.

A filled agenda.

The NWERC is coming up and your agenda is filling up with meetings. One of your teammates wants to plan a meeting, and asks for your input. However, instead of asking you for your exact agenda, you have to fill out two separate polls: one for indicating which days you are available, and one for the hours!

As a computer scientist, you plan your meetings only on whole hours and each meeting takes an integer number of hours. Therefore, your agenda can be modelled as a matrix of $$$7$$$ rows (days), and $$$24$$$ columns (hours). Each cell in this matrix is either '.' or 'x', meaning that hour of that day you are either free or have a meeting, respectively.

You have to pick at least $$$d$$$ days in the first poll and $$$h$$$ hours in the second poll, and we assume the meeting will take place on any of your picked hour/day combinations with equal probability. What is the probability that you can attend the meeting if you fill in the polls optimally?

Image by callmetak on Freepik

In her spare time, Zoe develops an online calculator. Unfortunately, the calculator was targeted by a denial-of-service attack last week. The attacker created a lot of integer variables, exponentiated them with each other, and tried to do a bunch of comparisons. The huge integers were too much for the server to handle, so it crashed. Before Zoe fixes the issue, she decides to actually perform the calculations that the attacker requested.

There are $$$n$$$ integer variables $$$x_1, x_2, \dots, x_n$$$. At the start, each variable is set to $$$2023$$$. You have to perform $$$m$$$ instructions of the following two types:

• Operations, of the form "! $$$i$$$ $$$j$$$", where $$$i \neq j$$$. This means that $$$x_i$$$ gets set to $$$x_i^{x_j}$$$.
• Queries, of the form "? $$$i$$$ $$$j$$$", where $$$i \neq j$$$. This means that you should print '>' if $$$x_i$$$ is greater than $$$x_j$$$, '=' if $$$x_i$$$ is equal to $$$x_j$$$, and '<' if $$$x_i$$$ is smaller than $$$x_j$$$.

Consider the first sample. After the $$$5$$$ operations, the values of the variables are:

$$$$$$ x_1=\left({2023}^{2023}\right)^{{2023}^{2023}},\, x_2=\left({2023}^{{2023}^{2023}}\right)^{2023},\, x_3={2023},\, x_4={2023}^{2023}. $$$$$$

You are travelling through the galaxy in your spaceship. There are $$$n$$$ planets in the galaxy, numbered from $$$1$$$ to $$$n$$$ and modelled as points in $$$3$$$-dimensional space.

You can travel between these planets along $$$m$$$ space highways, where each highway connects two planets along the straight line between them. Your engine can accelerate (or decelerate) at $$$1\ \text{m/s}^2$$$, while using fuel at a rate of $$$1$$$ litre per second. There is no limit to how fast you can go, but you must always come to a complete standstill whenever you arrive at the planet at the end of a highway.

It is possible for a highway to pass through planets other than the ones it connects. However, as your spaceship is equipped with special hyperspace technology, it simply phases through these obstacles without any need of stopping. Another consequence of using this technology is that it is impossible to jump from one highway to another midway through: highways must always be travelled in full.

Figure G.1: Illustration of Sample Input 1, showing highways in blue, and a route from planet $$$1$$$ to planet $$$3$$$. The green start of a highway indicates acceleration, and the red end indicates deceleration.

You need to fly several missions, in which you start at your home planet (with number $$$1$$$) and need to reach a given target planet within a given time limit. For each mission, determine whether it can be completed, and if so, find the least amount of fuel required to do so. As an example, Figure G.1 shows the optimal route for the second mission of the first sample.

Captchas are getting more and more elaborate. It started with doing simple calculations like $$$7 + 2$$$, and now, it has evolved into having to distinguish chihuahuas from double chocolate chip muffins.

To combat the rise of smarter bots, the Internet Captcha Production Company (ICPC) has outdone itself this time: given a distorted image containing many integers, find the maximum value that can be expressed using each of the given integers exactly once, using addition, multiplication, and arbitrary parentheses.

After unsuccessfully trying to solve such a captcha for an hour straight, Katrijn is terribly frustrated. She decides to write a program that outputs a valid arithmetic expression with maximal value.

On a small island far far away, a handful of old men live isolated from the rest of the world. The entire island is divided into plots of land by fences, and each old man owns a single plot of land bounded by fences on all sides. (The region outside all fences is the ocean.) Each of the inhabitants needs fish to survive and the only place where they can fish is the ocean surrounding them. Since not every plot of land is connected to the ocean, some of the men might need to pass through the land of others before being able to fish. The men can cross a single fence at a time, but cannot go through fenceposts or locations where fences intersect.

Unfortunately, the old men are greedy. They demand one fish each time a person wants to enter their land. Since they do not want to lose too much fish to the others, every old man chooses a route that minimizes the number of fish he has to pay to get to the ocean.

Over the years, this has led to rivalry between the old men. Each man hates all other men who have to pay less than him to reach the ocean. Two men only like each other if they have to pay the same amount of fish to reach the ocean.

Figure I.1: Illustrations of the first three Sample Inputs. In Sample Input 1, every man has direct access to the ocean, so they all like each other. In Sample Input 2, there does not exist a pair of neighbours who like each other, because the man living in the middle needs to pay one fish, whereas all of his neighbours do not have to pay any fish to reach the ocean. In Sample Input 3, there are six men, some of whom are friendly neighbours.

The natural question which now occurs is: are there some old men on this island who are neighbours (owning land on opposite sides of a single fence) and like each other? See Figure I.1 for two islands with opposite answers to this question.

You may know that in the 17th century, a group of Dutchmen founded a settlement called New Amsterdam on Manhattan Island that later went on to become New York City. Less well-known is the story of another group of Dutchmen that also moved over to America and founded a city called New Delft. Like its bigger counterpart, New Delft has been built on a grid made up of two sets of parallel streets that meet each other at a perpendicular angle.

Some stroopwafel bakeries have already been built in New Delft, but none of the streets have been constructed. Your task is to lay out the grid of streets. For this, you need to decide on an orientation for the grid so that there are two orthogonal directions for the two types of streets. Once the orientation is fixed, you may build arbitrary streets, as long as each of them has one of the two given directions, as shown in Figure J.1. Each street can be traversed in either direction.

Figure J.1: Illustration of Sample Input 2 with a possible street layout that gives the shortest possible path that visits all bakeries in some order.

The street layout should be created in an optimal way for the annual Stroopwafel Run. This is an event in which a group of runners visits all the bakeries in some order of their choosing, and they may start and end their run at any point in the city. Your task is to come up with a grid layout that makes this shortest path as short as possible.

In traditional Dutch clog dancing, you as the dancer need to follow a very specific sequence of movements. The dance takes place on a square grid of square tiles, and at the start of the dance you stand on the top left corner tile of the grid. You then alternate between two types of dance move, moving from tile to tile in the grid for as long as you want. Your first move may be of either kind, but after that you need to strictly alternate between the two kinds of moves.

Both moves are similar to knight moves in chess: in the first type of move, you go from your current square to a square that is $$$a$$$ tiles away along one axis of the grid and $$$b$$$ tiles away along the other axis. Similarly, in the second type of move, you need to move $$$c$$$ and $$$d$$$ tiles along the respective axes. As you can freely swap the two axes and choose the movement direction along each axis, there can be up to $$$8$$$ ways of performing a given type of move. Figure K.1 shows an example dance routine with $$$(a,b) = (1,2)$$$ and $$$(c,d) = (2,3)$$$.

Figure K.1: Illustration of Sample Input 3, showing a dance that begins in the top left corner of a $$$4\times 4$$$ grid and ends in the bottom left corner, visiting the blue squares along the way. There are $$$13$$$ reachable squares in total. The three squares highlighted in red cannot be part of any dance performance.

Starting on the top left corner tile, how many different tiles could you reach while doing a clog dance? It is not allowed to step outside of the grid and you do not count tiles that you are simply stepping over while doing a move. Note that you need to count all tiles that can be reached during some performance of the dance, but not necessarily during the same one.

The original Battleships game, before the upgrade to a $$$100 \times 100$$$ grid. CC BY-NC 3.0 by Pavel Ševela on Wikimedia Commons

You are playing Battleships in a large ocean with large ships. More precisely, there is a large square grid of size at most $$$100\times 100$$$ and inside it are up to $$$10$$$ of the largest type of ship in Battleships – the aircraft carrier – which has a length of five tiles, placed either horizontally or vertically. The ships do not overlap, but they are allowed to be adjacent to each other. See Figure L.1 for an example.

Unfortunately, your opponent appears to bend the rules to their liking. It looks like they do not always determine the placement of their ships before you start shooting. You are not impressed by their attempt at cheating, and decide to try and win the game anyway.

Figure L.1: Illustration of Sample Interaction 1 after the first four shots were fired.

Your goal is to locate and sink all your opponent's aircraft carriers in at most $$$2500$$$ shots, that is, you must hit each of the five tiles of all their ships.

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 two integers $$$n$$$ and $$$k$$$ ($$$5 \le n \le 100$$$, $$$1 \le k \le 10$$$), the size of the grid and the number of ships. It is guaranteed that it is possible to place $$$k$$$ aircraft carriers in the grid without overlap.

Then, your program needs to start firing shots. Each shot is fired by printing one line of the form "$$$x$$$ $$$y$$$" ($$$1 \le x,y \le n$$$), indicating you shoot at position $$$(x, y)$$$. The interactor will respond with "hit" if the shot was a hit, "sunk" if the shot caused an aircraft carrier to sink, and "miss" otherwise. If you have shot the same location before, the response will be "miss".

Once you sink the last aircraft carrier, the interaction will stop and your program must exit.

The interactor is adaptive: the positions of the ships may be determined during the interaction, and may depend on where you decide to shoot.

Make sure you flush the buffer after each write.

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

Firing more than $$$2500$$$ shots will result in a wrong answer.