One of Teddy's amazing cream cheese brownies As Valentine's Day is coming up, Teddy is spending some time baking cream cheese brownies to give to their friends! Since Teddy is such a nice friend, they have taken requests from each of their $$$N$$$ friends as to how large of a brownie they would like to receive. A friend will be happy to receive a brownie larger than the size that they asked for.
Unfortunately, Teddy had not expected such an overwhelming number of requests (they are very popular), and so they are not sure that they will be able to accommodate everyone with their $$$M$$$ baking tins. Each of the baking tins that Teddy has have a specific volume of brownies that they can be used to bake, and moreover, each baking tin can only be used once. Finally, Teddy can only assign (at most) one baking tin per request, so the same baking tin cannot be used to create a larger brownie that would later be split into two (or more) pieces.
With all of this in mind, Teddy would still like to make it a very special Valentine's Day for their friends, and so they would like to maximize the number of friends who receive their desired amount (in units of volume) of brownies. Your job is to assist Teddy in calculating this value by assigning the baking tins optimally. Luckily for you, it's a rainy day out, so you have plenty of time to sit inside and code up an algorithm to assist Teddy.
The input will begin with a line containing two space-separated integers, $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 2 \cdot 10^5$$$), representing the number of friends that requested brownies and the number of baking tins that Teddy has, respectively.
The next line will contain $$$N$$$ space-separated integers, $$$s_1, s_2, \dots, s_N$$$ ($$$1 \leq s_i \leq 2 \cdot 10^9$$$ for all $$$i \in \{1, 2, \dots, N\}$$$), where $$$s_i$$$ represents the size (in units of volume) of the brownie that Teddy's $$$i$$$-th friend requested.
The final line of input will contain $$$M$$$ space-separated integers, $$$t_1, t_2, \dots, t_M$$$ ($$$1 \leq t_i \leq 2 \cdot 10^9$$$ for all $$$i \in \{1, 2, \dots, M\}$$$), where $$$t_i$$$ represents the size (in units of volume) of the $$$i$$$-th baking tin that Teddy owns.
The output should consist of a single line containing a single integer, the maximum number of Teddy's friends that can receive their desired size (or larger) of brownie, should Teddy pair the baking tins to requests optimally.
5 3 8 12 25 3 10 1 8 20
2
Alberto loves working out. Unfortunately, he is single, and with Valentine's Day coming up, he has decided to work even harder. Each day, he will drink $$$N$$$ ($$$1 \leq N \leq 10^5$$$) new protein shakes throughout his workout, and each protein shake will give him $$$E_i$$$ units of energy ($$$1 \leq i \leq N$$$, $$$0 \leq E_i \leq 10^5$$$). Since he is superstitious, he always drinks his shakes in the order listed in the input, and once he starts drinking a shake he will finish it completely.
Today, his workout consists of doing as many sets of $$$M$$$ ($$$1 \leq M \leq 10^3$$$) pushups as possible. He needs $$$k$$$ units of energy to do the $$$kth$$$ pushup, and he will stop once he completes the current set. Once he completes a set, his energy level resets to $$$0$$$. He will continue doing sets until he runs out of protein shakes.
Given the units of energy in the protein shakes that he will drink today, how many complete sets of pushups will Alberto be able to complete?
The first line contains the integers $$$N$$$ ($$$1 \leq N \leq 10^5$$$) and $$$M$$$ ($$$1 \leq M \leq 10^3$$$).
The second line contains $$$N$$$ integers, $$$E_1, E_2, … E_N$$$ ($$$1 \leq i \leq N$$$, $$$0 \leq E_i \leq 10^5$$$).
A single integer representing the number of sets Alberto will complete.
4 5 2 20 80 4
2
3 3 20 5 2
1
In the first example, Alberto needs to use the first two energy drinks to make it through the first set (which takes $$$1+2+3+4+5$$$ units of energy), upon which his energy resets to $$$0$$$. The third energy drink gets him through the second set (which takes $$$6+7+8+9+10$$$ units of energy), and the last energy drink cannot get him through the third set.
It has started raining, so you decide to stay after school to finish your homework. You pull out your statistical analysis homework, a grid of n by n numbers. You notice a curious pattern: each cell at column $$$j$$$ and row $$$i$$$ has value $$$\left \lfloor{\frac{j}{i}}\right \rfloor$$$, (the floor of j/i), where $$$j$$$ ranges from $$$[1\cdots n]$$$ and $$$i$$$ ranges from $$$[1\cdots n]$$$. You are curious as to how many cells have the same value $$$k$$$.
The first line of input contains two integers, $$$1 \leq n \leq 100000$$$, and $$$0 \leq k \leq n$$$.
Please print an integer, the number of occurrences of value $$$k$$$.
4 2
2
A 4x4 table looks like this: $$$$$$ \begin{array}{c c} & \begin{array}{c c c c} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{c|c|c|c} 1 \\ 2\\ 3\\ 4 \end{array} & \begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \cr \hline 0 & 1 & 1 & 2 \cr \hline 0 & 0 & 1 & 1 \cr \hline 0 & 0 & 0 & 1 \cr \hline \end{array} \end{array} $$$$$$
Paulina the Precipitation Princess is working on a very interesting new method of creating rain, which she has named "prime precipitation".
She has specially engineered raindrops with unique aerodynamic properties, where their fall speed depends on their height. Given a raindrop's height, every second it will fall by exactly the number of prime divisors it has. For example, a raindrop at a height of $$$12$$$ will fall to a height of $$$9$$$ (as $$$12$$$ is divisible by two twice and three once). A raindrop at a height of $$$10$$$ will fall to a height of $$$8$$$ (as $$$10$$$ is divisible by two and five).
Given that elevation $$$1$$$ is the ground, such a raindrop may fall to the ground in $$$5$$$ seconds ($$$10 \rightarrow 8 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 1$$$).
For her first rainstorm, she will be dropping one raindrop of each height $$$[1, H]$$$. She will drop a raindrop, wait for it to hit the ground, then drop the next one.
Given this maximum height $$$H$$$, help Paulina determine how much time it will take for her to complete this process.
A single integer, $$$H$$$ ($$$1 \leq H \leq 4 \cdot 10^6$$$).
A single integer, the number of seconds for Paulina to drop all the rain.
6
11
You may need 64-bit integers for this problem.
Due to time limit constraints, this may be difficult to solve in Python.
Rose woke up in a mystical flower field. Since her name is Rose, she wants to collect as many of the $$$N$$$ roses in the field with her $$$E$$$ energy level (convince yourself that Rose can keep track of her energy quantitatively). Rose also enjoys running and moves at a speed of $$$1$$$ rosemeters/second. However, once a rose $$$i$$$ is picked from the field, the other roses disappear, and a rain monster will appear a distance $$$r_i$$$ rosemeters away from the rose and is restricted to moving along the perimeter with radius $$$r_i$$$ (centered at the rose).
Unfortunately for Rose, the rain monster has been spending lots of time at ✨ Rainy Day Monster Running and Fitness Center ✨ and will move $$$k_i$$$ times faster than Rose and does its best to catch Rose. For each rose, Rose has two options. Rose can move directly away from the rose. Alternatively, she can run along a circle of radius $$$e$$$ rosemeters centered at the rose, but she can only do this once for the current rose, which costs her $$$\lceil e\rceil$$$ energy, and she can choose to run along this circle forever if she wants to. Once she escapes the clutches of the monster, all the other roses reappear.
What is the maximum number of roses Rose can collect with her $$$E$$$ energy, given that she can choose to collect the Roses in any order she wants? Note that Rose can choose not to collect certain roses if she does not want to.
A diagram of the field is shown below (as well as two separate possible paths Rose could take assuming that the monster cannot catch her–note that path 2 will cost some $$$e$$$ energy):
The first line contains $$$N$$$ ($$$1\leq N\leq 500$$$), the number of roses and her energy level $$$E$$$ ($$$1 \leq E \leq 10^5$$$).
The next $$$N$$$ lines will contain two real numbers, the distance the monster spawns away from Rose $$$r_i$$$ ($$$1\leq r_i\leq 500$$$), and its speed factor compared to Rose $$$k_i$$$ ($$$1\leq k_i\leq 10^9$$$).
A single integer, the maximum number of roses Rose can collect with her $$$E$$$ energy.
4 5 5.00 4.00 1.00 2.00 1.15 3.15 6.00 5.00
3
Bob wants to create the most beautiful painting ever. The painting must be enormous, so he has purchased a grid of width $$$10^9$$$ and height $$$10^9$$$. Bob decided that today would be the best day to make the painting, but unfortunately it turned out to be a very rainy day. As a result, there are $$$M$$$ columns in the painting which have been completely washed out by the rain.
Before the rain began, Bob managed to paint $$$N$$$ rectangles on the painting. Rectangles are Bob's favorite shape, but if one rectangle is covered up by another, he would be very sad, so he made sure that none of the rectangles overlap.
Bob wants to know how many cells of paint on the original painting will remain after water washes away $$$M$$$ of the columns.
The first line of input contains integers $$$N$$$ and $$$M$$$ ($$$1 \le N, M \le 2 \cdot 10^5$$$).
The following $$$N$$$ lines each contain four integers $$$r_{1_i}$$$, $$$c_{1_i}$$$, $$$r_{2_i}$$$, and $$$c_{2_i}$$$ ($$$1 \leq r_{1_i}, c_{1_i}, r_{2_i}, c_{2_i} \leq 10^9$$$, $$$r_{1_i} \leq r_{2_i}$$$, $$$c_{1_i} \leq c_{2_i}$$$). These represent the bottom-left and top-right cells of the $$$i$$$-th rectangle of paint respectively. It is guaranteed that none of these rectangles will intersect.
The last $$$M$$$ lines of input each contain one integer $$$w_j$$$, indicating the $$$j$$$-th column of the painting which has been washed out by water. ($$$1 \le w_j \le 10^9$$$). Each $$$w_j$$$ is distinct.
Output the number of cells in the painting which contain paint but haven't been washed away.
4 3 3 1 5 4 1 5 4 6 1 2 1 3 5 5 5 5 2 4 5
11
3 3 1 5 3 7 1 8 2 8 4 6 5 8 1 3 10
17
Test 1:
As shown in the diagram on the left, there are four rectangles, occupying a total area of $$$23$$$. After the rain washes away some of the columns, there are four rectangles, occupying an area of $$$1 + 4 + 3 + 3 = 11$$$.
Test 2:
In this case, all of the water avoids the paint, so the answer is just the total amount of paint originally: $$$17$$$.
As a Valentine's Day surprise, you want to deliver chocolate to all of your friends. You have $$$N$$$ friends, each living in their own house labeled from $$$1$$$ to $$$N$$$. There are a series of $$$M$$$ one-way roads which connect houses together.
Unfortunately, it is storming heavily outside, so you resort to driving on the one-way roads instead of walking. Assuming you can start at any friend's house and can traverse through roads/houses more than once, what is the maximum number of unique friends you can deliver chocolate to?
The first line of input contains the integers $$$N$$$ and $$$M (1 \leq N \leq 10^3, 1 \leq M \leq 2N)$$$.
The next $$$M$$$ lines contain two integers $$$A$$$ and $$$B$$$, indicating that there is a one-way road pointing from house $$$A$$$ to house $$$B$$$. $$$(A \neq B, 1 \leq A, B \leq N)$$$
Please output an integer $$$K$$$, the maximum number of houses you can visit.
3 2 1 2 2 3
3
3 1 1 2
2
5 5 3 5 3 2 2 3 4 5 5 1
4
The recent rain and low temperatures have caused many trees to fall over on the streets of Austin, turning many two-way streets into one-way streets. In fact, so many trees have fallen over that you can only leave an intersection via one street, as all the other streets have been blocked by fallen trees. Additionally, the roads have become very icy, and the traffic lights are no longer operating due to a power outage, leading to very dangerous driving conditions.
Thankfully, most people are smart enough to not be driving in these conditions. However, two idiots have decided to try driving around in these treacherous conditions. They each start at separate intersections and take one minute to drive from one intersection to the next, taking the only available road at each intersection. If they enter the same intersection at the same time, they will crash into each other, being unable to brake under the icy conditions.
Your job is to find out how many unique pairs of starting intersections will not result in a crash between the two drivers.
The first line contains $$$n$$$ ($$$2 \leq n \leq 2 \times 10^5$$$), which is the number of intersections. The following $$$n$$$ lines each contain an integer $$$y$$$ ($$$1 \leq y \leq n$$$), meaning that the $$$x$$$th line (after the first) represents a one-way street from intersection $$$x$$$ to intersection $$$y$$$. Note that $$$x \neq y$$$, as an intersection can't have a street to itself.
Print out how the number of unique pairs of starting intersections that will not result in a crash between the two drivers. Because this number can be very large, please mod your final answer by $$$10^9 + 7$$$. Note that the order of the intersections does not matter. $$$(1,2)$$$ is the same as $$$(2,1)$$$.
3 2 1 1
2
6 2 1 1 5 4 4
13
You have been competing at UTPC since about 6 PM, and you realized that you need to rush to a birthday party immediately after! You peek outside, and you see that it has been raining acid! You don't want to get harmed, so you decide to construct some umbrellas.
You quickly run to Welch and start searching for chemicals. Suppose you currently are in possession of a set of chemicals. Each chemical can be described by some positive integer $$$c$$$. To create new chemical for the umbrella, you can pick a subset of the chemicals you have and compute the bitwise XOR of the subset, which describes the new chemical. If your set of chemicals is empty, the new chemical you create is just 0.
Any chemical you create can be used to construct an umbrella. Acids can also be described by a positive integer. Some chemical $$$c$$$ can protect against acid $$$a$$$ with protection level $$$b$$$ if $$$c \& a = b$$$, where $$$\&$$$ is bitwise AND.
You are given multiple queries, where you either add a new chemical to your overall set or check if you can create a chemical that can protect against the acid. Figure out what acids you can protect against for each query!
The first line contains $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — the number of queries. The following $$$q$$$ lines contain either of the following two inputs:
For each query of type 2, print "YES" if you can construct some chemical $$$c$$$ where $$$c \& a = b$$$, and "NO" otherwise. Each answer should be on its own line.
8 1 3 2 3 2 2 2 2 1 1 2 3 2 2 2 2 2 0 2 2 1073741823 0
NO YES YES YES NO YES