Sharing is caring, and Darcy_Liu loves to share. If he has $$$x$$$ slices of pizza to give away and split evenly among his $$$N$$$ friends, how many slices can he give to each, and how many will be left over?
One line consisting of 2 integers $$$x$$$ and $$$N$$$ $$$(1 \le x,N \le 10^9)$$$.
For each test case, output 1 line containing the number of slices each friend will get followed by the number of slices left over.
5 2
2 1
9 3
3 0
For the 2nd case, he has 9 slices and 3 friends. He can give 3 to each friend, splitting them evenly with none left over.
tldr: Darcy has 2 sets of 5 numbers each. He chooses one of the sets and adds up all the numbers in that set except one. What is the maximum sum of those 4 numbers?
Darcy has 10 classmates. 5 sit on the left side, while 5 sit on the right side. Each classmate has a certain amount of points. One day, Bruce invites Darcy to write on the blackboard. Facing attention from both the left and right side, he suddenly finds himself fighting a war on two fronts.
The situation may seem dire for Darcy, but luckily he has a secret ability: the blitzkrieg. In the blink of an eye, Darcy obliterates one classmate (using facts and logic), shocking the other 4 classmates on that side to surrender and give Darcy all their points. However, Darcy can only do this 1 time - as soon as he uses this ability, Bruce will banish him back to his seat for "being disruptive". How many points can Darcy win?
The first line contains 5 integers, with each integer $$$x$$$ being a number in the first set.
The second line contains 5 integers, with each integer $$$x$$$ being a number in the second set.
$$$1 \le x \le 100$$$
Output the maximum amount of points Darcy can obtain.
5 1 5 5 5 3 3 2 2 2
20
Darcy chooses every number in the first set except the number 1.
Darcy is celebrating his IOI platinum medal. At his party, he tried to split up his cake into many slices and distributed the slices equally. However, his supervisor Eric noticed that Darcy accidentally gave some people an incorrect amount of slices. Calculate how many times Darcy made a mistake.
The first line contains $$$N$$$, the number of people at the party. The next line contains $$$N$$$ integers, each integer $$$x_i$$$ representing the number of slices of cake the $$$i^\text{th}$$$ person has.
It is guaranteed that the total number of slices will be divisible by the number of people at the party.
$$$1 \le N, x_i \le 10$$$
Output the number of people who did not receive the number of slices they should have received if the cake was divided equally.
5 1 3 2 2 2
2
If the slices were evenly distributed, everyone would receive 2 slices. Darcy only gave 1 slice to person 1, and gave the extra slice to person 2.
Real problem statement:
Darcy is celebrating after winning the IOI platinum medal. At his party, Darcy made some cake and split it equally among the guests, giving everyone an equal amount. Everybody there either enjoyed it or didn't enjoy it (you can't do both). What they didn't know was that Darcy was secretly hired by Eric to spy on potential enemies. During the party, Darcy began to notice something strange: those who enjoyed cake were beginning to BUY cake from those who didn't! Such a display shall not fool Darcy, for he has taken economics and knows this is an unacceptable instance of the free market. Help Darcy find out how many people have participated in this illegal activity.
In Minerva, there are $$$N$$$ floating islands connected by $$$M$$$ bidirectional rainbow bridges. Each bridge has a different brightness and the length of each bridge is $$$1$$$. Throughout the lands, There are $$$Q$$$ animals that are trying to see the festival of light and darkness on island $$$1$$$. These animals can either be white or black. The animals all want to get to their destination while travelling the shortest distance. If there are many paths of the same distance, the white animals will try to maximize the total brightness of the bridges they cross, while the black animals will try to minimize it. Calculate the distance each animal will travel and the total brightness they will encounter on their journey.
Note: it will always be possible for each animal to reach island 1.
The first line contains $$$N$$$ and $$$M$$$.
The next $$$M$$$ lines are in the form $$$x$$$ $$$y$$$ $$$z$$$ representing a path between $$$x$$$ and $$$y$$$ with a brightness $$$z$$$.
The next line contains $$$Q$$$.
The next $$$Q$$$ lines contain $$$d_i$$$, the initial location of the $$$i$$$th animal, followed by either 'White' or 'Black', representing their color.
##Constraints
$$$1 \le x,y,d_i \le N \le 5 \times 10^5$$$
$$$1 \le z \le 256$$$
$$$N-1 \le M \le 10^6$$$
$$$1 \le Q \le 10^5$$$
For each of the $$$Q$$$ animals, output the length and brightness of their best path.
5 7 4 1 7 5 2 1 5 3 9 5 4 5 1 5 1 3 1 8 3 4 6 5 2 Black 5 Black 3 Black 3 White 1 White
2 2 1 1 1 8 1 8 0 0
At coding club, Darcy is watching the bouncing screensaver meme. The screensaver consists of a rectangular DVD logo of width $$$A$$$ and height $$$B$$$ bouncing around a rectangular screen of width $$$W$$$ and height $$$H$$$ at a speed of $$$1$$$ unit/second. When the logo touches a side of the screen, it bounces off such that the angle of incidence equals the angle of reflection. When the logo reaches a corner, its direction is simply reversed.
The logo begins at position $$$(x_0,y_0)$$$ (measured from the bottom left corner of the screen and logo) and travels in the direction $$$(x,y)$$$. After a while, Darcy noticed that the logo returned to its starting position and velocity. What is the minimum time Darcy had to wait?
The first line contains integers $$$W$$$ and $$$H$$$, the width and height of the screen. The second line contains integers $$$A$$$ and $$$B$$$, the width and height of the logo. The third line contains integers $$$x_0$$$ and $$$y_0$$$, representing the starting position of the logo (measured from the bottom left corner of the screen to the bottom left corner of the logo). The last line contains integers $$$x$$$ and $$$y$$$, meaning the logo has the same initial direction as a vector pointing $$$x$$$ units right and $$$y$$$ units up.
## Constraints
$$$1 \le A \lt W \le 1000$$$
$$$1 \le B \lt H \le 1000$$$
$$$1 \le A+x_0 \le W$$$
$$$1 \le B+y_0 \le H$$$
$$$-10^5 \le x,y \le 10^5$$$
$$$x \ne 0$$$ or $$$y \ne 0$$$
### Subtask 1 [20 $$$1 \le W,H,x,y \le 15$$$
Let $$$T$$$ be the minimum amount of seconds after beginning such that the logo is at position $$$(x_0,y_0)$$$ travelling in direction $$$(x,y)$$$. Print the 6 digits beginning from the first non-zero digit of $$$T$$$.
If this will never happen, print '-1'.
11 11 1 1 5 5 1 1
282842
$$$T = 28.2842712$$$
**Bobliu** the monkey lives on a banana tree. The tree can be modelled as a tree (a connected graph with $$$N$$$ nodes and $$$N-1$$$ edges). Bob is currently on the ground, marked node $$$1$$$. Every day, $$$2$$$ new nodes (not always distinct) grow a banana, and Bob climbs from his current spot to the 2 bananas (in any order) and eats them. He then takes a nap where he is and sleeps until the next day. What is the least distance he must travel?
The first line contains $$$N$$$, the number of nodes, and $$$D$$$, the number of days.
The next $$$N-1$$$ lines contain $$$a$$$, $$$b$$$, and $$$c$$$, marking a branch between $$$a$$$ and $$$b$$$ of length $$$c$$$.
The next $$$D$$$ lines contain $$$x$$$ and $$$y$$$, the location of the 2 bananas that day.
## Constraints
For all subtasks:
$$$1 \le a,b,x,y \le N$$$
$$$0 \le c \le 1000$$$
$$$1 \le N \le 10^5$$$
$$$1 \le D \le 10^6$$$
### Subtask 1 [10 $$$1 \le D,N \le 10$$$
### Subtask 2 [20 $$$1 \le N \le 1000$$$
Output the minimum total distance the monkey must travel.
5 2 1 2 4 2 4 3 4 3 1 5 4 1 5 3 2 5
14
On the first day, Bob starts at node $$$1$$$ and travels to node $$$3$$$ and then node $$$5$$$ to eat the bananas.
On the second day, Bob is already at node $$$5$$$ and eats the banana before travelling to node $$$2$$$.
After the revolution, [redacted] has been unrated again and all his points have been taken away. Now, he is working his way back up. On DMOJ there are $$$N$$$ problems, the $$$i^\text{th}$$$ of which takes $$$s_i$$$ minutes for him to implement and are worth $$$v_i$$$ points.
Unfortunately, due to [redacted]'s poor programming abilities, he must rely on Bruce for help. This year there are $$$Q$$$ classes. During each class, he is taught the problems from $$$l$$$ to $$$r$$$ and has $$$t$$$ minutes to solve the problems. He can only solve the topics he has been taught that class because after the class, he looks at memes and forgets everything he learned.
Every time [redacted] solves problem $$$i$$$, they gain $$$v_i$$$ points. **Each problem can be solved at most once per class.**
Help [redacted] regain his ranking and calculate how many points can be obtained by the end of the year.
The first line contains $$$N$$$.
The next $$$N$$$ lines contain $$$s_i$$$ and $$$v_i$$$, representing time and value of the $$$i^\text{th}$$$ problem.
The next line contains $$$Q$$$.
The next $$$Q$$$ lines contain $$$l$$$, $$$r$$$, and $$$t$$$ indicating a class $$$t$$$ minutes long covering problems from $$$l$$$ to $$$r$$$, including $$$l$$$ and $$$r$$$.
## Constraints
For all subtasks:
$$$1 \le N,v_i \le 10^4$$$
$$$1 \le Q \le 10^5$$$
$$$1 \le s_i,t \le 100$$$
$$$1 \le l \le r \le N$$$
### Subtask 1 [20 $$$r-l \le 100$$$
### Subtask 2 [30 $$$Q \le 10^4$$$
### Subtask 3 [50 No additional constraints.
The maximum total points that can be earned.
2 2 30 2 35 2 1 2 4 1 2 3
100
4 30 50 20 40 40 45 20 45 4 2 4 100 1 4 100 1 1 100 1 3 100
455
10 60 55 85 72 86 61 85 55 63 43 39 65 30 44 6 90 28 97 48 39 10 8 9 53 5 6 40 9 10 8 1 4 65 1 4 84 8 10 15 9 9 98 5 8 81 5 6 79 2 7 73
922
Sample 1: In the first class, he can solve problems 1 and 2. In the second class, he solves problem 2.
Amy crashed onto a distant planet and broke her starship's window. She needs to replace it with resources from the planet.
After some exploration, Amy found a gem consisting of many small crystals arranged in a flat grid lattice with $$$N$$$ rows and $$$M$$$ columns. While most of these crystals are identical, $$$K$$$ of them, called **impurities**, are made of other materials of varying strength. The melting point of any gem plate is equal to the sum of the strengths of all the impurities it contains. A plate containing no impurities (pure fragment) has a melting point of $$$0$$$.
Any ship must be heat resistant so it can withstand the high temperature inside stars. To create her window, Amy will need to cut out a rectangular plate with $$$R$$$ rows and $$$C$$$ columns. Help her determine the highest melting point of a plate she can use for her new window.
The first line contains $$$R$$$ and $$$C$$$.
The second line contains $$$N$$$ and $$$M$$$.
The third line contains $$$K$$$.
The next $$$K$$$ lines consist of integers $$$x$$$ $$$y$$$ $$$t$$$, indicating an impurity at row $$$x$$$ and column $$$y$$$ with strength $$$t$$$.
## Constraints
$$$1 \le x, R \le N \le 10^9$$$
$$$1 \le y, C \le M \le 10^9$$$
$$$1 \le K \le 10^5$$$
$$$-10^{12} \le t \le 10^{12}$$$
### Subtask 1 [10 $$$1 \le N, M \le 1\,000$$$
Output the maximum melting point of a rectangle with $$$R$$$ rows and $$$C$$$ columns that is contained in the gem.
1 1 10 10 6 1 1 10 2 2 5 3 2 8 2 3 3 4 4 -1 5 5 12
12
2 2 10 10 6 1 1 10 2 2 5 3 2 8 2 3 3 4 4 -1 5 5 12
16
1 1 10 10 6 1 1 -10 2 2 -5 3 2 -8 2 3 -3 4 4 -1 5 5 -12
0
3 3 5 5 5 3 3 1000 1 3 -9999 5 3 -9999 3 1 -9999 3 5 -9999
1000
First sample:
The $$$1$$$ by $$$1$$$ rectangle with the highest melting point is $$$(5,5)$$$.