You are using your favourite program, the BAPC ArchLinux Package Configurator, to upgrade your system. There are $$$n$$$ outdated packages that will be upgraded, and your package manager is kind enough to inform you of the download size for each package up front. Due to recent advances in parallelism, it downloads up to $$$k$$$ packages in parallel, although you do not know the order in which they are downloaded.
You are now looking at the download progress bar in the console, and observe that only $$$m$$$ packages have currently finished downloading but the overall download progress is already very high. This does not seem to make sense! You wonder: what is the maximum overall percentage of the total download size that could be done with this many package downloads completed? Note that there is a small duration of time in which a package that is being downloaded is reported as $$$100\%$$$ done, but not yet finished.
The input consists of:
- One line with three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1\leq n\leq 10^5$$$, $$$0\leq m\leq n$$$, $$$1\leq k\leq 10$$$), the number of packages being upgraded, the number of packages that finished downloading, and the number of packages that can be downloaded in parallel.
- One line with $$$n$$$ integers $$$s$$$ ($$$1\leq s\leq 10^9$$$), the sizes of the packages being upgraded.
Output the maximum possible percentage of the download that is done.
Your answer should have an absolute error of at most $$$10^{-4}$$$.
5 1 2 10 25 30 15 20
75.00000000000000000000
5 0 4 4 2 7 1 3
94.11764705882352941013
You are participating in the Battle-bots Aggressive Power Contest. It is a tournament where each team builds a robot that can battle with other robots, and you win by destroying your opponent's robot. Specifically, you win when your opponent's robot stops moving after its only motor is destroyed.
You have outfitted your bot with two weapons: it has a sword that can slash the opponent's bot in half, and it has a claw that can take a chunk out of your opponent's bot and crush it into scrap. The attacks take equally long. The program that controls your bot is always running to decide which attack to use next.
If your battle-bot uses the sword attack to cut its opponent in half, the half with the motor will keep moving, and you can ignore the other half. If your battle-bot uses the claw attack, it will take a chunk of size $$$1$$$ out of the opponent's bot, but unless you can take the bot out entirely you have to assume that the motor of the bot is in the piece you have not clawed, and keep fighting.
For example, consider the second sample case. If your opponent's bot is so big it would take $$$5$$$ claw attacks to completely crush it, you could act as follows. Start with a sword slash, cutting it down into two pieces of size $$$2\frac12$$$. Then use your claw on the part that is still moving, so it goes down to size $$$1\frac12$$$. Cut that piece in half with your sword again to bring it down to size $$$\frac34$$$. Then finally use your claw to crush the last moving piece of the bot. That way, you can beat it in four attacks.
Your bot is equipped with a quantum computer that can easily simulate a googol attack patterns per microsecond. However, if it does not know what the fastest attack pattern is, it will never know it has reached that, and never stop searching.
Finish your battle bot by writing a program that, given how many claw attacks it would take to take out the opponent, determines the minimal number of attacks you need in the worst case to take it out.
The input consists of:
- One line with an integer $$$n$$$ ($$$1\leq n\leq 10^{18}$$$), the number of claw attacks it would take to take out your opponent's bot.
Output the least number of attacks needed to destroy your opponent's bot.
5
4
6
4
3
3
Unlike your friends, you live in a terminal. You are cool. Your terminal is everything to you: you have optimized the font, colour scheme, keyboard shortcuts, and what not.
Once thing still annoys you though: all these commands you're typing involve so many file paths and are so long! Then it occurs to you: all this time you have been working from the root directory of the file system, but in fact you can change directory to anywhere you like! This should simplify your life a lot!
This way, if your working directory is /a/b, you can refer to the absolute file path /a/b/x using simply x. To go up a level, you can use .., so that you can refer to /a/y/z as ../y/z, and to /some/other/directory as ../../some/other/directory.
You being you, of course you overdo this and will now use relative paths everywhere!
Given the $$$n$$$ absolute file paths in the command you want to run, find the working directory that minimizes the total number of relative path components. For example, a/a/b/c, and ../../a/b both contain $$$4$$$ path components. Note that you can only change the working directory to a directory and not to a file path. Filenames will never coincide with directory names in the same directory.
In the first sample it is best to set the working directory to /home/jury/compressingcommands, leading to $$$6$$$ components: secret, solutions, and ../../hackerman/answers.
In the second sample it is best to set the working directory to /a, leading to $$$19$$$ path components: b/a/a/b, a/a, ../b, a/b, b/a/a/a, ../c, and b/a/b.
The input consists of:
- One line with an integer $$$n$$$ ($$$1\leq n\leq 10^5$$$), the number of absolute file paths.
- $$$n$$$ lines, each with a string $$$s$$$, an absolute file path. Each path contains only lowercase English letters (a-z) and slashes ('/'), starts with '/', does not end with '/', and does not contain consecutive slashes ("//").
Output the minimal number of relative path components that can be achieved by changing to a different working directory.
3 /home/jury/compressingcommands/secret /home/jury/compressingcommands/solutions /home/hackerman/answers
6
7 /a/b/a/a/b /a/a/a /b /a/a/b /a/b/a/a/a /c /a/b/a/b
19
3 /x/y/z /x/y/z /x/y/z
3
A new county has been created on artificially created land out from the coast, with code name "Built Anew Peninsula County", but the final name still needs to be chosen. To establish a new name, the cities within the county get to vote on the individual letters of the name.
As it happens, all cities in the county have a name with exactly $$$m$$$ letters, and so they decide the name of the county will also have exactly $$$m$$$ letters. Naturally, each city prefers their own name, and thus votes that the $$$i$$$th letter of the county name should match theirs. For each of the $$$m$$$ positions, the letter that received the most votes across all cities gets picked. In case of a tie between multiple letters, the one occurring earliest in the English alphabet gets picked.
Given the list of the city names, determine the result of the vote for the new county's name.
The input consists of:
- One line with two integers $$$n$$$ and $$$m$$$ ($$$1\leq n\leq 1000$$$, $$$1 \leq m \leq 1000$$$), the number of cities and the number of letters in each city name.
- $$$n$$$ lines, each with a string of length $$$m$$$, the name of a city.
Output the name of the new county.
3 5 apple maple alpha
aaple
3 4 icpc back laps
bapc
You have a lot of exams today! And you have not yet prepared for any of them! At least you know from experience that if you study enough for an exam, you will for sure pass it quickly, well within the allotted time. Even better, you stared so long at the daunting course curricula that you now know exactly how much time you will need to study for each exam in order to pass it within the given time. If you do not study long enough, you will for sure fail it.
As it happens, your university has some weird bureaucratic rules that require you to attend all your exams. The horror! And leaving early is not allowed, unless you know for sure you passed it!
Given the full exam schedule of when each exam starts, how long each exam takes, how much time you need to study for each exam, and how quickly you can finish each exam you studied for, how many exams can you pass at most?
You may start studying at time $$$0$$$, but can only study while not making an exam. The preparation for an exam does not have to be done in a contiguous block of time and may be interrupted.
The input consists of:
- One line with an integer $$$n$$$ ($$$1 \le n \le 2000$$$), the number of exams you have to attend.
- $$$n$$$ lines, the $$$i$$$th of which contains four integers describing an exam:
- $$$s_i$$$ ($$$0 \le s_i$$$), the start time of the $$$i$$$th exam,
- $$$p_i$$$ ($$$s_i \lt p_i$$$), the end time of the $$$i$$$th exam if you prepare for it,
- $$$e_i$$$ ($$$p_i \le e_i \le 10^9$$$), the end time of the $$$i$$$th exam if you do not prepare for it,
- $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$), the time needed to prepare the $$$i$$$th exam.
Output the maximum number of exams you can pass.
3 10 20 30 5 30 50 100 15 100 101 200 50
3
3 1000 1001 1002 1000 1003 1004 1005 500 1006 1007 1008 500
2
You are on a skiing trip in the Alps and need to take a funicular.
However, there usually is a long queue for the funicular to bring you to the top of the mountain. Being someone who hates wasting time in the morning, you want to find the best moment to start queueing in order to minimize queueing time.
The funicular station is open for $$$n$$$ minutes per day. A carriage transports $$$c$$$ people at once, and one carriage leaves exactly every minute. For every minute the funicular is open today, you know the number of people arriving.
You want to arrive when the station is open, exactly at the start of a minute, like everyone else. Note that you are a sociable person and if there are other people arriving at the same minute as you, you let them go first, after which you stand in the queue.
Calculate at which minute you should arrive to have minimal waiting time, or determine that it is impossible to catch a ride today. If there are two times achieving the same minimal waiting time, give the earliest occasion.
The input consists of:
- One line with two integers $$$n$$$ and $$$c$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq c \leq 10^9$$$), the number of minutes the funicular is open today and the number of people one funicular carriage takes up the mountain each minute.
- One line with $$$n$$$ integers $$$a_0, \dots, a_{n-1}$$$ ($$$0 \leq a_i \leq 10^9$$$), the number of new people showing up $$$i$$$ minutes after the funicular opens.
If it is not possible to take the funicular today, output "impossible". Else, output the least number of minutes after opening time you should enter the queue, such that the waiting time is minimized.
5 1 5 0 0 0 0
impossible
5 4 8 6 4 2 0
0
10 10 12 11 10 9 8 7 6 5 4 3
5
A funicular is a type of cable railway system laid on a steep slope, where two counterbalanced carriages are attached to opposite ends of a haulage cable, which is looped over a pulley at the upper end of the track.
For the longest time you could keep your toddlers happy by letting them play with triangular, square, and circular wooden blocks that fit exactly through perfectly sized holes. After letting them play a bit too long, they completely mastered this game and are now bored, preventing you from fixing the bugs in your code.
Just now, they decided to reverse roles and started screaming planar coordinates at you, insisting that you determine which shape each four points make: kite, trapezium, parallelogram, rhombus, rectangle, square, or none of those. You do not have time for this, since your bugs still need fixing. Instead, you write a new program to answer your toddlers' questions, ideally without bugs.
The definitions for the quadrilateral shapes are as follows:
- A square has four right angles and four sides with equal lengths.
- A rectangle has four right angles.
- A rhombus has four sides with equal lengths.
- A parallelogram has two pairs of parallel sides.
- A trapezium has one pair of parallel sides.
- A kite has reflection symmetry across a diagonal.
The input consists of:
- Four lines, each containing two integers $$$x$$$ and $$$y$$$ ($$$0\leq x,y\leq 10^9$$$), the coordinates of a point.
The four points are distinct, form a convex quadrilateral shape (i.e. all interior angles are strictly less than $$$180^\circ$$$), and are given in clockwise order.
Output the most restrictive type of quadrilateral that the points form, which is the first one of "square", "rectangle", "rhombus", "parallelogram", "trapezium", or "kite" that applies, or "none" otherwise.
0 0 0 1 1 1 1 0
square
1 1 2 3 4 5 3 3
parallelogram
You have recently moved to a new home, and you are almost done decorating it. However, you still feel like something is missing: you need some art on the wall! Since you have already spent most of your budget on the furniture, you decide to go to the cheapest art shop there is: the Budget Art Printing Company (BAPC).
At the BAPC, you can buy infinitely large sheets of paper on which a decoration is printed. Such a decoration consists of a rectangular pattern which is repeated in all directions. This pattern in turn consists of square pixels that are colored white, red, green or blue. After buying a sheet of paper, customers may then cut out a part of the sheet to create their very own artwork.
You have just found a pattern of pixels you like, but before you have it printed you decide to check whether it is possible to cut a beautiful artwork from it. You consider an artwork beautiful if it satisfies the following properties:
- It is cut out along pixel boundaries.
- It is a square.
- The pixels in the four corners of the square have four different colors.
As an example, consider the first sample input, visualized in the figure below. In the infinitely repeated pattern, it is possible to find several beautiful artworks.
Visualization of the first sample input. The pattern is shown repeated five times in the horizontal direction and two times in the vertical direction, but remember that it repeats indefinitely in all directions. The three bold outlined squares indicate some possible beautiful artworks. The input consists of:
- One line with two integers $$$h$$$ and $$$w$$$ ($$$1 \leq h \leq 4000$$$, $$$1 \leq w \leq 50$$$), the height and width of the chosen pattern.
- $$$h$$$ lines, each with a string of $$$w$$$ characters $$$c$$$ ($$$c \in \{\texttt{w}, \texttt{r}, \texttt{g}, \texttt{b}\}$$$), describing the pattern.
If it is possible to cut out a beautiful artwork from the sheet with the selected pattern, output "possible", otherwise output "impossible".
3 2 wr wg bg
possible
2 4 gbrw wbgr
impossible
6 6 bwwrrr bbbrrr bbbrwr rrrggg rrrgww rwwggg
possible
Long, long ago on a planet far, far away, a highly contagious virus caused an enduring pandemic.
Even so, the people wanted to travel between countries for their summer holidays. In the good old before-days, travelling from any country to any other country took 1 full day. However, during the pandemic, certain countries preferred not to receive travellers from areas that had higher infection rates, so they made them quarantine for a certain number of days before allowing them to continue their trip or start their holiday.
To keep everything fair, an independent Bureau for Accurate Pandemic Classification was founded. They assigned a $$$r$$$-value to each country based on the infection rate in that country. A higher $$$r$$$-value indicates higher infection rate.
Each country asked tourists to quarantine if the country they just came from had a $$$r$$$-value significantly higher than their own. In particular, when you wanted to travel from country $$$i$$$ to country $$$j$$$, you would have to quarantine for $$$t_j$$$ days if $$$r_i \gt r_j + m$$$.
Archaeologists have found evidence of $$$q$$$ tourists travelling between $$$n$$$ countries. For each tourist, the start and destination are known. The question that remains to be answered is: how long was each tourist's minimal travel time?
The input consists of:
- One line with three integers $$$n$$$, $$$q$$$, and $$$m$$$ ($$$2\leq n \leq 10^5$$$, $$$1\leq q \leq 10^5$$$, $$$0\leq m \leq 10^9$$$), the number of countries, the number of tourists, and the maximum allowed difference between two $$$r$$$-values when travelling to a country with a lower infection rate.
- One line with $$$n$$$ integers $$$r_1, \dots, r_n$$$ ($$$0 \leq r_1 \leq \dots \leq r_n \leq 10^9$$$), the $$$r$$$-value for each country.
- One line with $$$n$$$ integers $$$t_1, \dots, t_n$$$ ($$$0 \leq t_i \leq 10^9$$$ for all $$$i$$$), the required quarantine time in days when travelling to a country with a significantly lower $$$r$$$-value.
- $$$q$$$ lines, each with two integers $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq n$$$, $$$x \neq y$$$), indicating a tourist departing from country $$$x$$$ with final destination $$$y$$$.
For each tourist, output their minimal travel time in days between their departure country and destination country, in the order in which they appear in the input.
5 4 1 0 5 6 7 8 3 4 1 5 10 1 4 4 1 4 2 5 2
1 4 2 3
5 4 10 0 8 20 25 30 5 11 13 6 3 5 1 5 2 5 3 5 4
6 7 1 1
Your local jungle is being taken over by monkeys! Trees are quickly being colonized by them! As a Brave Ape Pictures Collector, this is your chance of taking sooo many pictures of primates that for sure will amaze your colleagues.
In particular, each day, one new monkey discovers your favourite tree containing $$$n$$$ branches. From your long experience observing primates, you know two things. First, each branch of the tree only has room for a single monkey. Second, monkeys are very social animals and always stick together in groups, that is, the branches they occupy form a single connected component.
This particular invasive species of monkeys happens to be new to you and you have not yet learned to distinguish them from each other. Still you wonder: how many different pictures of the monkey colony could you take on each day, until the tree is full of monkeys?
As an example, consider the first sample case, visualized in the figure below. On the third day, there are four different pictures you can take of the monkey colony.
Visualization of the first sample case on the third day. Branches are connected if they overlap (note the small gap between branches $$$1$$$ and $$$2$$$, and between branches $$$3$$$ and $$$4$$$). Monkey image from freevector.com
Given the exact structure of your favourite tree, determine for each day from $$$1$$$ to $$$n$$$ the number of different sets of branches the monkeys could occupy on that day, modulo $$$10^9+7$$$.
The input consists of:
- One line with an integer $$$n$$$ ($$$1\leq n\leq 1000$$$), the number of branches in the tree.
- $$$n-1$$$ lines, the $$$i$$$th of which ($$$1\leq i\leq n-1$$$) contains an integer $$$p_i$$$ ($$$0\leq p_i \lt i$$$), indicating that branch $$$i$$$ is connected to the upper end of branch $$$p_i$$$.
Output $$$n$$$ integers. The $$$k$$$th integer should be the number of connected subtrees that consist of exactly $$$k$$$ branches, modulo $$$10^9+7$$$.
5 0 0 1 1
5 4 4 3 1
3 0 1
3 2 1
The king of Belle Aire People's Country has come up with a new plan: he has heard about the popular phenomenon called "King of the Hill", and he would like to become one as well. To do so, he has ordered you to raise a flag on the highest hill in his square kingdom, which has dimensions $$$n \times n$$$. You are given a very expensive (it is gold- and jewel-embedded) satellite-based height-measuring system. This equipment is highly accurate: the heights on every location in the kingdom are represented with distinct integers. However, to cut costs, you are only allowed to take $$$10n+100$$$ measurements before reporting back to the king.
Furthermore, you know for certain that there is only a single point that is the absolute highest: this is the only point for which its height is larger than the (up to) four orthogonally adjacent points that lie inside the kingdom. In other words, there are no local maxima besides the global maximum.
This is an interactive problem. Your submission will be run against an interactor, which reads from the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol:
The interactor first sends one line with an integer $$$n$$$ ($$$1\leq n\leq 10\,000$$$), the width and height of the kingdom.
Then, your program should make at most $$$10n+100$$$ queries to find the highest point in the kingdom. Each query is made by printing one line of the form "? $$$x$$$ $$$y$$$" ($$$1\leq x,y\leq n$$$). The interactor will respond with an integer $$$v$$$ ($$$1 \leq v \leq 10^9$$$), indicating the height at coordinate $$$(x, y)$$$.
When you have determined the height of the highest point in the kingdom $$$v$$$, print one line of the form "! $$$v$$$", after which the interaction will stop. Printing the answer does not count as a query.
The interactor is not adaptive: the heights in the kingdom are fixed up front, and do not depend on your queries.
Make sure you flush the buffer after each write.
A testing tool is provided to help you develop your solution.
Using more than $$$10n+100$$$ queries will result in a wrong answer.
3 3 9 4 8 7
? 2 1 ? 2 2 ? 2 3 ? 3 2 ? 1 2 ! 9
4 600000000 864213579 864297531 987654321 123456789 975318642
? 3 3 ? 2 3 ? 2 2 ? 1 2 ? 1 1 ? 1 3 ! 987654321
You just started a new job at a shopping mall, and as it goes, you got the shittiest task of all: closing down at night. The mall consists of many rooms (which can be shops, hallways, or other public spaces) with open doors between them that must be closed. You can walk through a door both ways if it is open, but annoyingly, each door can only be locked from one of the two rooms it connects.
Your supervisor already locked the main entrance of the shopping mall, and left you inside with the task to lock all the doors. In order to do so, you may request additional exits to be installed in some of the rooms. If a room has an exit, then you are able to enter or leave the shopping mall through that room.
What is the minimal number of exits you need to request in order for it to be possible to lock all the doors and then leave the building?
The input consists of:
- One line with two integers $$$n$$$ and $$$m$$$ ($$$2\leq n \leq 10^5$$$, $$$1\leq m \leq 10^6$$$), the number of rooms and doors, respectively.
- Then follow $$$m$$$ lines, each containing two distinct integers $$$a$$$ and $$$b$$$ ($$$1 \leq a,b \leq n$$$, $$$a \neq b$$$), indicating a door connecting rooms $$$a$$$ and $$$b$$$ which can only be locked from room $$$a$$$.
Output the minimal number of exits that need to be installed.
2 1 1 2
1
3 2 2 1 3 1
2
5 4 1 2 3 1 4 1 5 1
3
10 14 1 2 2 1 3 4 3 5 4 6 5 6 6 3 7 8 8 9 9 7 1 8 2 10 4 9 5 10
2