Dr. Doof is lonely during the winter months, and is sad that his daughter, Vanessa, has not visited him for the holidays. Although a poor replacement, he decides that he wants to build a robot snowman. The structure of a robot snowman consists of a lower body, torso, and head. Each of these components is a solid metal cube with side lengths in ratio $$$5:3:1$$$. To feel more loved, the good doctor wants to make the largest "snowman" possible to give himself company (while still maintaining the ratio of dimensions). You can help him design this glorious creation by simply knowing the total amount of scrap metal available in cubic meters (Doof uses the metric system, and so should you).
A single positive integer $$$S$$$ ($$$1 \leq S \leq 10^9$$$) representing the total amount of scrap metal in cubic meters that Dr. Doof has for personal use.
A single positive number representing the side length in meters of the "head" of the robot snowman that Dr. Doof desires. Any answer within $$$10^{-3}$$$ of the judge solution will be accepted.
153
1.0000000000
216
1.1218137878
Alice and Bob have become intelligent robots! They have acquired a ball and want to toss it back and forth to each other. However, the sneaky Eve wants to steal their ball.
Alice and Bob are at $$$(x_a, y_a)$$$ and $$$(x_b, y_b)$$$ on the coordinate plane, respectively, where both their locations are lattice points (the coordinates are integers). Eve is also located at a lattice point, and if the path of the ball crosses directly overhead of Eve, she is able to jump up and steal the ball. However, if Eve is not directly on the path, she will not be able to intercept the ball.
Given multiple possible locations of Eve, determine if Alice and Bob's game of toss would be interrupted.
The first line of the input contains $$$x_a$$$ and $$$y_a$$$, Alice's location.
The next line of the input contains $$$x_b$$$ and $$$y_b$$$, Bob's location.
The next line contains $$$E$$$ $$$(1 \le E \le 100)$$$, the number of different possible locations of Eve.
The next $$$E$$$ lines each contain $$$x, y$$$, a possible location of Eve.
We know that $$$-10^4 \le x_a, x_b, x, y_a, y_b, y \le 10^4$$$.
Output $$$E$$$ lines, where each line is a simple Yes or No, corresponding to if Eve can intercept Alice and Bob's ball.
0 0 2 2 2 1 1 -1 -1
Yes No
A new AI bot has taken over much of the world's most important computer infrastructures and threatens to reshape life for humans as we know it. You have been chosen as Earth's last hope to go through a series of logic and math puzzles which the AI has set in order to get to the control room and deactivate the bot.
You've reached the final puzzle and you find $$$5$$$ doors in front of you (labeled $$$0$$$, $$$1$$$, $$$2$$$, $$$3$$$, and $$$4$$$ because computers love $$$0$$$-indexing). The AI bot, confident that you won't be able to find the door leading to the control room, gives you a large integer $$$n$$$ and the following equation: $$$$$$1^n + 2^n + 3^n + 4^n \pmod{5}$$$$$$
If you can evaluate this expression for the given value of $$$n$$$, that will be the door the control room is behind. Calculate or choose wrong and you will be locked out of the building for good with no chance to stop the bot. Given $$$n$$$, choose the door that will save humanity.
The only line of input contains a single integer $$$n$$$ where $$$0 \leq n \leq 10^{10^{5}}$$$.
Output a single line representing the door that you should choose.
4
4
18417128371888291122782652113433
0
In the first sample, $$$1^4 + 2^4 + 3^4 + 4^4 = 1 + 16 + 81 + 256 = 354$$$ so $$$354 \pmod{5} = 4$$$.
The AI Jeff has been created to help manage the packaging of Skittles! In fact, he was designed to be so intelligent that the overall management of deciding the packaging of skittles has become under his control.
Jeff's first task is given the $$$n$$$ skittles that are currently available, split them up into two batches, with the first batch containing $$$k$$$ skittles, and the second containing $$$n - k$$$ skittles. The first batch of skittles will be packaged and shipped out in a week, while the remaining skittles will be packaged in a month or so.
Jeff decides that he wants to rework the skittles packaging system in a way to optimize something. The only rules here are that no skittle can be wasted, and every package must have the same number of skittles. Since it is well known that every skittles bag must have the same number of skittles $$$s$$$, he decides given $$$k$$$ and $$$n - k$$$, $$$s$$$ will be the largest possible number of skittles such that $$$s$$$ divides both $$$k$$$ and $$$n - k$$$.
Jeff wants to find the optimal $$$k$$$ to maximize his skittle bag size. Unfortunately, Jeff has been stumped. Please help him determine the optimal batch size such that the packages will have the most skittles!
The first and only line of input will contain $$$n (2 \le n \le 10^9)$$$, the number of skittles Jeff has.
Output two space separated integers the batch sizes of skittles. If there are multiple ways to maximize the number of skittles in a package, output the answer that would be lexicographically the smallest (minimize the size of the first batch).
15
5 10
Every year, hundreds of skiers compete in an annual World Cup alpine ski race called the Hahnenkammrennen. Over the course of a weekend, skiers conquer several demanding slopes down the Hahnenkamm mountain and race to achieve the fastest times.
This year, to keep things "interesting" of course, the ski slopes have been scattered with various obstacles to block skiers' paths, such that they must dodge these hazards or surely get knocked out of the competition. To compensate for possible time delays caused by the hazards, ramps have also been added to the course, enabling skiers to launch into the air and sail over obstacles, traveling quickly without being slowed by the friction of snow.
This is also the first year that robots will be allowed to compete in the Hahnenkammrennen. You are determined to capitalize on this opportunity and win the World Cup with the first ever bot competitor: the Ski-Bot 3000. The hardware components for Ski-Bot have already been assembled, but now it must be able to navigate the fastest possible path down each slope that it faces.
Write a program for the Ski-Bot 3000 that, given an overhead map of a ski slope course from the Hahnenkammrennen, computes the length of the shortest path from the top to the bottom of the course. And hurry—the first race starts today!
The first line of input contains two integers, $$$N$$$ and $$$M$$$ ($$$1 \leq N,M \leq 1000$$$), denoting the number of rows and columns in the rectangular ski slope map respectively.
$$$N$$$ lines follow, each containing $$$M$$$ characters denoting grid cells on the ski slope map. A # character denotes an obstacle cell that cannot be skied across. A . denotes clear snow that can readily be traversed. Lastly, a > denotes a wooden ramp that will launch a skier upwards, such that they land on the next clear cell ahead of them down the slope.
The leftmost column of the grid represents the top of the slope, and the rightmost column represents the base. Skiers can choose to start in any clear cell at the top of the slope and likewise cross the course finish-line in any clear cell at the base.
Movement-wise, a skier can only ever ski downhill, or right-ward on the map. This means that if a skier is located on a clear cell in row $$$r$$$ and column $$$c$$$ on the slope map, their only next options are to ski into cells $$$(r+1, c+1)$$$, $$$(r, c+1)$$$, or $$$(r-1, c+1)$$$. Of course, if a skier reaches a ramp cell, their next move is to get launched into the air and land on the first clear cell down-slope from their current position. Note that each ramp cell is guaranteed to have a clear landing spot downhill on the course.
Print the length of the shortest path from top to bottom of the ski slope (left to right on the map). Note that each movement from cell to cell counts as a single path step, including a ramp jump which counts as only one step, regardless of how many obstacle cells or ramps a skier jumps over before she lands. You are guaranteed that a path down the slope is always possible.
3 14 ..##..##.>##.. ......#.##.#.. .#...#....#...
11
5 15 .#..##.>#####.. .###.....#.>##. ....##.>#.###.. ##.>##>#...###. .##>#.>#.##....
8
The robot overlord has a bit of a dilemma on his hands. The army has constructed a huge factory stocked with worker robots in order to make the next generation army. There are $$$n$$$ types of robots that the army is trying to build, each type having a unique ID which is an integer between $$$1$$$ and $$$n$$$ (inclusive of $$$1$$$ and $$$n$$$).
Now, to meet the army's goal of world domination, they must construct $$$k$$$ robots every day (the type of each robot doesn't matter, just need $$$k$$$ total every day). However, his current batch of workers tends to be a little temperamental. They have threatened to go on strike unless their demands for the new robots were met. The overlord would usually just incinerate the obstinate robots and use the scrap parts to create a new workforce but due to the time crunch, the overlord decides to humor the workers.
The worker's demand is simple enough: they want each of the $$$k$$$ robots made that day to follow the rule that if the $$$i$$$th robot made is of type $$$a$$$ ($$$1 \leq a \leq n$$$) then the $$$i + 1$$$th robot made must be of type $$$b$$$ where $$$a \mid b$$$. This must hold for all $$$i$$$ where $$$1 \leq i \leq k - 1$$$ which means that if the sequence of robots made is $$$r_1, r_2, \dots, r_n$$$ then $$$r_i \mid r_{i+1}$$$ for all $$$i$$$ ($$$1 \leq i \leq n - 1$$$).
Given $$$n$$$ and $$$k$$$, help the overlord find out the number of distinct robot sequences that satisfy the above demand that can be made. Since this number can be quite large, the overlord will suffice with the number modulo $$$1000000007$$$ $$$(10^9 + 7)$$$.
The only line of input will contain two space-separated integers $$$n$$$ and $$$k$$$ where $$$1 \leq n, k \leq 2000$$$.
Output a single integer representing the number of distinct robot sequences that satisfy the workers' demand modulo $$$1000000007$$$ $$$(10^9 + 7)$$$.
4 2
8
6 5
56
In the first sample, the sequences are $$$[1, 1], [2, 2], [3,3], [4,4], [1,2], [1, 3], [1,4], [2,4]$$$.
While most robots are known for their incredible logic and computational abilities, Artbot wants something more: to be excellent at softer skills as making art. Unfortunately, Artbot isn't very creative and only knows how to create art in one particular way.
Artbot's canvas is a labeled tree with $$$n$$$ vertices and Artbot always starts painting from the vertex with label $$$1$$$. Once Artbot leaves a vertex, Artbot will never visit that vertex again. After painting the initial vertex, Artbot travels across $$$d$$$ edges (choosing which edge to travel uniformly at random from all the edges that lead to unvisited vertices at each step) and paints the resulting vertex that it lands on. Artbot continues this process until Artbot cannot take an edge to an unvisited vertex, at which point its masterpiece is complete. Note that if Artbot is not able to travel across all $$$d$$$ edges, it will not paint the resulting vertex that it lands on.
However, as a robot, Artbot needs a concrete metric to use to evaluate its created art. Artbot cares about how many vertices of its canvas end up painted after Artbot finishes the process described above. Given a labelled tree, figure out the expected number of painted vertices after Artbot goes through the described procedure.
The first line will consist of two integers $$$n$$$ and $$$d$$$ ($$$1 \leq d \leq n \leq 10^5$$$), which give the number of vertices in the labeled tree and the number of edges Artbot travels across between painting vertices. The next $$$n - 1$$$ lines consist of two integers $$$u_i, v_i$$$ ($$$1 \leq u_i, v_i \leq n, u_i \neq v_i$$$) indicating that there is an edge between vertex $$$u_i$$$ and vertex $$$v_i$$$.
The expected number of vertices painted after Artbot goes through the described procedure can be expressed as a simplified, reduced rational $$$\frac{p}{q}$$$. Output $$$pq^{-1} \pmod {10^9 + 7}$$$.
5 1 1 2 2 3 3 4 4 5
5
6 2 1 2 1 3 1 4 1 5 5 6
250000003
For the first sample, all vertices of the tree will be painted. For the second sample, the root will be painted and vertex $$$6$$$ will be painted with probability $$$\frac{1}{4}$$$, which gives us the answer $$$\frac{5}{4}$$$. $$$5(4^{-1}) \pmod {10^9 + 7}$$$ gives us the sample answer.
EvilCorp has recently seen a sudden increase in sales and business has been booming (their status as rulers of the free world certainly helps). The company has been rapidly expanding and is hiring new people nearly every day. In order to boost company morale, the unnamed CEO has decided to pay out bonuses to employees (some of which are self-aware AI demanding rights) belonging to certain departments based on their performance.
EvilCorp is structured as follows:
- Each employee has exactly one direct supervisor (except for the CEO, who has no supervisor).
- An employee can have zero or more direct subordinates, and each employee heads their own department.
- Every employee is a part of their own department and all of the departments that their supervisor is a part of (e.g. the CEO is only a part of the department he heads, and all other employees are in his department).
When the CEO decides that a department is doing well, he pays out bonuses to all the employees that are a part of that department. Bonuses are calculated by multiplying the bonus amount $$$B$$$ with the employee's bonus multiplier $$$M$$$. All employees begin work with a bonus multiplier of $$$S$$$, but depending on performance, an employee's bonus multiplier can change (potentially affecting the amount of money that employee gets for future bonuses).
Although this rapid expansion has been great news for EvilCorp, the (puny human) CEO is struggling to handle the sudden increase in staff size. He needs you to create a program which can help keep track of the amount of money paid out to employees in bonuses!
Given different queries, keep track of the amount of money paid to the different employees in bonuses. Queries will be one of four types:
- Hire a new employee and assign their supervisor.
- Update an employee's bonus multiplier.
- Pay out bonuses to all employees in the department headed by a given employee.
- Output the total amount of money paid to a given employee.
Employees are numbered starting at 1 (the CEO) and all new employees are given the next integer employee identification (ID) number in the order they were hired into the pizzeria. The company initially has the CEO as the sole employee.
The input will begin with a line containing two integers, $$$N$$$ ($$$1 \leq N \leq 10^5$$$) and $$$S$$$ ($$$0 \leq S \leq 10^6$$$) representing the number of queries and the starting bonus multiplier for all new employees (including Louie). The next $$$N$$$ lines describe the queries using one of the following four formats:
- "1 $$$i$$$" meaning that a new employee is hired and has the supervisor with employee ID $$$i$$$.
- "2 $$$i$$$ $$$M$$$" meaning that the bonus multiplier of the employee with the ID $$$i$$$ is now equal to $$$M$$$ ($$$0 \leq M \leq 10^6$$$).
- "3 $$$i$$$ $$$B$$$" meaning that a bonus with the base amount, $$$B$$$ ($$$0 \leq B \leq 10^6$$$), is paid out to all employees in the department headed by $$$i$$$.
- "4 $$$i$$$" representing a query asking for the amount of money paid in bonuses so far to the employee with the ID $$$i$$$.
For each query of the fourth kind, print out a single integer representing the amount of money paid in bonuses to the specific employee so far.
7 1 3 1 10 4 1 2 1 2 1 1 3 1 5 4 1 4 2
10 20 5
13 10 1 1 1 1 2 2 20 3 1 5 4 1 4 2 4 3 1 2 3 2 7 4 1 4 2 4 3 4 4
50 100 50 50 240 50 70