Welcome to the 2021 Abakoda Long Contest! All our problem stories will revolve around the various misadventures of the high school students Alice, Bob, and Cindy, who had previously appeared in a similar long contest from last year (from the same problem author!). But the executives demand a new fourth character—the freshman Dani! We don't know much about him, other than the fact that he has a mysterious past... Maybe we'll learn more about him throughout the different stories?
Unfortunately, problem stories (which we'll call episodes) can usually only accommodate at most three different characters at a time. Now that there are four characters, for each episode, we'd have to pick one of the four to be excluded from that episode's hijinks. The fans certainly didn't like that!
Because of this backlash, we won't really be seeing much of Dani, outside of the few episodes he had already appeared in... What a shame that we'll never see the resolution of his character arc...
Oh well, nothing that can be done about that. The programming task that we have is simple. You will be given the names of three characters that appeared in some episode. Identify which among the four of Alice, Bob, Cindy, Dani is missing.
Input consists of a single line containing three space-separated names from among Alice, Bob, Cindy, Dani, in some order.
Output the name of the character that was not given in the input.
$$$$$$\begin{align*}
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{50} & \text{The names in the input are given in alphabetical order.} \\ \hline 2 & \mathbf{50} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
Alice Bob Cindy
Dani
Dani is the name that does not appear in the input.
Cindy was tasked with organizing her school's sportsfest this year. In addition to normal competitions like volleyball, tug of war, and an actual basketball match, Cindy thinks that it would be exciting to start off the sportsfest with a special basketball jump shot competition.
She has chosen $$$n$$$ of her classmates to participate in the jump shot competition. There are $$$n$$$ marks on the ground (drawn in chalk), placed such that the $$$i$$$th mark is $$$x_i$$$ units away from the basket. Cindy will assign one person to each mark, and she tells each person to stand at their assigned mark. Each person will then be asked to try to shoot the ball into the basket from their respective locations. For each classmate, we know their "skill level" is some numerical value $$$c_i$$$, meaning that they will successfully land their shot if and only if they shoot from a distance of $$$c_i$$$ units from the basket or closer.
Cindy believes that the sportsfest will start with a bang if all her classmates successfully land their shot. Is it possible to assign the students to the marks in such a way that each of them successfully lands their shot?
The first line of input contains a single integer $$$n$$$.
The second line of input contains $$$n$$$ space-separated integers $$$x_1, x_2, \dots, x_n$$$, the distances of each mark from the basket.
The third line of input contains $$$n$$$ space-separated integers $$$c_1, c_2, \dots, c_n$$$, the skill levels of Cindy's classmates.
Output YES if it is possible to have every student successfully land their shot, and NO otherwise.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq x_1 \lt x_2 \lt \dots \lt x_n \leq 12345 \\ \text{$1 \leq c_i \leq 12345$} \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{25} & 1 \leq n \leq 3 \\ \hline 2 & \mathbf{25} & 1 \leq n \leq 8 \\ \hline 3 & \mathbf{25} & 1 \leq n \leq 20 \\ \hline 4 & \mathbf{25} & 1 \leq n \leq 12345 \\ \hline \end{array}\\
\end{align*}$$$$$$
3 10 15 20 28 16 18
YES
3 10 15 20 24 13 13
NO
In the first sample input, one possible configuration is to assign the first student to the third mark (because $$$28 \geq 20$$$), the second student to the first mark (because $$$16 \geq 10$$$), and the third student to the second mark (because $$$18 \geq 15$$$).
In the second sample input, none of the assignments are valid.
Cindy was tasked with organizing her school's sportsfest this year. In addition to normal competitions like volleyball, tug of war, and an actual basketball match, Cindy thinks that it would be exciting to start off the sportsfest with a special basketball jump shot competition.
She has chosen $$$n$$$ of her classmates to participate in the jump shot competition. There are $$$n$$$ marks on the ground (drawn in chalk), placed such that the $$$i$$$th mark is $$$x_i$$$ units away from the basket. Cindy will assign one person to each mark, and she tells each person to stand at their assigned mark. Each person will then be asked to try to shoot the ball into the basket from their respective locations. For each classmate, we know their "skill level" is some numerical value $$$c_i$$$, meaning that they will successfully land their shot if and only if they shoot from a distance of $$$c_i$$$ units from the basket or closer.
Cindy believes that the sportsfest will start with a bang if all her classmates successfully land their shot. Unfortunately, she wasn't able to communicate this to Bob, who just totally randomly assigned students to marks. In light of this, Cindy is instead interested in finding the exact probability that a randomly chosen assignment of students to marks will result in all her classmates landing their shot successfully.
Recall that there are $$$n!$$$ ($$$n$$$ factorial) different ways to assign students to marks. Among them, count the number of assignments that result in all $$$n$$$ people landing their shot successfully.
The first line of input contains a single integer $$$n$$$.
The second line of input contains $$$n$$$ space-separated integers $$$x_1, x_2, \dots, x_n$$$, the distances of each mark from the basket.
The third line of input contains $$$n$$$ space-separated integers $$$c_1, c_2, \dots, c_n$$$, the skill levels of Cindy's classmates.
Output a single integer, the number of assignments of students to marks such that all of them land their shots successfully. Two assignments are considered different if there exists a student that was assigned somewhere else between the two ways.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq x_1 \lt x_2 \lt \dots \lt x_n \leq 12345 \\ 1 \leq c_i \leq 12345 \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{35} & 1 \leq n \leq 3 \\ \hline 2 & \mathbf{32} & 1 \leq n \leq 8 \\ \hline 3 & \mathbf{32} & 1 \leq n \leq 20 \\ \hline 4 & \mathbf{1} & 1 \leq n \leq 12345 \\ \hline \end{array}\\
\end{align*}$$$$$$
3 10 15 20 28 16 18
2
3 10 15 20 24 13 13
0
In the first sample input, there are $$$2$$$ valid assignments. We can assign the first student to the $$$20$$$ mark, the second student to the $$$10$$$ mark, and the third student to the $$$15$$$ mark. Or, we can assign the first student to the $$$20$$$ mark, the second student to the $$$15$$$ mark, and the third student to the $$$10$$$ mark.
In the second sample input, none of the assignments are valid.
Bob wants to give Cindy a gift for Valentine's Day. Whereas others would buy storebought sweets to give to others, Bob thinks that his gift will have a greater impact if it is homemade. Bob learned that one of Cindy's favorite foods is pili nut brittle (from Camarines Sur). Even though he doesn't know how to make it, he's going to try his best! All he needs is a YouTube tutorial and a dream.
First, Bob scatters $$$n$$$ pili nuts on a silicone mat. The position of the $$$i$$$th nut can represented as an ordered pair $$$(x_i, y_i)$$$, using the standard Cartesian coordinate system (for simplicity, we model each nut as just a single point). It is possible to have multiple nuts at the same location. Then, Bob pours a molten mixture of corn syrup and sugar at the point $$$(h,k)$$$. The hot liquid flows out evenly in all directions, so we can model the liquid as a circle centered at $$$(h,k)$$$, initially of radius $$$0$$$, and whose radius grows at a rate of $$$1$$$ unit per second.
Bob will stop pouring the very instant that all pili nuts are within the hot liquid, i.e. when all points are on or within the circle. Once the mixture cools and solidifies, Bob will be left with a circular piece of pili nut brittle. What will be the diameter of this final product?
The first line of input contains three space-separated integers $$$n$$$, $$$h$$$, and $$$k$$$.
Then, $$$n$$$ lines of input follow, each containing two space-separated integers $$$x_i$$$ and $$$y_i$$$, corresponding to the location of the $$$i$$$th pili nut.
Output the diameter of the final circle of pili nut brittle. Your answer will be considered correct if it is within $$$10^{-3}$$$ of the correct answer.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline -1000 \leq h, k \leq 1000 \\ -1000 \leq x_i, y_i \leq 1000 \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{25} & n=1 \\ \hline 2 & \mathbf{25} & 1 \leq n \leq 5 \\ \hline 3 & \mathbf{25} & 1 \leq n \leq 500 \\ \hline 4 & \mathbf{25} & 1 \leq n \leq 10^5 \\ \hline \end{array}\\
\end{align*}$$$$$$
1 2 3 2 4
2.000000000000
4 0 0 -3 4 5 0 1 1 -4 -3
10.000000000000
2 1 1 0 0 2 0
2.828427124746
We illustrate the second sample input. If the molten sugar is to be poured at $$$(0,0)$$$, then here is the layout of the liquid and the pili nuts.
Alice has been adjusting to her online microbiology class really well! She has a synchronous session with her instructor every week. By far, her favorite part is at the end of the session, when everyone says, "Thank you, sir!" one after another. It gives her a small burst of well-needed wholesome energy for the week. And her teacher friends have confirmed that they really appreciate hearing it as well!
Alice noticed that some students are shier than others. There are $$$n$$$ students in her microbiology class. The $$$i$$$th student will say "Thank you, sir!" only after at least $$$A_i$$$ other students have also said "Thank you, sir!" (if $$$A_i = 0$$$, then the $$$i$$$th student says "Thank you, sir!" immediately after class ends). Alice calls this behavior decorum sensing, because these students are trying to get a feel for what is appropriate to say or do based on what everyone else is doing.
Given the values of $$$A_1, A_2, A_3, \dots, A_n$$$, find the number of students who will eventually say "Thank you, sir!"
The first line of input contains a single integer $$$n$$$.
The second line of input contains $$$n$$$ space-separated integers $$$A_1, A_2, A_3, \dots, A_n$$$.
Output a single integer, the number of students who will eventually say "Thank you, sir!"
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 0 \leq A_i \leq n \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{25} & 1 \leq n \leq 6 \\ \hline 2 & \mathbf{25} & 1 \leq n \leq 100 \\ \hline 3 & \mathbf{25} & 1 \leq n \leq 1000 \\ \hline 4 & \mathbf{25} & 1 \leq n \leq 10^5 \\ \hline \end{array}\\
\end{align*}$$$$$$
10 1 6 1 8 0 3 3 9 8 8
5
4 1 2 3 4
0
In the first sample input, we can show that the $$$1$$$st, $$$3$$$rd, $$$5$$$th, $$$6$$$th, and $$$7$$$th students all say, "Thank you, sir!"
- First, the $$$5$$$th student says, "Thank you, sir!"
- After hearing this, the $$$1$$$st and $$$3$$$rd students say, "Thank you, sir!"
- After hearing them, the $$$6$$$th and $$$7$$$th students say, "Thank you, sir!"
- No further students say anything after that.
In the second sample input, no one will say "Thank you, sir!" How sad.
This is an interactive problem.
Alola! Alice landed an internship with the world-renowned Professor Kukui, the foremost expert on Pokémon moves. She just returned from an eight-week stay in Alola, and is excited to share her experience with you.
There are eighteen known Pokémon types, Normal, Fighting, Flying, Poison, Ground, Rock, Bug, Ghost, Steel, Fire, Water, Grass, Electric, Psychic, Ice, Dragon, Dark, Fairy. For an explanation of how type matchups work in Pokémon, read https://bit.ly/Abakoda2021PokemonTypeMatchups.
When we catch a Pokémon, we take it for granted that the Pokédex automatically tells us what type it is. But how did scientists first figure out that Raichu was an Electric type, whereas its Alolan regional variation is an Electric/Psychic type?
Professor Kukui assigned Alice the following problem. Alice is given a mystery Pokémon whose type is unknown. She can choose a type, and then attack the mystery Pokémon with a move of that type. After each attack, Professor Kukui's computer will tell her what that move's type effectiveness was against the mystery Pokémon ($$$4\times$$$, $$$2\times$$$, $$$1\times$$$, $$$0.5\times$$$, $$$0.25\times$$$, or $$$0\times$$$). You can assume that no other game mechanics are in play other than the type effectiveness system.
Since this method involves attacking and hurting the target Pokémon, Professor Kukui tasked Alice with developing a system that can figure out the mystery Pokémon's type in as few moves as possible. Alice is quite proud of her program, and she was able to prove that you should always be able to deduce the mystery type in five moves or less. Now, Alice is challenging you to do the same!
The judge first outputs a single line containing a single integer $$$T$$$, the number of test cases.
At the beginning of each test case, the judge secretly generates one or two Pokémon types. If there are two types, they are guaranteed to be different (so no Fire/Fire-type Pokémon). We may give type combinations that are still unused in the actual Pokémon games (such as Ice/Normal, as of the ninth generation).
You have two types of commands available to you.
If you wish to attack the mystery Pokémon, output a line containing ATTACK, a space, and then one of Normal, Fighting, Flying, Poison, Ground, Rock, Bug, Ghost, Steel, Fire, Water, Grass, Electric, Psychic, Ice, Dragon, Dark, Fairy. This is case-sensitive. The judge will then respond with a line containing the type effectiveness of a move of that type attacking the mystery Pokémon, which will be a line containing one of 4, 2, 1, 0.5, 0.25, or 0. If your query is invalid, the judge will respond with -1 and provide no further input; in this case, your program must exit immediately.
If you are ready to answer, output a line containing ANSWER, a space, and then the type(s) of the mystery Pokémon. If it has a single type, simply output that type (again, case-sensitive). If it has two types, output both of them in alphabetical order, separated by a forward slash /.
The judge will then respond with a single line containing NO if you were incorrect, or YES if you were correct. If your program receives a YES, then simply proceed with the next test case.
Technical Details
If you made an invalid command, said an invalid type, or received a NO, you will get $$$0$$$ points, and no further input (from the rest of the test cases) will be given from the judge. In such a case, your program should terminate immediately to prevent an Idleness Limit Exceeded verdict.
After printing a command or printing the answer, do not forget to flush the output. Otherwise, you will get an Idleness Limit Exceeded verdict. To manually flush the output, use:
- cout.flush() in C++
- sys.stdout.flush() in Python (don't forget to import sys)
- See the documentation for other languages.
There will be at most $$$980$$$ test cases in a single interaction.
Let $$$Q$$$ be the maximum number of times you used the ATTACK command in any of the test cases. Then, if you answered all the test cases correctly, scoring is as follows. $$$$$$ \begin{align*} \begin{cases} 0, & 18 \lt Q \\ 48 + 4 \times (18 - Q), & 5 \lt Q \leq 18 \\ 100, & Q \leq 5. \end{cases} \end{align*} $$$$$$ In other words, you get a baseline of $$$48$$$ points for answering the question correctly in $$$18$$$ commands or fewer, then the closer you are to $$$Q=5$$$, the more points you get (in increments of $$$4$$$).
Let's look at some sample interactions.
First, the judge tells us that this interaction has three test cases.
Contestant Judge
3
ATTACK Dragon
2
ATTACK Electric
0
ANSWER Dragon/Ground
YES
ATTACK Ground
4
ATTACK Normal
0.25
ANSWER Rock/Steel
YES
ATTACK Ice
0.5
ATTACK Steel
2
ATTACK Ghost
1
ATTACK Psychic
1
ATTACK Rock
2
ANSWER Ice
YES
In the first test case,
- Alice tries attacking with a Dragon-type move. It was super effective.
- Alice tries attacking with an Electric-type move. It was not effective.
- Alice realizes that Dragon is only super effective against Dragon, and that Electric is only not effective against Ground. She answers that the mystery Pokémon is Dragon/Ground, and the judge tells her she is correct.
In the second test case,
- Alice tries attacking with a Ground-type move. It dealt $$$4 \times$$$ damage, so Alice concludes that the mystery Pokémon has two types, both weak to Ground.
- Alice tries attacking with a Normal-type move. It dealt $$$0.25 \times$$$ damage, so Alice concludes that the mystery Pokémon has two types, both resisting Normal.
- Alice realizes that Normal is only not very effective against Rock and Steel, so she has enough information to conclude that the mystery Pokémon is Rock/Steel.
In the third test case, we can show that pure Ice is the only type consistent with the type effectiveness answers of Alice's five ATTACK commands.
For this interaction, Alice took $$$2$$$ attacks in the first test case, $$$2$$$ attacks in the second test case, and $$$5$$$ attacks in the third test case. So, $$$Q=5$$$, and she gets a full 100 points.
Contestant Judge
1
ATTACK Normal
0.5
ATTACK Psychic
1
ANSWER Rock
NO
In this interaction (which only has $$$1$$$ test case),
- Normal-type attacks are not very effective.
- Psychic-type attacks deal regular damage.
- Alice (hastily) concludes that the mystery Pokémon is Rock-type, since that is consistent with the judge's responses. However, the judge tells her she is incorrect! The mystery Pokémon in this case was Fighting/Steel, and there are still many other type-combinations consistent with the answers of the judge.
Alice has several long tests tomorrow, each worth at least 40% of her final grade in their respective subjects. So, naturally, she is procrastinating by watching videos on Youtube. She loves watching Numberphile videos, especially the ones that feature one of her mathematical idols, Neil Sloane. Sloane shows off tons of quirky integer sequences in his Numberphile appearances, so Alice decides to create her own cool sequence.
Let $$$a_n$$$ denote the $$$n$$$th term in the Alice sequence. Alice starts with the two terms $$$a_0 = 2$$$ and $$$a_1 = 3$$$. Then, Alice defines the sequence recursively, meaning each next entry in the sequence can be expressed in terms of the entries in the sequence that came before it (like in the Fibonacci sequence). For $$$n \geq 2$$$, Alice writes the formula $$$a_n = 2\ a_{n-1} - a_{n-2} + 2$$$.
The task is simple. Given $$$n$$$, find the value of $$$a_n$$$ in Alice's sequence. If you do it quickly enough, maybe Alice will still have time to study.
Input consists of a single line containing a single integer $$$n$$$.
Output a single line, containing the value of $$$a_n$$$.
$$$$$$\begin{align*}
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{30} & 0 \leq n \leq 10 \\ \hline 2 & \mathbf{15} & 0 \leq n \leq 100 \\ \hline 3 & \mathbf{15} & 0 \leq n \leq 10^4 \\ \hline 4 & \mathbf{10} & 0 \leq n \leq 10^5 \\ \hline 5 & \mathbf{30} & 0 \leq n \leq 3\times 10^9 \\ \hline \end{array}\\
\end{align*}$$$$$$
0
2
1
3
2
6
The values of $$$a_0$$$ and $$$a_1$$$ are $$$2$$$ and $$$3$$$, by definition. To get the value of $$$a_2$$$, we compute $$$a_2 = 2 \ a_1 - a_0 + 2 = 2 \times 3 - 2 + 2 = 6$$$.
Bob is excited to play the brand new video game Funny Girls (Kakatawa Shoujo) that Alice had gotten him as a gift! It's a visual novel with dating sim elements. It belongs to a genre of games whose main gameplay involves choosing one of several bachelorettes to romantically pursue, so the genre is sometimes referred to as galge (a shortening of "gal game").
Bob has really been enjoying this game, and discusses it with Alice every night. Alice mentioned that her favorite character is Alexa, the shy student council president who pines hopelessly for the main character but is unable to tell him how she feels. Bob, however, is much more interested in Cecille, the fun extroverted athletic girl with a carefree attitude. He thinks Alexa is nice, but finds Cecille to be a much more likeable and compelling character. Weirdly enough, when he mentioned this to Alice, she suddenly stopped responding to his messages...
Bob has almost finished the game, and could possibly end up with Alexa or Cecille, depending on whomever he meets next. The map of the game consists of $$$n$$$ locations arranged in a row, labeled $$$1$$$ to $$$n$$$ from left to right. In one step, he can travel from his current location to any of the locations directly adjacent to it. The level begins in a random location.
Some of these locations have an event flag. If he is in a location with Alexa's event flag, he ends up with Alexa and the game immediately ends. If he is in a location with Cecille's event flag, he ends up with Cecille and the game immediately ends. Note that if Bob already begins a level in a location with an event flag, then the game immediately ends without him having to move.
Not only will Bob's starting location in the final chapter be randomized, but he also is undecided as to whether he wants to end up with Alexa or Cecille. Thankfully, the event flags are fixed and always appear in the same locations. Thus, for each girl and for each possible starting position, help Bob find the minimum number of steps that he needs to travel in order for him to end the game with that girl.
The first line of input contains a single integer $$$n$$$, the number of locations.
The second line of input contains a string with $$$n$$$ characters. The $$$i$$$th character is A if the $$$i$$$th location has Alexa's event flag, is C if it has Cecille's event flag, and is . if it has neither's event flag.
First, output a line containing $$$n$$$ space-separated integers, the $$$k$$$th of which is the minimum number of steps to any of Alexa's event flags, from starting location $$$k$$$.
Then, output another line containing $$$n$$$ space-separated integers, the $$$k$$$th of which is this time the minimum number of steps to any of Cecille's event flags, from starting location $$$k$$$.
Whenever it would be impossible to end up with that girl from some $$$k$$$, output $$$-1$$$ as the answer to that starting location.
Note: Because of the possibly large output, it is recommended that Python users submit to PyPy.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq n \leq 2\times 10^5 \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{40} & n \leq 800 \\ \hline 2 & \mathbf{15} & \text{There is at most one event flag overall.} \\ \hline 3 & \mathbf{15} & \text{Alexa has at most one event flag.} \\ & & \text{Cecille has at most one event flag.} \\ \hline 4 & \mathbf{20} & \text{All event flags belong to the same girl.} \\ \hline 5 & \mathbf{10} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
4 .A..
1 0 1 2 -1 -1 -1 -1
5 C..CA
-1 -1 -1 -1 0 0 1 1 0 -1
6 CA...C
-1 0 1 2 3 -1 0 -1 3 2 1 0
In the third sample input, suppose that Bob starts at location $$$3$$$ and wants to end the game will Cecille. Note that he has to move $$$3$$$ steps to the right to reach the C at location $$$6$$$. He cannot move $$$2$$$ steps to the left to reach the C at location $$$1$$$, because then he would have to pass through the A at location $$$2$$$ first, which would already immediately end the game with Alexa.
Try to guess the problem from the following gif: https://imgur.com/xtk06Dt
The Physics Departments in the Philippines' top universities decided that it was high time that the Philippines catch up with other countries' research facilities, so that Filipino physicists could also be at the frontier of new theoretical discoveries. Thus, they have teamed up to create the Great Halcon Collider, a particle accelerator constructed beneath the mountains of the Mindoro provinces.
Alice was fortunate enough to have been selected by her school to be a student delegate who will be one of the first to tour the brand new facilities. However, the head scientists at the Great Halcon Collider were concerned about letting untrained teenagers onto their multi-billion peso facilities. Thus, they decided to administer the following test, and would only allow entry to the students who answer it correctly.
A positron particle, modeled as a point, begins in the bottom-left corner of a box with horizontal width $$$w$$$ and vertical height $$$h$$$. The particle moves continuously in a straight line at a constant velocity. Initially, the particle has a horizontal velocity of $$$x$$$ units per second, and a vertical velocity of $$$y$$$ units per second, where $$$x$$$ and $$$y$$$ are positive integers.
- What is the total distance traveled by the positron before vanishing?
- How many times did the positron bounce off a side of the box?
- Which of the four corners did the positron vanish at?
Alice really wants to see the Great Halcon Collider, so she's asked for your help!
Input begins with a single line, containing a single integer $$$t$$$.
Then, $$$t$$$ lines follow, each describing a test case. Each line contains the four space-separated integers $$$w$$$, $$$h$$$, $$$x$$$, $$$y$$$, respectively, for that test case.
For each query, output three lines, answering each of the scientists' questions.
- First, output a real number, the total distance (in units) traveled by the positron before vanishing.
- Then, output an integer, the number of times the positron bounced off a side of the box.
- Finally, output a string denoting which corner the positron vanished at. This should be one of TL, TR, BL, BR, which correspond to the top-left, top-right, bottom-left, and bottom-right corner, respectively.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq t \leq 1000 \\ \text{$1 \leq w, h, x, y \leq 1000$ for all test cases.} \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{30} & \text{$x = y = 1$ for all test cases.} \\ \hline 2 & \mathbf{30} & \text{$w = h = 1$ for all test cases.} \\ \hline 3 & \mathbf{30} & \text{$1 \leq w, h, x, y \leq 10$ for all test cases.} \\ \hline 4 & \mathbf{10} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
1 1 1 1 1
1.414213562373 0 TR
3 1 2 1 1 1 3 2 4 4 3 5 2
2.828427124746 1 TL 6.708203932499 3 BR 64.621977685614 21 BR
The positron travels as follows in the first sample input.
The positron travels as follows in the first test case of the second sample input.
The positron travels as follows in the second test case of the second sample input.
An animated gif of the positron's trajectory in the third test case of the second sample input has been uploaded here: https://imgur.com/xtk06Dt. This is the same gif shown at the beginning of the problem statement.
During a party, Cindy encountered Alice by herself in a corner of the room, not talking to anyone, but just watching other people interact. Cindy asked Alice what was wrong, and Alice explained that she found it hard to strike up conversations with random people. Cindy explained to Alice that talking with people is easy if you can find a suitable ice breaker to get over the original awkwardness. Since Alice was on the student council, she probably knew a lot people, so Cindy said that a good ice breaker for her would be to talk about a common friend that she and her conversation partner both knew.
Alice, nervous and pedantic, asked Cindy to clarify what it meant to know someone. After a two-hour long philosophical discussion about the Epiphany of the Face and "How can we say that we know anything???", Cindy offered the following simplified definition (for party purposes).
- In their school, there are many different organizations, and a student can join up to four different orgs.
- Two people know each other if they are part of the same club.
- Example: Alice and Cindy are both part of the Japanese Culture Org. So, Alice and Cindy know each other.
Alice still seemed nervous, so Cindy decided to spend the rest of the party talking with her, instead of pushing her to talk to strangers. The two of them developed a party game.
Alice, as part of the Student Council, knows the names of all the students in the school, as well as the full rosters of all orgs in the school. Cindy first names some classmate. Alice should say a sequence of names, starting with herself, Alice. Each next name that she mentions must belong to someone who knows the previous person in the sequence. The goal is to try to reach the classmate that Cindy named using the shortest sequence possible. The number of names (other than Alice) in the shortest such sequence to that classmate is that person's Alice number. A smaller Alice number means that, in a sense, Alice is a "closer acquaintance" of that person.
If the task is impossible for some person, then their Alice number is $$$-1$$$. Also, by definition, the Alice number of Alice is $$$0$$$.
The next day, Alice thought it was fun enough to turn into a programming problem. Can you replicate her success?
The first line of input contains two space-separated integers $$$n$$$ and $$$m$$$, the number of students in Alice's school, and the number of different orgs at Alice's school.
Next, a line containing $$$n$$$ space-separated words, the full list of names of the students in Alice's school. Exactly one of these will be Alice.
Each org is then described in the following manner.
- First, a line containing a single integer $$$k$$$, the number of students in this org. Each org has at least one member.
- Then, a line containing $$$k$$$ space-separated names, the students in this org, in some order.
Contestants are recommended to use fast methods of input and output for this problem. It is recommended that Python users submit to PyPy for this problem.
Output a single line containing $$$n$$$ space-separated integers, the Alice numbers of the students in Alice's school, listed in the same order that the students' names were given in the input.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline \text{Alice always appears in the list of students' names.} \\ \text{Each name will appear in no more than four different orgs.} \\ \text{No two students have the same name.} \\ \text{The names in each org roster are unique.} \\ \text{Each student's name consists of at most $5$ upper or lowercase English letters.} \\ \text{The names are case sensitive.} \\ 1 \leq n \leq 10^5 \\ 1 \leq m \leq 10^5 \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline
1 & \mathbf{40} & 1 \leq n \leq 40 \\ && 1 \leq m \leq 40 \\ \hline
2 & \mathbf{40} & 1 \leq n \leq 520 \\ && 1 \leq m \leq 520 \\ \hline
4 & \mathbf{20} & \text{No further constraints.} \\ \hline
\end{array}\\
\end{align*}$$$$$$
10 4 Alice Bob Cindy Dani Eve Franz Gabi Hans Isa Jules 3 Alice Bob Cindy 2 Cindy Dani 4 Dani Eve Franz Gabi 2 Hans Isa
0 1 1 2 3 3 3 -1 -1 -1
10 4 Alice Bob Cindy Dani Eve Franz Gabi Hans Isa Jules 3 Alice Bob Cindy 2 Bob Dani 2 Dani Eve 2 Cindy Eve
0 1 1 2 2 -1 -1 -1 -1 -1
In the first sample input, for Eve, Alice can consider the sequence, $$$$$$ \texttt{Alice$\to$Cindy$\to$Dani$\to$Eve}. $$$$$$ This sequence uses three names (other than Alice): Cindy, Dani, Eve. No shorter sequence exists. Thus, Eve has an Alice number of $$$3$$$.
For the second sample input, for Eve, Alice can consider the sequence, $$$$$$ \texttt{Alice$\to$Bob$\to$Dani$\to$Eve}, $$$$$$ which has $$$3$$$ names (other than Alice). However, the Alice number of Eve is not actually $$$3$$$, because a shorter sequence exists, $$$$$$ \texttt{Alice$\to$Cindy$\to$Eve}. $$$$$$ The Alice number of Eve here is actually $$$2$$$.
Cindy thought a fine complement to her athletic prowess would be to learn more fine dexterity and sleight of hand, and what better way to do that than to learn some cool card tricks? The art of prestidigitation! Legerdemain!
Alice heard about this and excitedly wanted to teach Cindy a special card trick that she had learned. Well, it's actually not really a trick... it's more like a puzzle. A numbers puzzle. But Alice was really excited, so Cindy indulged her.
Cindy combined innumerably many decks, and dealt out $$$n$$$ cards face-up on the table. Each card is associated with some numerical value. Two through Ten are each worth the number on them. The "face cards" of Jack, Queen, and King each have a value of $$$10$$$. For this problem, the Ace always has a value of $$$1$$$. Finally, we have a special card, the Joker. The Joker can do anything! It can magically transform into any of the other card types.
Alice and Cindy view the face-up cards that were dealt. Some (possibly none) will be Jokers. Alice gives Cindy some target value $$$m$$$. Cindy must replace each Joker with a non-Joker card, such that the sum of the values of all face-up cards becomes exactly equal to $$$m$$$.
Cindy spent so much time practicing the shuffling and the dealing and the flourishes, that she doesn't have any energy left for the computations! Do you think you could help her out?
The first line of input contains two space-separated integers $$$n$$$ and $$$m$$$, the number of face-up cards and the desired total value.
This is followed by a line containing a string with $$$n$$$ characters, encoding the face-up cards in the order they appear. Each character will be one of the following.
- A corresponds to an Ace.
- Digits 2 through 9 correspond to the numbers Two through Nine.
- T corresponds to a Ten.
- J, Q, K correspond to Jack, Queen, and King, respectively.
- * corresponds to a Joker.
If the task is possible, output a single line containing the word YES; otherwise, output NO.
If YES, output another line containing a string with $$$n$$$ characters. This should be exactly the same string given in the input, except each * has been replaced with one of A23456789TJQK, such that the total value of all the cards is exactly equal to $$$m$$$. If there are multiple solutions, output any of them.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq n \leq 10^5 \\ 1 \leq m \leq 10^6 \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{30} & \text{There are no Jokers.} \\ \hline 2 & \mathbf{30} & \text{There is at most $1$ Joker.} \\ \hline 3 & \mathbf{20} & \text{There are at most $3$ Jokers.} \\ \hline 4 & \mathbf{20} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
5 26 2JAK3
YES 2JAK3
6 23 3A4A5*
YES 3A4A59
3 31 ***
NO
26 27 AAAAAAAAAAAAAAAAAAAAAAAAAA
NO
Bob took an internship under the famous Filipino game designer Francisco Marikina (or Francisco M for short). Francisco M's goal is to revolutionize the Original Pilipino MMO (OPM) genre. Francisco M's first big decision is to have the game take place on a grid, instead of being free-roaming. But what kind of grid?
- First, he thought of using triangles, but then he would have to make it out of Bamboo, which isn't sturdy enough.
- Second, he thought that it was Hip to Be Square, but then realized it doesn't fit his overall theme of OPM.
- Thus, Francisco M realized his only option was to use a hexagonal grid for his game, to represent a Kaleidoscope World.
Francisco M's game takes place on an infinite hexagonal grid called the kaleidoscope world. A special hexagon has been marked as the starting city.
All hexagons are oriented such that they have two horizontal sides. In one step, a player can travel from their current hexagon to the hexagon that is directly up, down, right-up, right-down, left-up, or left-down from their position, represented by the shortcuts U, D, RU, RD, LU, LD, respectively. See the following diagram.
Players begin at the starting city. To move around, players choose a direction $$$t$$$ and a positive integer $$$k$$$, then move $$$k$$$ steps in that direction. The path of a player is a sequence of such movements.
Francisco M has traced the paths of $$$n$$$ different beta testers in his game. His task for Bob is to construct the following widget. Given two different players, Bob's widget should be able find the distance between those two players' final positions. The distance between two hexagons in the kaleidoscope world is equal to the minimum number of single steps needed to travel from one hexagon to the other. Bob's widget will also be tested against $$$q$$$ different queries.
Bob was quite proud of his solution, and challenges you to replicate his success.
The first line of input contains a single integer $$$n$$$, the number of players.
Each player is then described in the following manner.
- First, a line containing a single string, the player's username.
- Then, a line containing a single integer $$$m$$$, the number of movements made by this player.
- Then, $$$m$$$ lines follow, each of the form t k, where $$$t$$$ is one of U, D, RU, RD, LU, LD and $$$k$$$ is a positive integer, corresponding to the direction and number of steps of that movement. These movements are given in the same order that they are performed by this player.
The next line of input contains a single integer $$$q$$$, the number of queries.
Then, $$$q$$$ lines follow, each describing a query. Each line contains two space-separated strings, corresponding to the usernames of two different players.
For each query, output a line containing a single integer, the distance between the final positions of the two players in that query.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 2 \leq n \leq 2000 \\ \text{Each player's username is at most nine characters long, and consists only of upper or lowercase letters, or digits.} \\ \text{No two players have the same username.} \\ \text{$1 \leq m \leq 10$ for all players.} \\ \text{$1 \leq k \leq 10^7$ for all movements.} \\ 1 \leq q \leq 10^4 \\ \text{The two usernames in each query are different.} \\ \text{Each username mentioned in the queries belongs to some player given in the input.} \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & \text{$t$ is }\mathtt{U}\text{ or }\mathtt{D}\text{ for all movements} \\ \hline 2 & \mathbf{30} & \text{$m = 1$ for all players} \\ \hline 3 & \mathbf{30} & \text{$k \leq 3$ for all movements} \\ \hline 4 & \mathbf{20} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
3 jus102res 2 U 2 LU 1 dreeei 1 RU 4 ACSF313 3 LD 2 RD 2 U 1 3 ACSF313 dreeei jus102res ACSF313 jus102res dreeei
5 4 5
Here is the path taken by jus102res.
Here is the path taken by dreeei.
Here is the path taken by ACSF313.
We also illustrate the lengths of the shortest paths between each of the players, giving the answer to each of the queries above.
Bob had been invited by Alice and Cindy to attend an anime convention with them, and he's quite excited for the chance to cosplay. He heard that Alice and Cindy will be dressing up as Naruto characters with Kekkei Genkai (Bloodline Limits)—Alice will cosplay as Pakura of the Scorch Release, while Cindy will crossplay as the Sandaime Kazekage (user of Magnet Release). Sticking with this theme, Bob decides to cosplay as Darui, from the Village Hidden in the Clouds! Darui's Bloodline Limit, the Ranton (Storm Release, 嵐遁), allows him to fire laser-like beams of electricity that flow like water. One of his signature jutsus is Laser Circus (励挫鎖苛素), allowing him to fire multiple beams at once with pinpoint accuracy.
Unfortunately, Bob doesn't actually have the Ranton Bloodline Limit. All he has is a laser pointer. He is also not able to directly manipulate the trajectory of his laser beam, so instead he has set up an elaborate maze of mirrors.
The maze can be seen as a grid with $$$r$$$ rows and $$$c$$$ columns. The left and right boundaries of the rows are labeled L and R, while the top and bottom boundaries of the columns are labeled T and B. The rows are numbered $$$1$$$ to $$$r$$$ from top to bottom, and the columns are numbered $$$1$$$ to $$$c$$$ from left to right. Each boundary edge of the maze can be described by its label and row/column number. Each square in the grid contains a single double-sided mirror oriented at a $$$45^{\circ}$$$ angle, connecting two opposite corners of that square. Please refer to this illustration of the maze from the second sample input, as an example of how the labeling scheme works.
Bob will be firing his laser into the maze from one of its boundary edges (at an angle perpendicular to that edge). When the laser hits a mirror, it reflects off it at a 90 degree angle and keeps bouncing around in the maze until it leaves. Bob wants you to determine where the laser will exit the maze.
Also, he will be firing his laser into the maze $$$q$$$ different times, each from a different starting location. Find the exit location of the laser in each of these occurrences.
The first line of input contains two space-separated integers $$$r$$$ and $$$c$$$, the number of rows and the number of columns in the maze.
Then, $$$r$$$ lines follow, each containing a string with $$$c$$$ characters. This encodes the maze. Each character is either \, representing a mirror that connects the top left and bottom right corners, or /, representing a mirror that connects the top right and bottom left corners.
The next line of input contains a single integer $$$q$$$, the number of queries.
Then, $$$q$$$ lines follow, each describing a query. Each line contains the boundary edge from which Bob was firing her laser into the maze, described by its label and row/column number, with a space separating the two.
Contestants are recommended to use fast methods of input and output for this problem.
For each query, output a line containing the label and row/column number (separated by a space) of the boundary edge from which the laser will exit the maze.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq r \times c \leq 10^5 \\ 1 \leq q \leq \min(2(r+c),10^5) \\ \text{No two queries begin at the same starting location.} \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{30} & \text{All mirrors are oriented like }\mathtt{/}\text{} \\ \hline 2 & \mathbf{20} & r = 1 \\ \hline 3 & \mathbf{20} & \text{$r\times c \leq 10^3$} \\ \hline 4 & \mathbf{30} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
1 1 / 4 R 1 L 1 T 1 B 1
B 1 T 1 L 1 R 1
4 5 \/\/\ \/\// \\/\\ \\\// 4 T 2 R 1 L 3 B 4
T 1 T 5 B 2 L 1
Recall that you need to use an escape sequence to use the backslash character literal in most programming languages.
Let's look at each of the queries from the second sample input. This is the path of the laser when fired from the top of the $$$2$$$nd column.
This is the path of the laser when fired from the right of the $$$1$$$st row.
This is the path of the laser when fired from the left of the $$$3$$$rd row.
This is the path of the laser when fired from the bottom of the $$$4$$$th column.
Bob's art teacher tasked him with creating a collection of artworks that imitate the style of Vicente Manansala, one of the Philippines' national artists. As Manansala was a cubist, Bob worked hard to create a style that uses sharp geometric shapes to present a stylized and deconstructed perspective of the world.
Unfortunately, Bob is a better programmer than he is an artist. He leaned too hard into the "geometric shapes" idea, and the artworks he created were composed of only rectangles. His art teacher commented that Bob's paintings more closely resembled the abstract works of Piet Mondrian instead. Undeterred, Bob decided to call his new style Mondrianansala.
A rectangle is of the Mondrianansala style if it has integer unit dimensions, and the ratio of its shorter side to its longer side is exactly $$$2 : 3$$$ (so it could be $$$2 \times 3$$$ or $$$6 \times 4$$$, or $$$6 \times 9$$$, or $$$300 \times 200$$$, etc.). We say that an entire painting is of the Mondrianansala style if it satisfies the following conditions.
- It is painted on a square canvas.
- The painting is entirely composed of Mondrianansala-style rectangles.
- Each rectangle is one of $$$26$$$ different colors, and the entire rectangle is painted that color.
- No two touching rectangles have the same color (though rectangles of the same color may touch at corners).
Bob's running out of time, and he needs a lot of different Mondrianansala-style paintings for his exhibit. Can you write a program that, given a positive integer $$$m$$$, creates a Mondrianansala-style painting with exactly $$$m$$$ rectangles? You can even choose the size of the painting (within reason). Bob managed to prove that the task should always be possible when $$$m \geq 6$$$.
Input consists of a single line containing the integer $$$m$$$.
Output the painting. We will treat the painting as a pixelmap and represent it as an ASCII grid.
Output a line containing a single integer $$$n$$$, the side lengths of the painting. Then, output $$$n$$$ lines, each containing a string with $$$n$$$ uppercase English letters, representing the painting. Two pixels are considered the same color if they are represented by the same letter. Contiguous regions of pixels of the same color correspond to the rectangles.
We can show that, given the constraints, a solution always exists that satisfies $$$1 \leq n \leq 2500$$$. If there are multiple solutions, output any of them that have $$$n$$$ in this range.
Note: Because of the possibly huge output, it is recommended that Python users submit to PyPy.
$$$$$$\begin{align*}
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{25} & m=6\text{ or }m=12 \\ \hline 2 & \mathbf{20} & m=6\text{ or }m=2022 \\ \hline 3 & \mathbf{15} & m=6\text{ or }m=2038 \\ \hline 4 & \mathbf{15} & m=6\text{ or }m=5000 \\ \hline 5 & \mathbf{10} & 6 \leq m \leq 5000 \\ \hline 6 & \mathbf{15} & 6 \leq m \leq 2\times 10^5 \\ \hline \end{array}\\
\end{align*}$$$$$$
6
6 AAABBB AAABBB BBBAAA BBBAAA AAABBB AAABBB
24
24 AAAAAAAAAAAAAAABBBBBBBBB AAAAAAAAAAAAAAABBBBBBBBB AAAAAAAAAAAAAAABBBBBBBBB AAAAAAAAAAAAAAABBBBBBBBB AAAAAAAAAAAAAAABBBBBBBBB AAAAAAAAAAAAAAABBBBBBBBB AAAAAAAAAAAAAAACCCCCCDDD AAAAAAAAAAAAAAACCCCCCDDD AAAAAAAAAAAAAAACCCCCCBBB AAAAAAAAAAAAAAACCCCCCBBB DDDBBBBBBBBBBBBCCCCCCDDD DDDBBBBBBBBBBBBCCCCCCDDD CCCBBBBBBBBBBBBCCCCCCBBB CCCBBBBBBBBBBBBCCCCCCBBB DDDBBBBBBBBBBBBCCCCCCDDD DDDBBBBBBBBBBBBAADDAADDD CCCBBBBBBBBBBBBAADDAABBB CCCBBBBBBBBBBBBAADDAABBB AAAACCCDDDDDDDDDBBBBCCCC AAAACCCDDDDDDDDDBBBBCCCC AAAABBBDDDDDDDDDBBBBCCCC AAAABBBDDDDDDDDDBBBBCCCC AAAACCCDDDDDDDDDBBBBCCCC AAAACCCDDDDDDDDDBBBBCCCC
The second sample output corresponds to the $$$m = 24$$$ image shown in the problem statement.
Cindy was going through her old hard drives and found pictures of herself from when she was in Grade 2. Oh my gosh! She looked so nene in these old pics! Nene is a Tagalog slang word used to refer to the childish appearance of young girls, with the additional connotation of such things being baduy (lame or unfashionable, particularly due to being out of style).
The picture is encoded in a pixelmap, and can be represented by a grid of characters with $$$r$$$ rows and $$$c$$$ columns. The color of each pixel is represented by an uppercase English letter. In order to reduce the nene-ness of her picture, Cindy opened it in her favorite image-editing software Inkekescape, which only has one type of operation. When Cindy says, x is y (where x and y are uppercase English letters), the program replaces all pixels of color x (if any) with pixels of colors y.
Cindy has already performed $$$n$$$ such operations on her picture. But then, she's starting to have second-thoughts. She realizes that being nene (or totoy, for boys) was a phase that everyone went through, so she has nothing to be ashamed of. In fact, now she wants to preserve the original picture so that she has an authentic record of her childhood memories.
Unfortunately, she saved over the original copy of the picture, with no backup. The only way Cindy can fix her photo now is by using more of the x is y operations of Inkekescape.
Given the $$$n$$$ operations that Cindy has already performed, is it possible to perform some more operations to recover the colors of her original picture? If yes, please actually provide the series of operations that accomplishes this goal.
The first line of input contains two space-separated integers $$$r$$$ and $$$c$$$, the number of rows and the number of columns in the picture.
Then, $$$r$$$ lines follow, each containing a string of $$$c$$$ characters. This encodes the picture.
Then, this is followed by a line with a single integer $$$n$$$, the number of operations.
Then, $$$n$$$ lines follow, each containing the words x is y, where x and y are uppercase letters. These are the operations that Cindy had already performed, in the order that she performed them.
If the task is possible, output a single line containing the word YES; otherwise, output NO.
If YES, output another line containing a single integer $$$m$$$, the number of extra operations that you wish to perform. Then, output $$$m$$$ lines, each containing the words x is y, where x and y are uppercase letters. This corresponds to the extra operations, in the order that you wish to perform them, done after Cindy's last operation. After the last operation is done, the photo should be restored to its original state.
We can show that given the constraints, if a solution exists, there is one that satisfies $$$0 \leq m \leq 10^5$$$. If there are multiple solutions, output any of them that have $$$m$$$ in this range. Note that you don't have to minimize $$$m$$$.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq r \times c \leq 10^5 \\ 1 \leq n \leq 10^4 \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & \text{All pixels in the initial grid are the same color.} \\ \hline 2 & \mathbf{20} & \text{There are at most three different-colored pixels in the initial grid.} \\ \hline 3 & \mathbf{20} & \text{$1 \leq r \times c \leq 64$} \\ && \text{$1 \leq n \leq 100$} \\ \hline 4 & \mathbf{20} & \text{$1 \leq r \times c \leq 1600$} \\ && \text{$1 \leq n \leq 100$} \\ \hline 5 & \mathbf{20} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
3 2 AA AA AA 2 A is B B is A
YES 0
3 4 AABB BBCC AABB 4 A is D E is F C is A D is C
YES 3 A is E C is A E is C
1 3 ABC 2 A is D C is D
NO
For the first sample input, Cindy's operations already restored the photo to its original state, so we don't have to do anything.
We illustrate the second sample input. Here are the operations performed by Cindy. Note that the E is F operation did nothing, because there were no E pixels at the time.
