Alice, Bob, and Cindy are going on a road trip together this Christmas break! While all their other friends are vacationing in Japan and Europe, the three friends think that it's going to be more fun (and economical!) to bond by exploring the Philippines together. Coincidentally, the three of them brought the exact same kind of bag for their personal belongings. Thankfully, it should be possible to tell them apart because each bag has a name tag that says one of Alice or Bob or Cindy, corresponding to its owner. These strings are case-sensitive!
Unfortunately, the name tags have gotten a bit faded over time, so some of the letters might be a bit hard to read. You are at least assured that the length of the string on the nametag is correct. Let's help keep their vacation stress-free by writing a program that identifies the owner of the bag from a possibly unclear name tag, assuming that the owner is one of Alice or Bob or Cindy.
Input consists of a single line containing a single string, corresponding to what can be read on the name tag. Each character in $$$s$$$ is either an upper or lowercase English letter, or a period . which indicates that the character is unreadable and could be any letter.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline \text{The input string consists of $1$ to $5$ characters, each either an upper or lowercase} \\ \text{English letter or period.} \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{33} & \text{There is no }\mathtt{.}\text{ character in the input.} \\ \hline 2 & \mathbf{33} & \text{All characters in the input are }\mathtt{.}\text{ }\mathbf{or}\text{ the string is $1$ letter long} \\ \hline 3 & \mathbf{34} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
If we assume that one of Alice or Bob or Cindy should be the owner:
- If exactly one of their names could possibly be what is written on the nametag, output that name.
- If there is more than one possible answer, output CAN'T TELL
- If the name tag doesn't match with any of the three, output SOMETHING'S WRONG
You are reminded that your logic should be case sensitive.
Ali.e
Alice
bob
SOMETHING'S WRONG
.i...
Cindy
Alice loves braids! Her preferred hairstyle for as long as anyone has known her has always been some kind of braid.
One day, Bob asked Alice if she could teach him how to do a simple braid. Alice, excited, gave him the following instructions for a basic braid.
- Split the hair into three sections.
- For $$$n$$$ times, take two adjacent sections and cross one over the other.
- We alternate between crossing the left-over-middle and right-over-middle.
- The initial crossing is up to you.
Bob didn't quite understand, so Alice created the following image to hopefully explain things more clearly. Here is an example braid with $$$n = 7$$$ crossings that begins with left-over-middle.
Alice thinks that the image was so helpful that they should make more. Given the number of crossings $$$n$$$, the initial crossing, and a string $$$s$$$ which encodes the colors we would use for the three sections, output a similar drawing of a braid, using ASCII art. See the Output Format and Sample I/O for more details.
The first line of input contains a single integer $$$n$$$, the number of crossings in the braid.
The second line of input contains either left-over-middle or right-over-middle, indicating which is the initial crossing in the braid.
The third line of input contains a single string $$$s$$$ with three distinct uppercase letters, which represent the colors of the sections from left to right.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq n \leq 50 \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline
1 & \mathbf{33} & n = 1 \\ \hline
2 & \mathbf{33} & \text{The initial crossing is }\mathtt{left-over-middle}\text{.} \\ && s = \text{ABC} \\ \hline
3 & \mathbf{34} & \text{No further constraints.} \\ \hline
\end{array}\\
\end{align*}$$$$$$
Output an ASCII grid with $$$9$$$ columns and $$$1+4n$$$ rows, representing the braid.
The first row contains the first, second, and third letters of $$$s$$$ in the $$$1$$$st, $$$5$$$th, and $$$9$$$th columns, respectively, representing the three sections as originally positioned from left to right, with their respective colors.
Each of the $$$n$$$ crossings is represented by another four rows. Examine the samples to see, for each crossing, how to render the section that goes over, the section that goes under, and the section that is unused. Place a . on every "empty" square of the grid which does not contain a section.
1 left-over-middle ABC
A...B...C .A.B....C ..A.....C .B.A....C B...A...C
2 right-over-middle ABC
A...B...C A....B.C. A.....C.. A....C.B. A...C...B .A.C....B ..A.....B .C.A....B C...A...B
7 left-over-middle NOI
N...O...I .N.O....I ..N.....I .O.N....I O...N...I O....N.I. O.....I.. O....I.N. O...I...N .O.I....N ..O.....N .I.O....N I...O...N I....O.N. I.....N.. I....N.O. I...N...O .I.N....O ..I.....O .N.I....O N...I...O N....I.O. N.....O.. N....O.I. N...O...I .N.O....I ..N.....I .O.N....I O...N...I
Alice, Bob, and Cindy are going caroling! Wouldn't it be cute if they had a special song for each Department of their school? Tonight, they're going to visit the Computer Science Dept. Let's write them a cute song!
The song, "The $$$n$$$ Days of Codemas," has $$$n$$$ verses labeled in order from $$$1$$$ to $$$n$$$, and each verse follows a specific pattern.
You can check the first Sample Output for what the song looks like with $$$n=6$$$ verses, but let's look at how to construct such a song in general. Each verse consists of some number of lines.
For each $$$k$$$ from $$$1$$$ to $$$n$$$, the $$$k$$$th verse looks as follows:
- Its first line is:
On the <kth> day of Codemas, my computer gave to me, - The next $$$k-1$$$ lines are:
<x> compiler warnings, where $$$x$$$ counts down from $$$k$$$ to $$$2$$$; as an exception, for $$$x = 5$$$, it is instead:FIVE! COMPILER! WARNINGS!!! - On all verses except the first, the last line is:
And a syntax error on line three! On the first verse only, omit that And, so the last line is just:A syntax error on line three!
In the first line, <kth> should format the verse number $$$k$$$ in its ordinal form. For this problem, use the following formatting rules:
- If the last digit is $$$1$$$, the suffix is st
- If the last digit is $$$2$$$, the suffix is nd
- If the last digit is $$$3$$$, the suffix is rd
- Otherwise, the suffix is th
- As a special exception, if the last two digits are $$$11$$$, $$$12$$$, or $$$13$$$, then the suffix is th
You have to answer $$$Q$$$ questions of the following form: Given a positive integer $$$i$$$, what is the $$$i$$$th line in the song? Or, say that the song has already ended.
The first line of input contains two space-separated integers $$$n$$$ and $$$Q$$$.
$$$Q$$$ lines follow, each containing some integer $$$i$$$, corresponding to the $$$Q$$$ questions that must be answered.
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.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq Q \leq 10^5 \\ 1 \leq n \leq 10^9 \\ 1 \leq i \leq 10^{18} \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline
1 & \mathbf{12} & i \leq 15 \\ \hline
2 & \mathbf{40} & i \leq 10^5 \\ \hline
3 & \mathbf{12} & Q \le 5 \\ && i \le 10^{12} \\ \hline
4 & \mathbf{12} & i \le 10^{12} \\ \hline
5 & \mathbf{12} & Q \le 5 \\ \hline
6 & \mathbf{12} & \text{No further constraints.} \\ \hline
\end{array}\\
\end{align*}$$$$$$
Output $$$Q$$$ lines, answering each of the questions in order. If for some question, there is no $$$i$$$th line in the song, then output Codemas is already over! instead.
The checker is strict. Do not even output extra spaces or newlines.
6 30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
On the 1st day of Codemas, my computer gave to me, A syntax error on line three! On the 2nd day of Codemas, my computer gave to me, 2 compiler warnings, And a syntax error on line three! On the 3rd day of Codemas, my computer gave to me, 3 compiler warnings, 2 compiler warnings, And a syntax error on line three! On the 4th day of Codemas, my computer gave to me, 4 compiler warnings, 3 compiler warnings, 2 compiler warnings, And a syntax error on line three! On the 5th day of Codemas, my computer gave to me, FIVE! COMPILER! WARNINGS!!! 4 compiler warnings, 3 compiler warnings, 2 compiler warnings, And a syntax error on line three! On the 6th day of Codemas, my computer gave to me, 6 compiler warnings, FIVE! COMPILER! WARNINGS!!! 4 compiler warnings, 3 compiler warnings, 2 compiler warnings, And a syntax error on line three! Codemas is already over! Codemas is already over! Codemas is already over!
2023 8 1 2 561 4000 4004 6216 24753 1000000
On the 1st day of Codemas, my computer gave to me, A syntax error on line three! On the 33rd day of Codemas, my computer gave to me, FIVE! COMPILER! WARNINGS!!! And a syntax error on line three! On the 111th day of Codemas, my computer gave to me, On the 222nd day of Codemas, my computer gave to me, 405 compiler warnings,
In the digital world, there's only three things to do.
Hello virtual reality! Bob is excited to surf on the wild and wacky place known as the World Wide Web! He's already watched the thorough tutorial that will teach a cool kid like him all about how to navigate the cyberspace. The only thing left is that he needs a username!
Unfortunately, his preferred username of bobTheBuilder has already been taken. So, as is customary, Bob is going to append a number to the end of his username. But not just any number—Bob wants it to be a positive integer, and he wants to take into account the digital style of this number. Furthermore, the number itself cannot be too small or too large.
The digital style of a positive integer $$$n$$$ is merely the product of its digits. So, for example, the digital style of $$$1984$$$ is $$$1 \times 9 \times 8 \times 4 = 288$$$.
But Bob's a contrarian, you see. He actually wants to minimize his digital style, because he thinks not being cool is the new cool thing (as long as you do it ironically). Given positive integers $$$L$$$ and $$$R$$$, what is the minimum possible digital style among all integers $$$n$$$ such that $$$L \leq n \leq R$$$?
Input consists of a single line containing the two space-separated integers $$$L$$$ and $$$R$$$.
$$$$$$\begin{align*}
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{34} & 1 \leq L \leq R \leq 10^{4} \\ \hline 2 & \mathbf{33} & 1 \leq L \leq R \leq 10^{9} \\ \hline 3 & \mathbf{33} & 1 \leq L \leq R \leq 10^{18} \\ \hline \end{array}\\
\end{align*}$$$$$$
Output a single integer, the minimum possible digital style across all integers in the given range.
42 47
8
225 228
20
This is an interactive problem.
This year, Alice decided to take an internship at the Gates to the Underworld, under the supervision of the Egyptian God of Death, Anubis.
She assists Anubis in weighing the hearts of the deceased in order to determine whose souls are worthy of entering the realm of the dead. Each heart is weighed against a feather of Ma'at, the goddess of truth, using a pair of balance scales. Those with hearts lighter than the feather get to enter the underworld; those with hearts heavier than the feather have their souls devoured by the goddess Ammit.
But Alice has an ambitious goal — what if they can precisely numerically measure the weight of each heart? Intrigued, Anubis challenges her to devise a feasible plan.
In order to comply with company policy, Alice is still required to use Anubis' balance scales. Balance scales have two pans, a left and a right. Alice can place any number of items in each pan, and once released, the scales will tip in the direction of the pan whose items have a greater total weight.
Alice can custom-order a special set of feathers from Ma'at. Each feather will have a known positive integer weight (in units), where Alice is free to specify the exact weight that she wants for each feather in her set.
Then, Anubis will test her. He will present to her a series of hearts, and she must precisely measure the weight of each heart using only the balance scales and her special set of feathers. The weight of each heart is guaranteed to be a positive integer when measured using the same units as Alice's feathers.
Ma'at will grant Alice at most $$$15$$$ feathers. Alice wants to maximize the number of units that these $$$15$$$ feathers can measure. Let's help her out!
First things first, we want to make sure you have a high-level idea of what this problem is all about, without getting buried in technical details. Observe the "dialogue" interaction between Alice and Anubis shown here (at url https://imgur.com/a/HAJSRxk). This interaction is also what is encoded in the Sample Interaction section.
As we saw, the interaction comes in two phases: the "requesting", then the "testing".
First, output a positive integer $$$n$$$, meaning that you request a set of $$$n$$$ feathers, indexed from $$$1$$$ to $$$n$$$. Then, output a line of $$$n$$$ space-separated positive integers $$$w_1, w_2, w_3, \dots, w_n$$$, corresponding to the desired weight that you want each feather to have.
- This $$$n$$$ can be at most $$$15$$$.
- Each $$$w_i$$$ should be at most $$$10^8$$$
- You may have multiple feathers with the same weight.
Next, output a positive integer $$$M$$$, corresponding to the claim, "Using only these feathers, I can accurately determine the weight of any heart, so long as its weight is a positive integer not greater than $$$M$$$." Ultimately, the higher this $$$M$$$, the higher your score will be. You may output $$$M$$$ up to $$$10^8$$$.
Based on your chosen feathers, Anubis will now challenge your claim. The judge first outputs a positive integer $$$T$$$, meaning that $$$T$$$ test cases will follow. This $$$T$$$ will be at most $$$100$$$.
For each test case, the judge selects a heart with some positive integer weight. We will give this heart an index of $$$0$$$, and lets its weight be denoted by $$$w_0$$$.
To use the balance scales, output a line containing only the word WEIGH. Then, output these four pieces of information, describing which items you want to put in each pan.
- First, a positive integer $$$k_l$$$, the number of items going in the left pan.
- Then, $$$k_l$$$ non-negative integers $$$l_1, l_2, \dots, l_{k_l}$$$, the indices of the items going in the left pan.
- Next, a positive integer $$$k_r$$$, the number of items going in the right pan.
- Finally, $$$k_r$$$ non-negative integers $$$r_1, r_2, \dots, r_{k_r}$$$, the indices of the items going in the right pan.
Let $$$L$$$ and $$$R$$$ be the total weights of the items placed in the left and right pans, respectively. Formally, $$$$$$\begin{align*} L &= w_{l_1} + w_{l_2} + \dots + w_{l_{k_l}}, \\ R &= w_{r_1} + w_{r_2} + \dots + w_{r_{k_r}}. \end{align*} $$$$$$
The judge will give one of the following responses.
- > if $$$L \gt R$$$
- < if $$$L \lt R$$$
- = if $$$L = R$$$
- >:( if your query was invalid. Perhaps, for example,
- You attempted to place an item in more than one pan.
- You used an index not in the range $$$0$$$ to $$$n$$$
- You did not provide exactly $$$k_l$$$ or $$$k_r$$$ items to put in each pan.
You may perform as many queries as you want, so long as all test cases are answered within the time limit.
When you are ready to report the weight of the heart, output a line containing only the word VERDICT, and then output one of the following:
- If you believe that $$$w_0 \gt M$$$, output a line containing the words HEAVY
- Otherwise, you believe that $$$1 \leq w_0 \leq M$$$, and you should output a line containing the word EXACT. Then, output another line containing a single positive integer, the value of $$$w_0$$$.
- :) if your answer is correct. If so, the judge immediately proceeds to the next test case.
- >:( if your answer is incorrect, or if your reporting was otherwise invalid.
If the judge ever sends a >:( verdict, it will immediately terminate, and will send no further responses. In such a case, your program should terminate too.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline \text{If you receive a }\mathtt{:)}\text{ verdict on all test cases, then you will be awarded points based on how high your declared $M$ was.} \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{30} & M \geq 15 \\ \hline 2 & \mathbf{5} & M \geq 25 \\ \hline 3 & \mathbf{10} & M \geq 70 \\ \hline 4 & \mathbf{5} & M \geq 1000 \\ \hline 5 & \mathbf{20} & M \geq 32123 \\ \hline 6 & \mathbf{5} & M \geq 65456 \\ \hline 7 & \mathbf{15} & M \geq 7142857 \\ \hline 8 & \mathbf{10} & M \geq 14142135 \\ \hline \end{array}\\
\end{align*}$$$$$$
2
<
=
:)
>
:)6 1 1 2 3 5 8 15 WEIGH 3 1 3 6 2 0 5 WEIGH 2 4 5 2 0 2 VERDICT EXACT 7 WEIGH 1 0 6 1 2 3 4 5 6 VERDICT HEAVY
The blank lines are only used here to illustrate the interaction between the contestant and the judge. Do not actually print these extra lines in your program.
Cindy's slick shuffling and fancy flourishes have allowed her to successfully sideline as a freelance card dealer. She's going to need some extra assistance for today's client, though, as he is... extremely superstitious.
Cindy has been contacted by Fun-Day Master Franz Chua to assist in fortune-telling by use of some mystical numbered cards. Each mystical card contains a single digit from $$$0$$$ to $$$9$$$. For the fortune-telling, Cindy takes a deck that consists of some number of mystical cards, shuffles it well, and then deals all of its card out in a row, in one straight line. Then, we concatenate the digits from left to right to form a single non-negative integer (possibly with leading zeroes).
If the resulting number is divisible by $$$4$$$, then Fun-Day Master Franz Chua predicts that the client will be cursed to live a boring life for the rest of their days. Otherwise, he predicts that the client will have a wonderful and exciting week!
Of course, Fun-Day Master Franz Chua doesn't actually like handing out ill fortunes—it's bad for business! So, he calls a deck of mystical cards Four-Safe if it is absolutely impossible that the resulting number is divisible by $$$4$$$, no matter how the deck is shuffled and dealt.
In order to test that his hired dealer actually understands his fortune-telling process, Fun-Day Master Franz Chua will only hire Cindy if she can solve the following puzzle.
There are $$$n$$$ chests in Fun-Day Master Franz Chua's studio, labeled from $$$1$$$ to $$$n$$$. Each chest contains some number of mystical cards.
Cindy first selects $$$k$$$ of the chests. Then, using only the mystical cards in those chests, she must choose some of them to assemble a Four-Safe deck. Cindy doesn't have to use all the mystical cards in these chests. The goal is to make as large a Four-Safe deck as possible (i.e. one with the greatest number of mystical cards).
What is the largest possible Four-Safe deck that can be constructed by this process?
The first line of input contains two space-separated integers $$$n$$$ and $$$k$$$.
Then, $$$n$$$ lines of input follow, describing the contents of each chest. The $$$i$$$th chest is described by a string of digits $$$s_i$$$ on the $$$i$$$th line. Each digit of $$$s_i$$$ corresponds to a card in the $$$i$$$th chest with that digit written on it.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq k \leq n \leq 2\times 10^5 \\ \text{Each chest contains at least $1$ card.} \\ \text{There are at most $10^6$ cards in total.} \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & \text{There are at most $5$ cards in total.} \\ \hline 2 & \mathbf{23} & n \leq 10 \\ \hline 3 & \mathbf{17} & n \leq 15 \\ \hline 4 & \mathbf{19} & n \leq 2000 \\ \hline 5 & \mathbf{21} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
First, output a line with $$$k$$$ distinct space-separated integers from $$$1$$$ to $$$n$$$, corresponding to the indices of the chests you selected.
Let $$$m$$$ be the size of your Four-Safe deck. If $$$m = 0$$$, output the string empty. Otherwise, if $$$m \gt 0$$$, output a line containing a string of $$$m$$$ digits, representing the Four-Safe deck that you built. It must be possible to construct this string using only digits from the strings of the chests you selected.
If there are multiple possible answers, any will be accepted, so long as $$$m$$$ is maximized.
4 2 0004 169 269 7200
2 4 1970
4 4 444 4 4444 4
1 2 3 4 empty
The second sample I/O shows that we are always forced to select exactly $$$k$$$ chests, even if we don't use any of the cards from some (or all) of the chosen chests.
Cindy has been having fun with the video game that Alice recommended, Pokey Mans: I'm in Pain, but with the 'S'. Sure the game feels rushed, and it has a host of bugs and glitches and other technical problems that are quite frankly embarrassing for a franchise as large as Pokey Mans... but underneath all that garbage is a game that Cindy finds to be genuinely fun! It's just... a lot of garbage...
Cindy is a very competitive player, so she wants to unlock the incredibly powerful character, Golden Joseph, affectionately known as Golden Joe. Golden Joe will only join your team after you've acquired at least $$$x$$$ Joe-Bucks from exploring the world.
You get Joe-Bucks by finding Joe's secret treasure chests. There are $$$n$$$ different treasure chests whose locations are scattered throughout the map. Each treasure chest gives Cindy some Joe-Bucks when opened, but this amount is not fixed.
Each treasure chest has its own drop table, which is some list of $$$k$$$ non-negative integers. When you open some treasure chest, the game uniformly randomly selects one of the $$$k$$$ values from its drop table, and then gives you that many Joe-Bucks. Cindy can open as many treasure chests as she wants, but once opened, the treasure chest then disappears and cannot be opened again.
These treasures eventually respawn, but it takes a long time and Cindy is impatient. So, right now, with these $$$n$$$ chests, help answer Cindy's question: Is it possible for her to get enough Joe-Bucks to unlock Golden Joe? And if so, is it guaranteed? Or does she have to get lucky?
The first line of input contains three space-separated positive integers $$$n$$$, $$$k$$$, and $$$x$$$.
Then, $$$n$$$ lines follow, each describing the drop table of a treasure chest. Each drop table is described by a line containing $$$k$$$ space-separated integers, the contents of this drop table.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq x \leq 10^{9} \\ 1 \leq n, k \\ nk \leq 10^5 \\ \text{The values in the drop table are positive integers not greater than $10^8$.} \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{33} & k = 1 \\ \hline 2 & \mathbf{33} & nk \leq 20 \\ \hline 3 & \mathbf{34} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
- If it is certain that Cindy can get at least $$$x$$$ Joe-Bucks by opening treasure chests, no matter her luck, output ALWAYS
- If it is possible but not guaranteed to get at least $$$x$$$ Joe-Bucks by opening treasure chests, output SOMETIMES
- If it is impossible to get at least $$$x$$$ Joe-Bucks by opening treasure chests, output NEVER
3 4 5 3 1 4 1 5 9 2 6 5 3 5 8
ALWAYS
5 2 10 1 100000000 1 100000000 1 100000000 1 100000000 1 100000000
SOMETIMES
1 1 2 1
NEVER
1 6 999 30 50 10 100 200 777
NEVER
The moon drives me crazy
Ugh, the moonlight drives me nuts!
It's such an eyesore!
Alice is volunteering at a magical bunny farm in order to earn some extra credit for her biology class! Magical bunnies are peculiar in that each one can only be in one of three possible states: young, mature, or old.
The farm initially has $$$a$$$ young bunnies, $$$b$$$ mature bunnies, and $$$c$$$ old bunnies. Whenever Alice sacrifices a magical Moon Stone, the following three things happen simultaneously:
- Half of the young bunnies (rounded down) become mature; the rest die :(
- Each mature bunny gives birth to $$$3$$$ young bunnies. Then, half of the mature bunnies (rounded down) become old; the rest die :(
- Each old bunny gives birth to $$$1$$$ young bunny. Then, they all die :(
For her own personal reasons, Alice wants the farm to have $$$d$$$ young bunnies, $$$e$$$ mature bunnies, and $$$f$$$ old bunnies. However, she knows that getting those exact quantities is unlikely. So, she instead settles for aiming to be as close to her target as possible, for some definition of "close".
Suppose that currently, the farm has $$$x$$$ young bunnies, $$$y$$$ mature bunnies, and $$$z$$$ old bunnies. Then, Alice uses the following formula to compute the "square error": $$$$$$\begin{align*} \text{square error} ~ = (x - d)^2 + (y - e)^2 + (z - f)^2. \end{align*}$$$$$$
Find the minimum possible value of the square error, and also the minimum number of magical Moon Stones that Alice needs to sacrifice in order to achieve it.
Also, you must answer $$$T$$$ different test cases.
The first line of input contains a single integer $$$T$$$, the number of test cases.
Then, $$$T$$$ lines follow, each containing the six space-separated integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$, $$$e$$$, and $$$f$$$, corresponding to the values in each test case that must be answered.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq T \leq 100 \\ 0 \leq a, b, c \leq 100 \\ 0 \leq d, e, f \leq 10^8 \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline
1 & \mathbf{33} & 0 \leq a, b, c \leq 3 \\ && 0 \leq d, e, f \leq 3 \\ \hline
2 & \mathbf{33} & 0 \leq a, b, c \leq 10 \\ \hline
3 & \mathbf{34} & \text{No further constraints.} \\ \hline
\end{array}\\
\end{align*}$$$$$$
Output $$$T$$$ lines. For each test case, output the following two space-separated values.
- First, the minimum possible square error
- Then, the minimum number of magical Moon Stones that need to be sacrificed in order to attain this minimum square error
3 1 2 3 6 9 2 3 1 1 9 5 1 1 2 3 4 5 6
4 6 5 6 27 0
- In the first test case, after sacrificing $$$6$$$ magical Moon Stones, there will be $$$6$$$ young bunnies, $$$9$$$ mature bunnies, and $$$0$$$ old bunnies. This gives a square error of $$$4$$$, which we can show to be minimal.
- In the second test case, we can show that the minimal square error is $$$5$$$, which is achieved after $$$6$$$ or $$$8$$$ magical Moon Stones. We output $$$6$$$ since that's the smaller of the two and we want to use as few magical Moon Stones as possible.
- In the third test case, the minimum square error of $$$27$$$ is achieved if Alice just doesn't use any magical Moon Stones at all.
Bob decided that it would be fun to experiment with other mediums of art in his spare time. He started to enjoy art (and life!) a lot more when realized that he can just try out new and exciting things, without needing "permission" from an "official" curriculum. People he perceives as experts, or as ones living exciting lives, actually earned those labels by being proactive with their life experiences.
Today, Bob is playing around with stained glass tile mosaics!
Bob's mosaic can be described as an $$$n \times n$$$ grid, where each cell contains a translucent square tile that is colored either red or blue. Each tile is completely indistinguishable from any other tile of the same color, even if you rotate it around or flip it over. Bob hung the mosaic on a frame on the wall.
Cindy, enthralled by the art, wanted to observe it from a bunch of different angles. To that effect, she picked up the mosaic and applied some sequence of movements to the it. We can break these movements up into four main types of operations, which we show below.
- L to rotate the mosaic $$$90^\circ$$$ counter-clockwise
- R to rotate the mosaic $$$90^\circ$$$ clockwise
- H to reflect the mosaic horizontally (across its vertical axis)
- V to reflect the mosaic vertically (across its horizontal axis)
Unfortunately, when she was done, Cindy couldn't remember what the original mosaic looked like! However, she does remember the exact sequence of operations she performed. Given that information, please help Cindy recover the appearance of the original mosaic before Bob finds out.
The first line of input contains a single integer $$$n$$$.
Then, $$$n$$$ lines follow, each containing a string of length $$$n$$$. This encodes the $$$n \times n$$$ mosaic after all the operations have been performed. The colors red and blue are represented by # and . characters.
The next line contains the string $$$s$$$, encoding the operations in the order that they are performed on the mosaic. Each operation is described by a letter whose meaning is given above.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 3 \leq n \leq 750 \\ 1 \leq |s| \leq 5 \times 10^5 \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline
1 & \mathbf{20} & n = 3 \\ \hline
2 & \mathbf{25} & n \leq 12 \\ && \text{There are no }\mathtt{L}\text{ or }\mathtt{R}\text{ commands.} \\ && |s| \leq 1000 \\ \hline
3 & \mathbf{25} & n \leq 12 \\ && |s| \leq 1000 \\ \hline
4 & \mathbf{16} & \text{There are no }\mathtt{L}\text{ or }\mathtt{R}\text{ commands.} \\ \hline
5 & \mathbf{14} & \text{No further constraints.} \\ \hline
\end{array}\\
\end{align*}$$$$$$
Output $$$n$$$ lines, each containing a string of $$$n$$$ characters. This should represent the original mosaic before all the operations were performed.
3 .#. .#. ##. RHL
##. .#. .#.
12 ............ ......#..... ....#.#.#... ....#.#.#... ..#.#.#.#... ..#.#.#.#... ..#.#.#.#.#. ..#######.#. ..#########. ...#######.. ....#####... ....#####... LVR
............ .....#...... ...#.#.#.... ...#.#.#.... ...#.#.#.#.. ...#.#.#.#.. .#.#.#.#.#.. .#.#######.. .#########.. ..#######... ...#####.... ...#####....
12 ...######... ..#......#.. .#......#.#. #..#..#.#..# #.#.....#..# #.#.#......# #.#.##.....# #.#.....#..# #..#..#.#..# .#......#.#. ..#......#.. ...######... LHRVLLHRHLHVRHRLRVR
...######... ..#......#.. .#........#. #.###..###.# #..........# #..#....#..# #.....#....# #....##....# #..#....#..# .#..####..#. ..#......#.. ...######...
5 ..#.. .###. #.#.# ..#.. ..#.. VRHL
..#.. .###. #.#.# ..#.. ..#..
An evil race of aliens called the Rhombulans have invaded planet Earth! Rhombulans are characterized by two main traits. They hate music, to the point where their mission is to exterminate all music in all its forms throughout the galaxy. On the other hand, they love geometry! Which shape do they love the most? Well isn't it obvious...? It's the parallelogram!
The Rhombulans worship the parallelogram, to the point where it has bled into their war strategies, even at times where it would not be the most rational decision. Alice, Bob, and Cindy have been contracted as Elite Bit Agents, and it is their job to sort through all the binary code from the computers of defeated Rhombulans in order to gleam some useful military secrets.
Alice, Bob, and Cindy have unearthed that Rhombulan bases are located at the three non-collinear integer points $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$, and $$$(x_3, y_3)$$$. A completing point is one such that if they take it together with the three input points, then the four points form the vertices of a parallelogram; Alice, Bob, and Cindy believe that the final Rhombulan base is located at one such completing point.
Now, they need to give a report on the information that they have discovered regarding the possible locations of the final Rhombulan base. After all, there may be multiple possible completing points, and their generals need as much information as they can get in order to best decide where to send their troops.
Thus, you were assigned the following task. For each possible completing point, output the following pieces of information:
- What are the coordinates of this completing point?
- What is the area of the formed parallelogram?
- Is the formed parallelogram a rhombus?
- Is the formed parallelogram a rectangle?
Godspeed, agent. And remember: music LIVES!
Input consists of three lines, each containing the space-separated integers $$$x_1$$$ and $$$y_1$$$, then $$$x_2$$$ and $$$y_2$$$, then $$$x_3$$$ and $$$y_3$$$.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline -10^3 \leq x_1, y_1, x_2, y_2, x_3, y_3 \leq 10^3 \\ \text{$(x_1, y_1)$, $(x_2, y_2)$, and $(x_3, y_3)$ are not collinear.} \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{33} & \text{$y_1 = y_2$ and $x_2 = x_3$} \\ \hline 2 & \mathbf{33} & y_1 = y_2 \\ \hline 3 & \mathbf{34} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
If there are infinitely many completing points, output INFINITE.
Otherwise, if there are finitely many completing points, output each of them in sorted order; output the ones with smaller $$$x$$$-coordinates first, breaking ties by outputting the ones with smaller $$$y$$$-coordinates first.
For each completing point, output five lines:
Replace the values enclosed in angle brackets with the information describing each completing point, as follows:
point: <x> <y>
area: <a>
is rhombus: <yes/no>
is rectangle: <yes/no>
-------------------------
- <x> and <y> are the $$$x$$$ and $$$y$$$ coordinates of this completing point. Give each value to exactly two places after the decimal point, truncating the rest.
- <a> is the area of the formed parallelogram. Again, give the value to exactly two places after the decimal point, truncating the rest.
- <yes/no> on the third line is yes if the formed parallelogram is a rhombus, and no otherwise
- <yes/no> on the fourth line is yes if the formed parallelogram is a rectangle, and no otherwise
- This last line is just a "separator" to easily visually distinguish between different completing points; the - appears 25 times
The checker is strict. Do not even output extra spaces or newlines.
1 1 2 1 2 3
point: 1.00 -1.00 area: 2.00 is rhombus: no is rectangle: no ------------------------- point: 1.00 3.00 area: 2.00 is rhombus: no is rectangle: yes ------------------------- point: 3.00 3.00 area: 2.00 is rhombus: no is rectangle: no -------------------------
0 0 5 0 -3 4
point: -8.00 4.00 area: 20.00 is rhombus: no is rectangle: no ------------------------- point: 2.00 4.00 area: 20.00 is rhombus: yes is rectangle: no ------------------------- point: 8.00 -4.00 area: 20.00 is rhombus: no is rectangle: no -------------------------
Osu!
Cindy is helping manage a mixed martial arts tournament that is being hosted at her school. Now that the tournament is over, it's time to get all the competitors lined up for a ceremonial photo...
The tournament included $$$n$$$ martial artists from a variety of disciplines and backgrounds. Cindy's analytics team used an assortment of machine learning techniques in order to assign each competitor a distinct power ranking, an integer from $$$1$$$ to $$$n$$$ that describes their martial arts skill relative to the other martial artists. In this system, $$$1$$$ is the lowest ranking and $$$n$$$ is the highest ranking.
After all, if there's anything that Cindy learned from YouTube, it's that people love power rankings.
These $$$n$$$ martial artists then arranged themselves in a queue, in preparation for the final photo. We can describe their initial ordering by using a permutation $$$p_1, p_2, p_3, \dots, p_n$$$, where $$$p_1$$$ is the ranking of the person currently at the front of the queue, and $$$p_n$$$ is the ranking of the person currently at the back.
However, Cindy believes that she'll get the perfect thumbnail if this queue is sorted in ascending order. That is to say, each competitor must have a higher ranking than everyone in front of them in the queue.
To make sure things don't get too rowdy, Cindy only has the following two possible operations at her disposal.
- S to swap the positions of the two front-most people in the queue.
- P to tell the person at the front of the queue to move to the very back; then, everyone adjusts. In other words, we "pop" off the person currently at the front of the queue, then "push" them to the back of the queue.
The first line of input contains a single integer $$$n$$$.
The second line of input contains the $$$n$$$ integers $$$p_1, p_2, p_3, \dots, p_n$$$.
$$$$$$\begin{align*}
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{33} & 3 \leq n \leq 5 \\ \hline 2 & \mathbf{33} & 3 \leq n \leq 8 \\ \hline 3 & \mathbf{17} & 3 \leq n \leq 50 \\ \hline 4 & \mathbf{17} & 3 \leq n \leq 250 \\ \hline \end{array}\\
\end{align*}$$$$$$
Output a single string consisting only of the letters S and P, encoding the commands that you would like to give, in order.
If you would like to output the empty string (meaning no operations will be done), output empty instead.
Your solution will be accepted if this string has no more than $$$10^5$$$ characters. We can show that a solution always exists within these bounds. Note that you do not have to minimize the number of operations.
5 4 3 1 5 2
SPPSP
5 1 2 3 4 5
empty
Once again, Cindy finds herself playing a game that Alice recommended to her, in the hopes that they can get closer by bonding over their experiences in their playthroughs. That's not to say that the game isn't fun, though! There's lots to do in the world of Sushii, including a decent customization system which can let you try on a lot of different outfits.
The next map, the Scarlet Swamp, is a marshland and is full of lots of puddles of mud. A cool detail is that when Cindy's character steps into the mud, her outfit actual gets dirty, and stays dirty for a while too. Wow, realism! Well, unfortunately, Cindy loves her outfit so much that she would hate for it to get covered in mud...
The map of the Scarlet Swamp is represented as a grid with $$$R$$$ rows and $$$C$$$ columns. We let $$$(i, j)$$$ denote the square in the $$$i$$$th row from the top, and the $$$j$$$th column from the left. Each square can be one of three different types of terrain:
- . denotes open space which can be freely traversed
- # denotes a lava tile which will instantly kill Cindy if she walks into it
- $$$\tilde{}$$$ denotes a muddy tile which can be freely traversed, but doing so would make Cindy muddy as well.
In order to avoid getting muddy, Cindy can use any of the $$$k$$$ wooden planks that are littered around the world map. The squares $$$(i_1, j_1)$$$, $$$(i_2, j_2)$$$, $$$\dots$$$, $$$(i_k, j_k)$$$ each initially contain a single wooden plank.
Wooden planks can be placed on open space and muddy tiles, and Cindy can still walk on such tiles even if there are planks on them; in fact, if there is a wooden plank on a muddy tile, then when Cindy moves to that square, she steps on the plank, avoiding sinking into the mud. This is the only way to walk into muddy tiles without getting dirty.
Thus, Cindy's character also has access to two more helpful commands: get the wooden plank from the square she is facing; and put down the wooden plank she is holding onto the square she is facing. Note that after Cindy puts down a wooden plank somewhere, she is free to come back to it later and pick it up again.
Each square may only contain at most one wooden plank at a time. Cindy may only hold onto one wooden plank at a time, and she spawns into the world not initially holding a wooden plank.
Starting from her spawn point of $$$(r_s, c_s)$$$, Cindy needs to make it to the objective at $$$(r_t, c_t)$$$ without getting dirty. Can you help her figure out what to do? Of course, if the task is impossible, you should tell her so.
The first line of input contains the space-separated integers $$$R$$$ and $$$C$$$, the number of rows and columns in the grid.
The second line of input contains the space-separated integers $$$r_s$$$, $$$c_s$$$, $$$r_t$$$, and $$$c_t$$$, encoding the coordinates of the starting tile and the target tile.
Then, $$$R$$$ lines follow, each containing a string of length $$$C$$$. This encodes the world map of Sushii as a grid, with the meanings of each character described above.
Then, the next line contains a single integer $$$k$$$, the number of wooden planks in the world.
Then, $$$k$$$ lines follow, each containing a pair of space-separated integers $$$i$$$ and $$$j$$$ that describe the coordinates of some plank.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq R, C \leq 100 \\ \text{All wooden planks initially appear on distinct squares, and none are on lava tiles.} \\ \text{$(r_s, c_s) \neq (r_t, c_t)$ and both are guaranteed to be open space.} \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & k = 0 \\ \hline 2 & \mathbf{26} & k \leq 1 \\ \hline 3 & \mathbf{23} & \text{The map has no lava tiles.} \\ \hline 4 & \mathbf{11} & R = 1 \\ \hline 5 & \mathbf{20} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
If the task is impossible, output a line containing NO. Otherwise, output YES.
Furthermore, if your answer was YES, you should output another line containing a "command string," describing the moves that Cindy must perform so that she reaches the objective.
Each character in the command string corresponds to a certain action that Cindy's character can take:
- L: Cindy turns $$$90^\circ$$$ counterclockwise.
- R: Cindy turns $$$90^\circ$$$ clockwise.
- F: Cindy takes a single step forward in the direction she is facing. If this action would cause any of the following to happen, then you get an immediate Game Over (i.e. Wrong Answer)
- Cindy exits the bounds of the map
- Cindy steps into a lava tile
- Cindy steps into a muddy tile that doesn't have a wooden plank in it.
- G: If Cindy is currently not holding a wooden plank, and there is a wooden plank on the square she is facing: the wooden plank is removed from that square, and Cindy is now holding a wooden plank.
- In any other case, this command causes an immediate Game Over.
- P: If Cindy is currently holding a wooden plank, the square in front of her exists and is not a lava tile, and there is no wooden plank on the square she is facing: Cindy is no longer holding a wooden plank, and the square in front of her now contains a wooden plank.
- In any other case, this command causes an immediate Game Over.
Your command string will be accepted if it successfully brings Cindy to $$$(r_t, c_t)$$$ (it doesn't matter what direction she's facing) and if it is no more than $$$2 \times 10^5$$$ characters long. Note that the number of commands doesn't have to be minimized. It can be shown that, given the constraints, if a solution exists, then one exists that uses $$$2 \times 10^5$$$ commands or fewer.
2 3 1 1 2 3 .~. .#. 2 2 1 1 3
YES GLPFFRF
2 3 1 1 2 3 .~. .#. 2 1 1 1 3
YES FLLGFRPFFRF
4 3 4 1 1 2 #.. ~#. .#~ .~. 1 2 1
YES RRFGRRFLPFFRRGRPFFFLF
2 2 2 2 1 1 .~ #. 0
NO
Bob's Mondrianansala artworks from last year were so popular that his art teacher has tasked him with creating another collection of paintings for this year's STEM Exhibit. Bob, foolishly, accepts.
Bob's paintings will once again be composed entirely of rectangles, in what he calls the Mondriamorsolo style. This year, Bob wants his paintings to be even more gorgeously geometric, so he recalls the following definitions from math class.
Recall that two objects are congruent if one can be transformed into the other by some combination of rotations or reflections. Two objects are similar if one can be made congruent to the other by scaling it up or down by the same amount in all directions.
For example, consider the following image.
- The $$$4 \times 6$$$ rectangle would be congruent to any other $$$4 \times 6$$$ rectangle.
- The $$$4 \times 6$$$ and $$$6 \times 4$$$ rectangles are congruent because one is just a rotation of the other.
- The $$$2 \times 3$$$ rectangle is similar to the $$$4 \times 6$$$ and $$$6 \times 4$$$ rectangles, because it can be made congruent to both of them by scaling by a factor of $$$2$$$ in all directions.
Bob wants all rectangles in his painting to be irreducible, which he defines as follows:
- A rectangle is reducible if it has integer side lengths, and if it can be cut up into some number of non-overlapping rectangles that satisfy the following conditions,
- They all also have integer side lengths
- They are all congruent to each other
- They are all similar to the original rectangle
- If not, then the rectangle is irreducible.
Now, the problem. A painting is in the Mondriamorsolo style if it satisfies all of the following criteria.
- It is painted on an $$$n \times n$$$ canvas.
- The painting is entirely composed of exactly $$$n$$$ rectangles with positive integer dimensions, and all of these rectangles are irreducible
- No two rectangles in the painting are congruent to each other.
- Each rectangle is painted one of $$$26$$$ different colors, and the entire rectangle is painted that color.
- No two rectangles that touch at their edges may have the same color (though rectangles of the same color may touch at corners).
Given a positive integer $$$n$$$, help Bob by producing any painting of that size in the Mondriamorsolo style, or say that no such painting exists.
Input consists of a single line that contains a single integer $$$n$$$.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq n \leq 1200 \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{30} & 1 \leq n \leq 8 \\ \hline 2 & \mathbf{16} & \text{$n=1$ or $n = 1000$} \\ \hline 3 & \mathbf{16} & \text{$n=1$ or $n = 1011$} \\ \hline 4 & \mathbf{16} & \text{$n=1$ or $n = 1200$} \\ \hline 5 & \mathbf{11} & 1 \leq n \leq 100 \\ \hline 6 & \mathbf{11} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
If the task is possible, output YES. Otherwise, output NO.
If YES, also output the painting. We will treat the painting as a pixelmap and represent it as an ASCII grid.
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.
1
YES A
2
NO
7
YES CAABBBC BAABBBC BAABBBC BAABBBC BAABBBC BAACCCB BAACCCB