Colloportus is a charm that magically locks objects such that they cannot be opened manually. On the other hand, Alohomora, also known as Thief's Friend, is an unlocking charm that can open even magically locked objects. Both charms are taught in Hogwarts charms class in the first year and, by the end of the fifth year, every student should be able to cast them, as they are required in the Theory of Charms examination.

In the exam, each student is given $$$n$$$ interlocked chain links. To pass this part of the exam, you have to use the Alohomora charm to open some of the links and the Colloportus charm to interlock them again. By the end of the exam, the chain links should form a single closed chain. Ron messed up and is now left with a bunch of partially interlocked chain links and only enough time to cast both spells a single time.

More formally, Ron is able to open one chain link, change with which other chain links it is interlocked with, and then lock it again. After this, each chain link should be interlocked with exactly two other chain links to form a single closed chain. Is it still possible for Ron to pass the exam?

In his first potion lesson Snape asked Harry: "Tell me, what would I get if I added powdered root of asphodel to an infusion of wormwood?". Back then, Harry had no idea what this meant and Snape had to explain to him that this would make a sleeping potion, so powerful that it is known as Draught of Living Death.

Now is Harry's sixth-year and his new professor, Slughorn, wants him and everyone else to brew exactly this potion. To no surprise, Harry is the one to brew it best, as he is the only one who knew that the final potion should contain exactly $$$p$$$ percent of powdered root of asphodel.

After the class is over, professor Slughorn decides to mix some of his students potions together to brew a perfect Draught of Living Death himself. His class consists of $$$n$$$ students, including Harry, and each of them attempted to brew the potion. Therefore, Professor Slughorn has access to $$$n$$$ potions, each in a different cauldron. The $$$i$$$th cauldron contains $$$c_i$$$ liters of potion in total and it contains $$$p_i$$$ percent of powdered root of asphodel. How many liters of the Draught of Living Death can Slughorn brew?

On Halloween, Quirrell suddenly enters the Great Hall and claims to have seen a troll in the dungeons. The evacuation of the students into their dormitories is started immediately. At the same time, a group of teachers prepares to search the dungeons for the troll.

The dungeons were constructed over a long period of time and are a system of connected corridors. They originally consisted of just one long corridor with an entrance and an exit. Over time, new corridors were added. Each new corridor had its entrance placed on the right-hand wall of an already existing corridor and ended in the same corridor where it started, but further towards the exit. Furthermore, a newly built corridor did only intersect with the corridor containing its entrance and exit. To ensure that nobody gets lost, each corridor contains markers pointing to the corridor's exit.

Illustration of the second sample.

The teachers have a map of the dungeons and want to use the fact that there is only one exit to their advantage. They lock the exit and start all together at the entrance to the system. To ensure that all of them actually reach the exit, they agree that each of them only moves towards the exit of the current corridor or enters another corridor through its entrance. Of course, they want to avoid that the troll can leave through the entrance or even attack them from behind. Hence, they want to move in such a way that there is never a path between the entrance of the dungeons and the troll which is not blocked by some teacher. Fortunately, each teacher is capable enough to deal with the troll, that is, it is sufficient if it can be guaranteed that at least one teacher encounters the troll. How many teachers have to go to the dungeons?

The system of corridors in the dungeons can also be constructed by composition of systems of corridors. For each such system there are two positions that are defined as the entrance and the exit of the corridor, respectively.

• () denotes just one corridor with an entrance and an exit.
• (A+B) denotes that we append the system B to A, that is, the entrance of A is the new entrance of the system, the exit of B is the new exit and we merge the exit of A with the entrance of B.
• (A*B) denotes that A and B are parallel to each other. This means that the entries of A and B are merged and form the new entrance and the exits of A and B are merged as well and form the new exit.

