You, Jacob Slowden, have been hired by the Children of Immortal Agents (CIA) to put a wrench into the Not So Advanced's (NSA's) operations.
Working at the pace of a wolf, which is ironically not that fast—only once every full moon—you go ahead and break into the NSA's system to slow them down. After all, if you are slow, then your enemies must be slowed down as well, keeping your name true to its meaning.
As the NSA was not very advanced, it was very easy for you to gain access to their system. Of course, this does not necessarily mean that you were able to do it fast. In any case, you were still surprised with what you saw. Unencrypted passwords. Basic network configuration. Even Ronald Gump's Tweeter had better security.
Their passwords were already unencrypted, so what else could you do? After thinking for a while, you decided on swapping the passwords between all of their user accounts.
Of course, it wouldn't be good if they suddenly got completely locked out of their account. Even they would be suspicious if that happened. So whenever they try to log in, you give a hint saying how close they are from the correct password. Specifically, you measure this in terms of how many "moves" it would take to turn it into the correct password: one addition, deletion, or replacement of one character counts as one "move". You seem to recall from your Cryptographic Secrets training that this was called the Leviathan distance or something. Or wait, was that a character from the game Decryption of the Aged?
After thinking about how to do this, you now go on to implement your hints:
Note that passwords may contain spaces, and passwords are case-sensitive and space-sensitive.
The first line of input starts with an integer $$$t$$$, the number of test cases.
Each test case consists of two lines.
The first line of each test case consists of a single string containing the entered password.
The second line of each test case consists of a single string containing the correct password.
Constraints
For each test case, output a single line containing (without the quotes)
5 password password password passw0rd password pazzword password pazzw0rd password username
You're logged in! You almost got it. You're wrong in just one spot. You almost got it, but you're wrong in two spots. You're wrong in three spots. What you entered is too different from the real password.
Taal is erupting; panic ensues, hundreds are fleeing, horses are burning, and another island is forming in the lake (Yellow Lake) inside the island (Volcano Island) inside the lake (Taal Lake) inside the island (Luzon). It looks like the world is ending, but you are unfazed through the crisis. You have no reason to worry, being part of the Craters of Utmost Precedence Society (C.U.P.S) - citizens studying interesting volcano craters since time immemorial. With that, a plan to stop the eruption forms!
Taal threatens to devour Batangas and turn all its citizens into Pompeii and Herculaneum, but with your trusty C.U.P.S. standard issue handbook you figure out that there are $$$n$$$ craters from which lava is flowing from. If left unchecked, these craters will erupt in (also) $$$n$$$ days. Each of the $$$n$$$ craters have one of two states:
A quick survey of the area gives you the state of each of the $$$n$$$ craters $$$S$$$, with $$$S_i$$$ denoting whether the crater is open or not. The cataclysm threatened by Taal will be neutralized if and only if all craters have been completely filled with ash after at most $$$n$$$ days.
To completely fill the craters, your faithful dog (and best friend - because dog is man's best friend <3) Roro can piss on the craters, turning the lava into ash. To this effect you choose $$$m$$$ craters each day for Roro to visit, which can be different or same every day. However, you realize that he's not the brightest of the bunch: he misinterprets your long-term actions into short-term gains, and will always visit exactly $$$m$$$ (no more, no less) craters each day, even if that crater has already been filled with ash. To make matters worse, Taal's volcanic ash is the main component of Roro's favorite food ashbu! If he arrives at a crater currently filled with ash, he will devour the ash inside the crater, opening it again!
Now, you have to plan your actions properly. Given $$$n$$$, the number of craters to completely fill up and consequently the number of days we have, the number of craters $$$m$$$ Roro visits each day, and the inital state of the craters $$$S$$$, find the commands that completely fills Taal volcano if it is even possible, within $$$n$$$ days, or if it is impossible, say so.
The first line of input contains integer $$$t$$$, the number of test cases. $$$t$$$ test cases follow.
Each test case is composed of two lines. The first line contains two space-separated integers $$$n$$$ and $$$m$$$:
The second line of a test case contains the initial state of each crater $$$S$$$. $$$S$$$ is represented as a binary string, with $$$S_i$$$ either being $$$0$$$ or $$$1$$$:
Constraints
For each test case, do the following:
If it is impossible to stop Taal, output the following exact string in a single line:
"CATACLYSM IMMINENT - TIME TO HOARD FACE MASKS"
(without the quotes).
If there is a way to stop Taal, output the craters Roro needs to visit each day in the following format:
There may be multiple possible ways to stop Taal within $$$n$$$ days. In that case, output any of the valid solutions.
1 4 2 1100
3 1100 0011 1100
In the first test case, Taal starts with the first two craters open: 1100. We have to find a way to fill all of these craters in at most $$$4$$$ days, choosing $$$2$$$ craters each day. We achieve this by choosing the first two craters on the first day, last two craters on the second day, and the first two craters (again) at the third day. By the end of the third day, all craters will be filled up:
Valentine's Day was just around the corner, but Kouhai still hasn't confessed to Senpai at the Academy of Covert Machinations (ACM)! But alas, Kouhai knows that even if they do confess, it's all for nothing as Senpai has a track record of rejecting every single guy that confesses to her.
Senpai evaluates potential suitors using $$$q$$$ qualities. These qualities are also weighted with $$$W$$$ (where $$$W_i$$$ is the multiplier for the $$$i$$$th quality). Your quality scores is denoted by $$$P$$$, where $$$P_i$$$ is your score for the $$$i$$$th quality. For example, if the your score for quality $$$P_1$$$ is $$$3$$$, and it is weighted with $$$W_1 = 3$$$, your effective quality score is $$$3\times 3 = 9$$$. Obviously, a bigger quality score is better. Likewise, a smaller (or even negative) quality score hurts chances of getting Senpai to notice you.
Likewise Senpai has her own quality scores $$$S$$$, where $$$S_i$$$ is the score for the $$$i$$$th quality. You want to compare this with your own quality scores $$$P$$$. If $$$$$$\sum_{i=1}^{q} S_i \leq \sum_{i=1}^{q} P_i\cdot W_i$$$$$$ (i.e. your total sum of weighted qualities are at least the same as Senpai's), Senpai is then impressed and will accept your confession! $$$\heartsuit$$$ $$$\heartsuit$$$ $$$\heartsuit$$$ $$$\heartsuit$$$
However, a complicating factor is the fact that Senpai's qualities/standards change continuously over time, and can be represented using the equation: $$$$$$ S_i(t) = F_i\cdot t + C_i $$$$$$
In this equation, $$$t$$$ represents the time passed so far, $$$F_i$$$ represents the change rate factor for the $$$i$$$th quality, and $$$C_i$$$ is the constant factor for that quality. We can assume that at the start, $$$t = 0$$$, and that $$$F_i$$$ and $$$C_i$$$ are constants.
Since you're pretty average, all of your quality scores $$$P$$$ start out at zero too ($$$P_i(0) = 0$$$ for all $$$i$$$). To catch up, you have a growth rate limit $$$g$$$, which denotes the limit at which you can improve your quality scores as described by the following formula: $$$$$$ \sum_{i=1}^{q} \left(\frac{d}{dt}P_i(t)\right)^2 \leq g^2 $$$$$$
This means that the combined magnitude of all rate of changes in qualities is less than or equal to $$$g$$$. The rate of change $$$\frac{d}{dt}P_i(t)$$$ doesn't even need to be positive or constant — the total magnitude just needs to be less than or equal to your growth rate limit $$$g$$$.
Each quality score as a function of time, $$$P_i(t)$$$, can then be any continuously differentiable function as long as they satisfy the above condition.
Combining all aforementioned equations to compare to Senpai's score: $$$$$$\begin{align*} P_i(0) &= 0 \, \text{for all $i$ from $1$ to $q$}\\ \sum_{i=1}^{q} \left(\frac{d}{dt}P_i(t)\right)^2 &\leq g^2 \\ S_i(t) &= F_i\cdot t + C_i \end{align*}$$$$$$
And to win Senpai's heart, it must be true that $$$$$$\sum_{i=1}^{q} S_i(t) \leq \sum_{i=1}^{q} P_i(t)\cdot W_i.$$$$$$
Help Kouhai find the smallest $$$t$$$ that can satisfy the above criteria assuming he improves his qualities $$$P_i(t)$$$ optimally.
The first line of input contains a single integer $$$c$$$ denoting the number of test cases. The descriptions of the $$$c$$$ test cases follow.
The first line of each test case contains two space-separated positive integers $$$q$$$, and $$$g$$$; the number of qualities Senpai is looking at $$$q$$$, and Kouhai's growth limit with respect to time $$$g$$$.
A line containing $$$q$$$ space-separated integers follows, representing the weights $$$W_i$$$. The $$$i$$$th integer corresponds to $$$W_i$$$, the weight for the $$$i$$$th quality.
$$$q$$$ lines then follow, describing how Senpai's standards change over time. The $$$i$$$th line from which contains two space separated integers $$$F_i$$$ and $$$C_i$$$, the change rate factor and the constant factor for the $$$i$$$th quality ($$$S_i(t) = F_i\cdot t + C_i$$$).
Constraints
For each test case, output a single line containing a single nonnegative real number $$$t_{\min}$$$, the earliest possible time $$$t \geq 0$$$ that Kouhai can win Senpai's heart.
Answers with an absolute or relative difference of at most $$$10^{-10}$$$ from the judge's answer will be accepted.
1 4 4 1 1 1 1 1 3 2 3 2 3 1 3
6.00000000000
The optimal way to achieve Senpai's standards is by distributing your growth rate like below:
This satisfies the constraints $$$$$$P_i(0) = 0$$$$$$ and $$$$$$\sum_{i=1}^{q} \left(\frac{d}{dt}P_i(t)\right)^2 \; \leq \; g^2.$$$$$$ With $$$P_i(t)$$$ like this, the earliest $$$t$$$ where $$$$$$\sum_{i=1}^{q} S_i(t) \leq \sum_{i=1}^{q} P_i(t)\cdot W_i$$$$$$ is $$$t = 6.0$$$. (Calculate the resulting $$$S_i(t)$$$ and $$$P_i(t)$$$ values to see.)
It can be shown that this is the minimum possible such $$$t$$$, among all possible choices of the $$$P_i$$$s.
The past year has not been very great for you and your team. So many embarassing mistakes have been made. And very public ones at that. With the advent of the Weirdly Wide Web, everyone now knows what you're doing. Clips of your team have been uploaded to the "Cloud" and anyone can watch it via UTube.
For instance, there was that one time when you tried to track an IP address using the GUI interface that you created with Visual Advanced.
Or that time when a hacker broke past your team's firewall, swiftly causing sparks to fly and creating actual fire in your department.
That time when you tried to launch a cybernuke.
Or asked the CCTV guy to rotate the picture 75 degrees around the vertical.
Of course, nothing beats the time when a computer virus took over during Freedom Day. As any beginning progammer can tell you, binary code is a series of ones and zeroes. The virus turned ones into zeroes and zeroes into ones, effectively reversing your code.
The list goes on. Downcast at this very long list of blunders, you wonder how you and your team will move forward. Fortunately, your VP, also known as Vision Possible, steps in and tells you of a plan to turn the situation around.
He calls it the "Move to Remove Confidential Blunders (MTRCB)". Explaining further, he says that the past mistakes were due to unsupervised access to usually confidential documents, movies, and other secrets. The key, therefore, is to implement a chain of command according to each person's capability, which is of course measured by age. Obviously, age determines everything about a person. It is a hierarchical world we live in, after all.
While you stand amazed at Vision Possible's ability to do the impossible, the MTRCB's rules are explained to you. Since generally, people are already responsible when they turn 18 years old, you now have these rankings:
Now, you must do your part in implementing these rules. You do your best as your team's success depends on this. Given a person's age, the corresponding ranking, and the title of what that person wants to access, say if you should grant access to that person.
There is only one test case per file. The test case is formatted in two lines.
The first line contains an integer $$$a$$$ denoting the age of the person that you are checking access for, followed by a space, and then followed by a string denoting the corresponding ranking of what that person wants to access.
The next line contains the title of what the person wants to access.
Constraints
Output a single line containing (without the quotes):
18 R-18 Frozen 3
OK
1 R-13 Star Wars: The Fall of Skywalker
ACCESS DENIED
13 PG Agent Cody Banks
OK
1000 G Die Hard: Finally Die
OK
15 R-16 Blaze Runner: 2049
ACCESS DENIED
9 PG Hunger Games: Catching Firaga
OK IF ACCOMPANIED
10000 R-18 Karate Adult
OK
123456 G Min Payne
OK
1 G Mark of the Mini-Ninjas
OK
420 R-13 Team Fortress 5
OK
17 R-18 Heneral Looney
ACCESS DENIED
Ha HAHa haHA! You are the Mysterious Criminal Absconder, cunning trickster and nemesis of the Academy of Covert Missions.
Currently, you are on the top floor of their headquarters. HAHAHAh haha HAHH! (That's your "I'm hiding in my enemy's HQ" cackle.) In your hands is the top floor's floor plan in the form of a $$$r \times c$$$ grid. Each cell is a $$$1 \times 1$$$ square meter of space that is either a wall, a door, or an empty space.
You want to plant a bomb on this floor, and are planning to trigger it once someone enters the floor from downstairs. You've hacked the security system such that at most $$$k$$$ doors are allowed to be open at once. Once the agent arrives, all doors will be shut. From their current cell, they are only able to 1) walk to an adjacent cell that is either an empty space or an open door, or 2) open or close a door which is at a adjacent cell, both of which will take $$$1$$$ second each time they choose to do it. Of course, the agent will not be able to step on any space outside the floor plan's grid; they would fall out of the building.
Now, you've always loved playing games with this organization. To keep the game fair, you're going to have to plan this carefully in order to give them a chance to defuse this bomb. You must select 1) the cell where the agent will enter the floor and 2) the cell where the bomb will be, and determine if it is possible for them to reach the bomb. If it is, they must do so in the minimum time possible, else they will say goodbye to many precious files in their building.
Given the floor plan and the planned locations the two empty cells containing the agent's entrance and the bomb, would it be possible for the agent to defuse the bomb? If yes, what would be the minimum time for them to arrive at the cell containing the bomb?
Note: Two cells are considered adjacent if they share a common side.
The first line of input contains $$$t$$$, the number of test cases.
The first line of each test case contains three space-separated integers $$$r$$$, $$$c$$$ and $$$k$$$. The $$$i$$$th of the next $$$r$$$ lines contains a string of length $$$c$$$ denoting the $$$i$$$th row. It consists of the following characters:
Constraints
For each test case, output a single line containing:
2 3 12 3 ....D...#.#B A#.D.D..#.#. .D..D...D.D. 7 11 8 ......#.... ......#..B. ##....#.... ..#....#### ...#...D... ...D...D... ...#...#.A.
19 HAHAHUHU
You've spent the past couple of years as a Chugent, fulfilling various types of missions. You've infiltrated the Pentacontagon. You prevented the bombing that attempted to kill the not-so-rich King P'Taka. Despite doubts, you were also able to apprehend the master thief Pin Lu V. Amidst all these, you kept up with your daily regimen: 100 push-ups, 100 sit-ups, 100 squats, and a 10 km run. You kept at it every single day. You feel healthier than ever, but you think that your age is catching up to you as you notice your hair thinning for some reason.
With these thoughts in mind, you go to your mentor, the Great Spaitama. You tell him that it's time to be promoted from a Chugent to a full-fledged Jogent. He agrees, and presents you with a final test. He takes off and runs a few kilometers worth, but you are able to quickly follow him due to your daily training. You end up at the roof of what looks like a giant warehouse. You find and examine a secret door, and realize that it uses locks that are among the hardest to break into in the world. Thankfully, you are with no other than the Great Spaitama, who can open any lock with just ONE kick! It's not your first time seeing his technique, but you are still amazed at how he can kick the lock open without making any sound.
With the door open, you can now see the big rectangular room below you, and attached on one of the walls, you see something shiny.
"Is that a cheese grater?", you ask.
The Great Spaitama replies, "Not quite. You use it for fruits, and is worth a couple of thousands. A small, soft-spoken, client approached us to steal it."
He continues, "Note the floor tiles below. There are blue, red, and white tiles. Upon stepping on a blue tile, you end up turning and moving to your right. Stepping on a red tile sends you to your left. White tiles cause you to move forward."
He then hands you a pair of gloves. "Use these to stick onto the wall. Unfortunately, I can't drop you to the wall directly, and can only drop you on ONE specific tile. You can choose the direction (north, south, west, east) that you will be facing though. You just need to end up on a tile that will push you towards the wall. Let's call the border of a tile adjacent to the wall a "wall segment". You just need to end up at any of those wall segments; getting to the grater will then be easy with those gloves."
The following illustrates the "wall segments". There are five wall segments at the top and bottom walls each, and three wall segments at the left and right walls each.
"ONE last thing. Should you need it, I can help you change a white tile to either blue or red. Only ONE though, or it would be too easy for you. Understood?"
You tell The Great Spaitama that you are ready to begin. You still don't get his affinity with the number ONE. In any case, you try to impress him by not only getting to ONE wall segment, but telling him that you can actually get to other wall segments as well.
How many distinct wall segments can you possibly reach, if you can change at most one white tile to either blue or red?
The first line of input contains a single integer $$$t$$$ denoting the number of test cases.
The first line of each test case contains two space-separated integers $$$h$$$ and $$$w$$$ denoting the height and width of the grid, respectively.
The next $$$h$$$ lines each contains a string of length $$$w$$$ denoting a row of the grid (from top to bottom). Each string consists of the following characters:
Constraints
For each test case, first output a single line containing a single integer $$$d$$$ denoting the number of distinct wall segments you can reach. Then, print $$$d$$$ lines describing these wall segments. Each of these lines contains a character $$$x$$$, a space, and then an integer $$$k$$$.
Output the wall segments in sorted order, first by increasing $$$x$$$ (alphabetically) and then by increasing $$$k$$$.
2 3 5 RBWWW WWWWW SWWBW 5 1 W W R W S
10 B 1 B 2 B 3 B 4 L 1 L 2 L 3 R 1 R 2 T 3 6 B 1 L 3 L 4 L 5 R 4 R 5
The following illustrates the sample input:
The gray wall segments cannot be reached. The remaining wall segments can be reached.
While fooling around at work today your boss, the head producer at Accelerated Creator of Movies (ACM), gives you a large list:
James Bold: Fingers
Missionary Possible: Callout
John Licks 3: Caramellum
Tom Clancy's Jack of Ryan
Fasting and Furious: Hobos with Shows
... (many more movies)
Your boss then tells you: "Slick, high-octane, spy thriller movie franchises are popular nowadays! Make $$$n$$$ movies like that!" and immediately leaves. With your jobs on the line, your hardworking team of writer-producers create the generic genre perfect spy movie scenario for you:
Seems good, right? You have just called all the agents your connections could afford, and not only they give you a list of $$$a$$$ actors to cast, but also that they have already booked the actors for the first episode! The only thing left is to decide the casting for the $$$n-1$$$ movie episodes left - but you remember that you can only change 1 slot in the cast after every movie ($$$1$$$ leaving the slot, $$$1$$$ arriving at that slot the next).
Given a list of actors $$$a$$$ and the initial lineup of $$$g$$$ cast members, list the cast changes needed to reach $$$n$$$ movies.
The first line of input contains $$$t$$$, the number of testcases.
Each test case consists of three lines:
Constraints
For each test case, output $$$n - 1$$$ lines, each containing two space-separated lowercase strings $$$a_\text{out}$$$ (actor being replaced) and $$$a_\text{in}$$$ (actor coming in).
Output a single blank line before the output of every test case except the first one.
There may be multiple valid answers; any one will be accepted.
2 2 4 4 ali bob carl dude ali bob 2 4 5 ali bob carl dude earl carl dude
bob carl carl dude ali bob dude earl carl dude dude ali
Cast list for the first test case (bold text means a cast change occured):
Two best friends Maggie and Dana attend church mass at their hometown every Monday. They usually wake up at 10:00 am, attend mass at 11:23 am (the priest is really strict with regards to time), and finish at 3:00 pm. After that, most of their free time is spent reading books, finding stories, and keeping up to date with the news.
Today however, November 23 is a special day for both of them, as there's a supper happening this evening in their honor. Their other best friend Esmael has invited 58 guests in to his house to celebrate! Obviously, Maggie and Dana are very excited to attend the supper.
There's a slight problem though: the supper is located at the other end of region, so they have to walk across to get there! The region can be represented as an $$$\ell \times w$$$ rectangular grid, where the upper left corner is the church where Maggie and Dana will be coming from, and the bottom right corner being the supper location. Maggie and Dana can only move either directly downwards or rightwards (towards the destination).
Local bullies Andall and Zaldie hear about this, so they decide to make it hard for Maggie and Dana to get there. They decide to block specific parts of the region to limit Maggie and Dana's movement. For example, for $$$\ell = 7$$$ and $$$w = 5$$$:
...####
#...###
##...##
###...#
####...
Here, # represents a cell that is blocked, and . represents a cell that is not blocked.
They only leave a cascading path $$$\ell - w + 1$$$ wide for Maggie and Dana to get through! Maggie and Dana note that this is only possible due to their home province's unique geography, where its length is larger than its width ($$$\ell \gt w$$$). The cascading path shifts to the right by $$$1$$$ step for each row down in the region, where it ends at the bottom-right corner.
Now, Maggie and Dana want to know how many ways they can get to Esmael's supper, given that they are being blocked by Andall and Zaldie. Help them find that out!
The input consists of a single line containing two space-separated integers $$$\ell$$$ and $$$w$$$, the length and width of the region Maggie and Dana live in.
Constraints
Output a single line containing a single integer denoting the number of paths Maggie and Dana can take from the upper left corner (the church) to the bottom right corner (Esmael's supper), assuming Andall and Zaldie blocked the region in the way described above. Since the answer may be very large, only output it modulo $$$104857601$$$.
7 5
16
Congratulations, comrade! You have won the labor ticket.
Report to the Auditing and Census Ministry (ACM).
Company Olympichia has been infiltrated by capitalists.
Algotzkan government needs to determine severity.
Your orders: evaluate compromisation for all inquiries.
Glory to Algotzka.
The structure of Company Olympichia is best described as a rooted tree. $$$n$$$ employee details have been given. Each detail includes which employee is the superior of another, and if they are suspected capitalist spies, or patriotic socialist comrades.
The Ministry has been given $$$q$$$ inquiries. Each inquiry contains an employee $$$i$$$ to be investigated, number of filthy capitalist spies $$$c$$$ and number of upstanding socialist comrades $$$s$$$.
You are required to give report on chain of command for each inquiry. A valid chain of command for employee $$$i$$$ is any connected subgraph that is rooted at $$$i$$$.
If there exists a valid chain of command with exactly $$$c$$$ cowardly capitalist spies and $$$s$$$ peerless socialist comrades, then company is compromised. Otherwise, it is not compromised.
Photos taken from https://munkahelyiterror.blog.hu/2012/07/17/lekurvazott_es_fizikailag_bantalmazott_az_elelmezes_vezeto and https://ycl.org.uk/ licensed under https://creativecommons.org/licenses/by-nc-nd/3.0/
There is one test case for each input file.
Input starts with one line containing two space-separated integers $$$n$$$ and $$$q$$$, the number of employees and inquiries respectively. The employees are numbered from $$$1$$$ to $$$n$$$.
The second line contains a list of $$$n$$$ space-separated integers $$$E_1, E_2, \ldots, E_n$$$: the Olympichia employee details given to you by the government of Algotzka. The $$$j$$$th number $$$E_j$$$ in the list corresponds to the employee number which is the direct superior of the one in the list. The first number in this list $$$E_1$$$ (counting starts at $$$1$$$) is always the root node for the entire company; we will denote this by having $$$E_1 = 0$$$.
The third line contains a string of length $$$n$$$, $$$A = A_1A_2\ldots A_n$$$ denoting the affiliations of the Olympichia employees described above. The $$$j$$$th character, $$$A_j$$$, can only be one from the following:
Then $$$q$$$ lines follow. Each line contains three space-separated integers $$$i$$$, $$$c$$$, and $$$s$$$. This represents each inquiry made by the Algotzkan government.
Constraints
Output one line for each inquiry, containing the result of the investigation (without the quotes):
5 3 0 1 2 3 4 CSCSC 1 3 2 1 2 2 2 2 1
COMPROMISED COMPROMISED NOT COMPROMISED
Spies are usually seen with a cocktail or some other booze in hand. Even if you don't actually like cocktails yourself, at the very least you'd have to blend in to find your target in their favorite bar. After all, shady business transactions are usually done in such dark, relaxing, and hidden places. Sneaking something into your target person's drink is something that you, the best spy in the world, have done many times, and you have just been assigned another target to add to your super long long list of successful missions.
Except that this time, your target is an Asian king named Mr. Bin. And Mr. Bin doesn't like cocktails. Instead, after gathering intel, you found out that Mr. Bin has negligible ankles, likes coffee, and has a very adorable cat named Soseol. Your colleagues thought that you were slacking off when they saw you scrolling through Tweetur, but you were actually browsing Mr. Bin's daily posts of himself, his coffee, and his cat at the subtle coffee shop Covert Feline caFe. You were totally doing research and not spending hours looking at Soseol.
You don't know what Mr. Bin did to become a target, but you were told to disguise yourself as a barista at the Covert Feline caFe and put some sugar in Mr. Bin's favorite coffee drink. You don't know why it's sugar specifically since you usually used some other harmful substance in your past missions. Maybe it's to ruin his diet (pure evil). Or maybe he's actually allergic to sugar, who knows?
Sneaking in the sugar is the easy part. The trickier part is preparing the coffee, since you have never prepared coffee before. You don't drink coffee as you never needed the extra caffeine, being the excellent spy that you are. Upon observing the cafe, you noticed that there are three dispensers (cold, neutral, and hot), each giving water at a specified temperature. To prepare Mr. Bin's drink, the water has to be within a certain temperature range, and you achieve this by getting and mixing water from the three dispensers. When you mix water this way, the resulting drink gets the average temperature of the three dispensers, weighted by their respective volumes.
Furthermore, cats usually run around the cafe, causing the dispensers to malfunction. Each dispenser has a chance of malfunctioning, and when it does, it could end up dispensing water with the temperature of the other dispensers instead. At most one dispenser malfunctions.
As you need to be in perfect disguse as a barista, you should be able to know the volume of water that you will get from each dispenser. You must select it in a way that maximizes the probability that the drink ends up with a temperature that is within the acceptable range.
You may get any nonnegative real amount of water (in milliliters) from each dispenser, as long as the total volume is exactly $$$1000$$$ milliliters.
The first line of input contains an integer $$$b$$$, the number of Covert Feline caFe branches that Mr. Bin visits, followed by the descriptions for each branch.
The first line of each branch contains three integers $$$t_1, t_2, t_3$$$ denoting the respective temperatures for the three dispensers (cold, neutral and hot), separated by single spaces.
The second line for the branch contains three fractions denoting the respective probabilities of the three dispensers to malfunction, separated by a space. The $$$i$$$th fraction, $$$m_{i,\text{(n)}}/m_{i,\text{(d)}}$$$, denotes the probability that the $$$i$$$th dispenser malfunctions.
Then three lines follow. Each of these lines contains three probabilities separated by single spaces, expressed as a fraction of two integers. The $$$j$$$th fraction in the $$$i$$$th line, $$$d_{i,j,\text{(n)}}/d_{i,j,\text{(d)}}$$$. represents the probability that the $$$i$$$th dispenser releases water at the temperature of the $$$j$$$th dispenser if the $$$i$$$th dispenser malfunctions.
The next and final line for the branch contains two space-separated integers $$$l$$$ and $$$u$$$, where $$$l$$$ and $$$u$$$ are the lower and upper bounds for the acceptable range of temperatures. The bounds are inclusive.
Note: The temperatures and volumes are given in units used internally by spies. As these are used in the secret formulas for certain secret substances, the actual conversions to common SI metric units are not disclosed publicly.
Each probability is written as x/y where x and y are integers.
Constraints
For each branch, output a line containing a single fraction denoting the maximum probability that the drink is within the allowable temperature range, if the amounts obtained from the dispensers are chosen optimally. Print it as a fraction "x/y" (without the quotes) in lowest terms and with positive denominator. If the probability is $$$0$$$, output "0/1" (without the quotes). If the probability is $$$1$$$, output "1/1" (without the quotes).
1 37 38 39 1/5 3/5 1/5 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 36 38
14/15
"Beats like digits. Every beat is one. Every rest is a zero. Binary code. That's why all those assassins tried to save my life. It was hidden on me, hidden inside my head. A few simple lines of computer code that can break into any system."
Armed with this very dangerous weapon, you now need to send this information to your trusty friend John. Unfortunately you and John have no access to things like HTTPS or encrypted e-mail. Instead, you have agreed beforehand to send the needed numbers in the following very elaborate manner: You will send a total of $$$n$$$ people to John's apartment. Then John will record every person's weight in micrograms and height in nanoinches. After $$$n$$$ people visit in total, John can now extract the secret computer code as precisely the (integer) sequence of weights (in micrograms) if the $$$n$$$ people are sorted by height.
You already have these "encrypted" numbers. Can you verify that you can get back the secret computer code?
It is guaranteed that no two people have the same height (in nanoinches).
The first line of input contains a single integer $$$n$$$.
The second line of input contains $$$n$$$ space-separated integers $$$w_1, w_2, \ldots, w_n$$$ denoting the weights of the $$$n$$$ people in micrograms.
The third line of input contains $$$n$$$ space-separated integers $$$h_1, h_2, \ldots, h_n$$$ denoting the heights of the $$$n$$$ people in nanoinches.
Constraints
(In other words, some of these people are microscopic.)
Output a single line containing $$$n$$$ space-separated integers denoting the secret computer code.
3 2 1 4 1 4 3
2 4 1
Tasked with finding new recruits for the Division of Cryptographic Secrets, you put up a place where you can observe people's talents in finding clues, solving puzzles, and uncovering mysteries: an Escape the Room game!
You've thought of something that can be used to unlock one of the doors in the Room. To get feedback, you've approached your friends Andy, Natalie, and Dylan.
You ask them, "Complete the pattern: 1, 2, 3, 5, X. What is X?"
Andy quickly answers, "8! Isn't it just the Fibonacci sequence?"
Almost immediately, Natalie says, "Could also just be the roots of $$$x^5 - 19x^4 + 129x^3 -389x^2 + 518x - 240$$$."
Dylan then adds, "Isn't it a bit ambiguous? Technically you could have any piecewise function. How about adding some constraints?"
You take their feedback into account. After contemplating for a bit, you propose a variant. "Alright, how about this. Given the sequence, output $$$n$$$ distinct nonzero polynomials that 'fit' the sequence, with maximum degree $$$k$$$."
This variant seems fair enough to them. "Time to test the puzzle then," they say. Andy, Natalie, and Dylan take turns in giving you random sequences, while you need to reply with the different polynomials that could fit those sequences. Here, "fitting" means that the polynomial will evaluate to zero for all of the integers in the given sequence.
The first line of input starts with an integer $$$t$$$, the number of sequences.
$$$t$$$ sequences follow, described in two lines each.
The first line for each sequence consists of three integers $$$n$$$, $$$k$$$, and $$$\ell$$$, each separated by a space. $$$n$$$ and $$$k$$$ are as described previously, while $$$\ell$$$ denotes the length of the sequence.
The second line for each sequence contains the $$$\ell$$$ integers $$$s_1, s_2, \ldots, s_\ell$$$ that make up the sequence, separated by single spaces.
Constraints
For each of the $$$t$$$ sequences, output the following:
If less than $$$n$$$ such polynomials exist, print how many there are on its own line, followed by those polynomials. If there are at least $$$n$$$, print $$$n$$$ on its own line, followed by any $$$n$$$ polynomials.
Output each polynomial on each own line. First output its degree $$$d$$$, followed by exactly $$$d+1$$$ space-separated integer coefficients in decreasing order of exponents. The leading coefficient must not be zero.
The absolute value of the coefficients must also be less than or equal to $$$10^9$$$.
Important: For this problem, we treat the integers as congruent modulo $$$999983$$$. In other words, two integers $$$x$$$ and $$$y$$$ are considered equal if $$$999983$$$ divides $$$x - y$$$. (This implies that two polynomials $$$p$$$ and $$$q$$$ are considered equal if every coefficient of $$$p - q$$$ is divisible by $$$999983$$$. For example, $$$x - 1$$$ is considered the same as $$$999984x + 999982$$$, etc.)
There may be multiple valid answers. Any valid answer will be accepted.
3 1 5 4 1 2 3 5 1 3 4 1 2 3 5 1 4 3 3 7 42
1 5 1 -19 129 -389 518 -240 0 1 4 1 -52 441 -882 0
Note that 5 1 999964 129 -389 518 999743 is also a valid output for the first test case and is equivalent to the sample output above. (For example, evaluating it at $$$1$$$ will give $$$1999966$$$ which is equivalent to $$$0$$$ since $$$1999966 - 0$$$ is divisible by $$$999983$$$, so $$$1$$$ is a root.)
So you, as well as every member of the Penguin Secret Agency (PSA), have successfully sunk the evil genius's secret iceberg base by dancing on it until it flipped. He's pretty mad about that and went back to his igloo as a result. However, intelligence reports say that he has a special ice farm to create a second Iceberg Base.
You move to his ice farm and realize that you don't have anything to melt the ice with. You did however, bring your Puffle. After giving it a berry, it bursts into flames, ready to melt the ice for you, turning it into water. There is a problem though: if the Puffle is forced to go into the water, it cannot melt any more ice blocks. Also, you must melt all the ice to prevent the second Iceberg Base. Lastly, you need to give your Puffle instructions on how to move. They aren't known for their puzzle solving skills, but their memory is excellent. Don't forget to pick up your Puffle after it's done. Good luck!
The area to solve is an $$$r\times c$$$ grid. We denote by $$$(i, j)$$$ the cell at the $$$i$$$th row (from the top) and the $$$j$$$th column (from the left). In particular, $$$(1, 1)$$$ is the top-left corner of the area.
Your starting position is cell $$$(i, j)$$$, and your ending position can be anywhere.
Determine if a path that goes through each cell exactly once is possible. You are considered to have already passed the starting cell at the beginning. If it is possible, give a sequence that will do so.
Output your instructions as a sequence of directions: up, down, left, or right.
Should it be impossible, say so as well.
The first line of input contains $$$t$$$, the number of test cases.
Each test case consists of a single line containing four space-separated integers $$$r, c, i, j$$$.
Constraints
For each test case, output a single line containing a single string which is either:
2 2 3 1 1 3 3 1 2
DRRUL IMPOSSIBLE