Hermione was really proud of her one million word text she wrote for her assignment. She was, until she realized that the text must be handed in on a single piece of paper with limited dimensions. Obviously, she could have just shortened her text, but Hermione decided to go another route. She decided to just copy her text to a new piece of paper, writing a little bit smaller... To make this easier, she decided to first change the line breaks in her text such that the sum of the height and width of the piece of paper is minimized. Given Hermione's text with $$$n$$$ words and assuming that each character takes up one unit height and one unit width, what is the minimal height plus width that can be achieved by inserting line breaks? Note that two words which are on the same line need to be separated by a single space.

In the Wizarding World, Arithmancy is the study of numbers and their magical properties, and it is also Hermione's favourite class at Hogwarts. She is currently studying for the final exams, the Nastily Exhausting Wizarding Test (N.E.W.T.), using last year's exam questions.

To this day, students at Hogwarts still use parchments and quills as writing material. While these have some disadvantages compared to muggles' pen and paper, an advantage is that using magically enchanted parchment allows for more quirky exam questions such as the following:

You need to find a hidden integer number $$$x$$$ between $$$1$$$ and $$$100$$$, inclusive. Up to $$$50$$$ times you may write an integer number $$$y$$$ on the provided piece of parchment. For each number you write, one of the following four words will appear next to it:

• equal, if you found the correct number;
• factor, if $$$y$$$ is a divisor of $$$x$$$;
• multiple, if $$$y$$$ is a multiple of $$$x$$$;
• other, if none of the above is true.

We decided to reuse this N.E.W.T. question as a problem for Winter Contest 2022. Unfortunately we were not able to obtain enough magical interactive parchment in time for the contest, so that we had to convert the original question into an interactive programming problem instead.

This is an interactive problem. Your submission will be run against an interactor, which reads the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol: Repeatedly output query numbers $$$y$$$ ($$$1 \le y \le 100$$$). For each such number, the interactor replies with one of the strings equal, factor, multiple or other, as described above.

After every query you should flush the standard output to ensure that the query is sent to the interactor. For example, you can use fflush(stdout) in C++, System.out.flush() in Java, and sys.stdout.flush() in Python.

You may use at most $$$50$$$ queries and your program must exit after you found the hidden number. The interaction will be run multiple times. The hidden number $$$x$$$ is fixed in advance and will be different for each run.

A testing tool is provided to help you develop your solution. It can be downloaded from the DOMjudge problems overview page.

Inspired by some ideas from the Muggle world, a bunch of Ravenclaw students recently founded Studentbook. This is actually a book (magically enhanced, of course), which has a page for each Hogwarts student showing their recent social activities.

Every interested student can buy their own small version of this book, which shows recent activities of their friends. Unfortunately, this is not very popular at the moment, because everybody already knows what their friends are up to anyways.

One of the Ravenclaw students behind Studentbook, Michael Corner, has a plan to fix this. He wants to perform the powerful spell Amicitia, also known as the friendship spell. This spell acts permanently and does the following: If student $$$a$$$ and student $$$b$$$ are friends and student $$$b$$$ and student $$$c$$$ are friends as well, then student $$$a$$$ and $$$c$$$ will be made friends by the spell.

Michael was immediately alerted to the potentially catastrophic consequences of his plan. Due to the spell, it might happen, that more and more friendships will be formed, completely disrupting the social balance in Hogwarts.

But he does not want to abandon his idea so easily. Instead, he first wants to find out how many friendships would be formed by the spell.

The Triwizard Tournament is a contest between wizarding schools, with each school represented by a champion. At the start of the school year, students enter their names into the Goblet of Fire, which selects one champion for each of the $$$n$$$ participating schools. The school champions then face off in three magical events spread throughout the year.

For this most recent edition, the Triwizard Tournament is using the same scoring system that has been used in the sport climbing event of last year's Tokyo Summer Olympics (this is a sport where muggles compete to see who is able to climb vertical obstacle courses the fastest). After each of the three events, all $$$n$$$ champions are ranked by their scores, each receiving a rank between $$$1$$$ and $$$n$$$, inclusive. In the end, the three ranks of each champion are multiplied and the champion with the lowest score wins the cup for their school.

The first two events have already happened and the third is scheduled for tomorrow. Is it still possible for our favourite, the Hogwarts champion, to win? If yes, find a possible ranking for the third event so that this happens. As Hogwarts won the last edition of the tournament, the rules stipulate that in the event of a tie the Hogwarts champion will be declared the winner.

Harry Potter just found out that there were not only $$$7$$$ but $$$8$$$ horcruxes. The vicious Voldemort stored the last one in the middle of a desert. To protect the 8th horcruxes, vicious Voldemort cursed the desert in a way that Harry Potter can only pass it by walking the entire distance which takes him $$$d$$$ days in total. The amount of water that any person can carry while being in the desert is also limited to $$$c$$$ units. As Harry Potter cannot carry enough water by himself, he takes some of his beloved friends with him that he lured into joining the secret club Dumbledore's Army which he founded a few years back during his school time in Hogwarts.

While Harry Potter and each of his friends can carry $$$c$$$ units of water, they need to drink one unit of water per day. At the end of each day, Harry Potter can decide who of his friends will accompany him further to the middle of the desert and who has to return to the origin the next day. When travelling back, his friends use the exact same route as on their forward journey in order not to get lost. Thus, they need the same number of days they travelled so far to get back to the origin.

Harry Potter and any of his friends can pass on an integer amount of water units to any of their peers. However, if any person is sent home, he must be given enough water to reach the origin safely.

Harry Potter does not want to put his friends at danger. Therefore, it is sufficient for him if he reaches the middle of the desert alone to destroy the $$$8$$$th horcrux by himself. Once the horcrux is destroyed, it magically changes to a portkey that takes Harry Potter safely back to Hogwarts.

What is the minimum number of friends that Harry Potter needs to take with him in order to reach the middle of the desert?

Last night, Rubeus Hagrid once again visited his giant half-brother Grawp in the forbidden forest. Unfortunately, when Grawp saw Hagrid's pink umbrella, he used it to chase barbaric bowtruckles in the trees. In this chaotic chase, Grawp unfortunately broke Hagrid's umbrella into pieces. Back in his homey hood, Ruben Hagrid wants to assemble a new umbrella. In the past, he only stored the broken pieces of his wand in it. However, he recently realized that members of the non-magic community mostly use umbrellas to protect them against the rain. In order to blend in and hide his true identity whenever he goes shopping to London, Hagrid wants his new umbrella to look exactly like any other umbrella.

The umbrella should consist of a straight wooden handle with $$$8$$$ metal ribs of length $$$x$$$ meters connected symmetrically to its top. Hagrid wants to attach the remaining non-stretchable, rainproof, pink fabric he found in his hood along the full length of the metal ribs, i.e. from the top of the umbrella where all ribs meet down to the very end of each metal rib. If the umbrella is opened all the way, the fabric between two metal ribs forms a isosceles triangle. Depending on the amount of fabric that is used, the umbrella can be opened more or less wide.

Hagrid has up to $$$a$$$ square meters of non-stretchable, rainproof, pink fabric available for the umbrella. Since he is quite a corpulent man, he wonders what the maximum area is that the umbrella can keep dry if the rain falls perpendicular to the ground and there is absolutely no wind?

On their quest to destroy the horcruxes, Harry, Ron and Hermione have returned to Hogwarts to search for the Lost Diadem of Ravenclaw, which they suspect has been turned into one of these dark artifacts. It does not take long before their presence is noticed, and now the Hogwarts professors and the members of the Order of the Phoenix are shielding the castle with various protective jinxes and charms to prepare for the arrival of Voldemort and the Death Eaters.

One of the most powerful charms in their repertoire is Repello Inimicum, which creates a near impenetrable barrier that will disintegrate anything that tries to pass through it. The charm needs to be performed by $$$n$$$ wizards and witches working together. Each of them uses their wand to draw a large circle in the sky while chanting the incantation. The potency of the charm depends on the number of points where two or more of these circles touch or intersect.

For simplicity we assume that the $$$n$$$ circles that make up the charm are all drawn in the same plane. Given $$$k$$$, the number of intersections that is needed for the charm to be the most potent, find a possible arrangement of the $$$n$$$ circles so that there are exactly $$$k$$$ intersection points. Two circles touching in a point counts as a single intersection. If more than two circles intersect in some point, then that point is only counted once.

Hermione is training the Liquefacio spell which allows her to liquefy objects and living creatures. She is already quite good at liquefying books, plants, and rats, so she decided to go one step further and try to do it with her cat Crookshanks. Of course she wants Crookshanks to get back her original shape and so it is important that she does not lose one single drop of the liquid she will transform Crookshanks into.

Illustration of the first sample. The first two kettles are large enough for the cat. Since the second has less volume than the first, it is the only solution.

She therefore decided to put Crookshanks in a kettle before performing the spell, and, to stay inconspicuous, she wants the kettle to be as small in volume as possible. She asked Dobby to help her find a suitable kettle. He showed her a large selection of cylindrical kettles from the Hogwarts kitchen, and now she has to decide which one she wants to take.

During his seventh year in Hogwarts, Neville Longbottom reactivated Dumbledore's Army with Ginny and Luna, and replaced Harry as their leader in order to fight against Voldemort's takeover. As he did so often lately, this night Neville sneaked into the restricted section of the library to find new ways to inconvenience Snape and his fellow Death Eaters and Slytherins.

Among the books he discovered during his previous visit, one in particular caught his attention. It contains a spell which supposedly fixes the vanishing steps in certain staircases that had plagued Neville during his entire time in Hogwarts and are now used as an opportunity to ridicule and belittle the poor first-years more than ever. Willing to try this spell and put an end to this, he decided to take the book this time.

Luckily, the spell allows fixing all the vanishing steps in an arbitrarily long sequence of consecutive steps at once. However, the spell gets longer and longer the more consecutive steps are considered. For the spell's shortest possible form, this sequence can contain up to 32 consecutive steps. In order to increase this number, the word long can be appended an arbitrary number of times to the front of the spell, doubling the maximum number of consecutive steps every time. For instance, long long and long long long can be applied to sequences of consecutive steps of length 64 and 128, respectively.

Unfortunately, the new regime under Snape greatly strengthened the safety measures, so Neville should return the book as soon as possible so that they won't notice that someone sneaks into the restricted section and close the last remaining loopholes in their security system. Because the spell requires the casting wizard to stand close to the first step of the considered sequence, it would take too long to apply it multiple times. Furthermore, he of course wants to keep the spell itself as short as possible.

Neville already knows the sequence of consecutive steps he wants to fix using the spell and also knows which of these steps need fixing, but is not sure what the shortest sufficient form of the spell is. Can you help him?

You may know Wizard's Chess, which is a magical version of chess, but there are more magical games in the wizarding world. Another one you may recognize is Magic Marbles, which is similar to the muggle game Marble Temple. In this game, you are given a chain of differently coloured marbles $$$m$$$, which you need to destroy. To do this, you can add additional marbles to the chain. This may sound counterproductive, but if there ever is a run of at least $$$k$$$ consecutive marbles that are of the same colour, then all of these marbles magically disappear instantly. The resulting gap is closed by moving the remaining marbles closer together, which can lead to new runs that then again disappear.

The initial state of the first sample. The first marble will be added between the second yellow marble and the first blue marble. Since this results in a run of three blue marbles, all of them instantly disappear.

This year there is a great Magic Marbles tournament in Hogwarts. However, you fear that some magicians are not as sincere as you and may try to cheat in this magic tournament. Therefore, you decided to simulate the game without magic.