In a not-so-far dystopian future, people are paired with their soulmates via machine learning algorithms. This has streamlined the process of marriage so much that Mel, a baker, can't keep up with all the orders for wedding cakes, and he needs your help!
Mel's cakes are constructed with 5 layers, and each cake must be constructed in order (layer 2 can only be created after layer 1 is placed, layer 3 can only be created after layer 2 is placed, and so on). Each day, Mel gets the ingredients for one layer, which he can use to continue building one cake. He can also choose to not build that layer, but if he doesn't the ingredients spoil and he can't use them later!
Mel is good at multitasking so he can build many cakes simultaneously. Given the layer ingredients Mel gets for $$$N$$$ days, how many cakes can Mel complete, assuming he starts with nothing?
The first line contains a single integer $$$N$$$ ($$$1 \le N \le 10^6$$$), denoting the number of days Mel will get ingredients.
The next line contains $$$N$$$ integers $$$a_1,...,a_N$$$ ($$$1 \le a_i \le 5$$$), where Mel can build layer $$$a_i$$$ on the $$$i$$$th day, if he chooses.
Output one integer, the number of cakes Mel can finish.
11 1 1 2 3 4 4 5 2 3 4 5
2
In the first example, Mel can construct two cakes; one with ingredients from days 1, 3, 4, 5, and 7; and another with ingredients from days 2, 8, 9, 10, and 11.
You have meticulously collected all possible types of jellybeans and now you want to display them by splitting them into a series of piles.
Specifically, jellybeans have $$$N$$$ different qualities (size, color, taste, etc). Quality $$$i$$$ has $$$q_i$$$ options. Given that you have collected all the jellybeans, you own one example of every combination of each quality.
You have now decided to split them up so they can be put on display around the world. However, you're very concerned so you have adopted an interesting procedure. If possible, you divide the initial pile into two equally sized piles in the first round. In the next round, attempt to split each of these piles once again into equally sized piles. You then continue until this is no longer possible.
Given the number of qualities $$$N$$$ and the number of options for each quality, how many rounds will this process last?
First Line: A single integer, $$$1 \leq N \leq 10^4$$$
Second Line: $$$N$$$ integers $$$1 \leq q_i \leq 10^4$$$
The number of rounds the process will last.
2 6 2
2
Since there are two qualities with $$$6$$$ and $$$2$$$ options respectively, there are $$$12$$$ total jellybeans in your collection.
Round 1: Split $$$12$$$ into two piles of $$$6$$$.
Round 2: Split the two piles of $$$6$$$ into four piles of $$$3$$$.
To support local bakeries, you've decided to organize a Brownie Brawl, where competitors face off and try to bake as many brownies as possible in a given time limit!
Before they compete, each baker is interviewed and asked how many brownies they plan on baking:
Baker 1 claims, "I will bake $$$a_1$$$ brownies, and they'll be the best brownies you've ever tasted!"
Similarly, Baker 2 claims, "I plan on baking $$$a_2$$$ brownies, and they're going to be way better than anyone elses."
Baker 3 decides to switch it up, and states: "I'm going to bake $$$a_3$$$ times as many brownies as the previous two bakers, combined. That way, I'll surely win".
This ambitious claim got the crowd roaring, and from then on each baker made a similar claim, to bake $$$a_i$$$ times as many brownies than the previous two bakers combined. As the organizer, you appreciate the enthusiasm, it's also gotten you slightly worried: if everyone bakes as many brownies as they claim, how many brownies will you end up with?
The first line contains a single integer, $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$), the number of bakers. The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), which correspond to each baker's claim.
For each baker, output the number of brownies they claim to bake, modulo $$$10^9+7$$$.
4 2 3 2 3
2 3 10 39
In the example test case:
Baker 1 and 2 make 2 and 3 brownies, respectively.
Baker 1 and 2 combined bake 5 brownies, so baker 3 makes $$$2 \cdot 5 = 10$$$ brownies.
Baker 2 and 3 combined bake 13 brownies, so baker 4 makes $$$3 \cdot 13 = 39$$$ brownies.
You just saw an ad on TV about Starburst and the new "juicy" version. Since you want to try it out, you want to go to the nearest convenience store to pick it up. When thinking about your options, you find three different transportation methods available to you. When evaluating these three options, you know you want to get there as fast as possible. If there are two different transportation methods that take the same amount of time, you will choose the one that saves money (you can use the saved money to buy more Starburst!). The three options are:
Bus (B): 3 minutes per unit of distance, 2 dollars per unit of distance
Car (C): 10 minutes per unit of distance, 10 dollars per unit of distance
Walk (W): 10 minutes per unit of distance, 5 dollars per unit of distance
Output the mode of transportation (B, C, or W) that is most optimal. If there is no path, return "None".
The first line contains two integers $$$m$$$ and $$$n$$$ ($$$1 \leq m, n \leq 750$$$), representing the number of rows and columns respectively. The next $$$m$$$ lines contain $$$n$$$ letters each. There is exactly one S and one E, representing the start and end, respectively. All other letters are B, C, or W, representing the mode of transportation available for that cell.
You may travel horizontally or vertically.
Output the mode of transportation (B, C, or W) that is most optimal. If there is no path from the start to the end that only uses a single mode of transportation, print "None".
4 4 BBCC BSCC BWWE BBBB
B
Gretel is running a bakery that specializes in mass-producing gingerbread houses! Her bakery is separated into two divisions: one that bakes and assembles the gingerbread pieces and the other which decorates the assembled houses. The latter division is currently dealing with a backlog of $$$10^{18}$$$ gingerbread houses that have yet to be decorated, but is short on workers to frost all of them. Until more help can arrive, Gretel decides to arrange the houses in a horizontal row and assign each of her $$$N$$$ workers to a starting point. Worker $$$i$$$ starts at $$$s_i$$$ (not necessarily unique), which refers to the $$$(s_i)$$$-th leftmost gingerbread house. Each worker can decorate exactly one house per minute, and will move onto decorating the next house to the right regardless of whether or not it is decorated yet. For $$$Q$$$ points in time $$$q_i$$$, Gretel would like to know the number of distinct gingerbread houses that have been decorated at least once after $$$q_i$$$ minutes have elapsed. Can you help her retrieve these counts?
The first line of input contains two space-separated integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N, Q \leq 10^5$$$), representing the number of workers and queries, respectively. The second line of input contains $$$N$$$ space-separated integers $$$s_i$$$ ($$$1 \leq s_i \leq 10^9$$$), representing the starting points of each of the workers on the row of houses. The third line of input contains $$$Q$$$ space-separated integers $$$q_i$$$ ($$$0 \leq q_i \leq 10^9$$$), representing the points in time Gretel would like to know the number of decorated houses.
Output a single line with $$$Q$$$ space-separated integers, representing the answers to Gretel's queries in the order that they were given in.
2 5 5 10 1 2 3 4 5
2 4 6 8 10
5 10 10 20 30 40 50 11 12 13 14 9 8 7 6 4 3
51 52 53 54 45 40 35 30 20 15
Inspired by https://www.youtube.com/watch?v=yEmgU9oX7ns
Tom is very fond of Jaffa Cakes, but he is having trouble convincing Zendaya to eat his favorite dessert. Because Tom knows that Zendaya is a fan of number games, he decides to play a game with her involving the serial numbers on each of the $$$N$$$ Jaffa Cakes he possesses. The $$$i$$$-th Jaffa Cake initially has serial number $$$x_i$$$, and Zendaya can choose to repeatedly modify the serial numbers via a special operation. Each operation involves choosing an index $$$j$$$ such that $$$1 \leq j \leq N$$$ and a positive integer $$$y$$$, and every Jaffa Cake except for the $$$j$$$-th one will have its serial number changed to $$$x_i \oplus y$$$ (in other words, $$$x_i$$$ is XORed with $$$y$$$ for all $$$i \neq j$$$).
If Zendaya can successfully transform all $$$N$$$ serial numbers to $$$0$$$ using the operation, she does not have to eat a Jaffa Cake. Otherwise, she must humor Tom's request and eat the dessert. Given the serial numbers on the Jaffa Cakes, can you help Zendaya figure out if she has a chance to avoid a tasting?
The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 100$$$) representing the number of Jaffa Cakes that Tom has for the game. The second line of input contains $$$N$$$ space separated integers $$$x_i$$$ ($$$0 \leq x_i \lt 2^{30}$$$) that represent the original serial numbers of the Jaffa Cakes.
If Zendaya (assuming she plays optimally) has to eat a Jaffa Cake after playing the game, print "JAFFA!" on a single line. Otherwise, output "NO JAFFA!" on a single line.
4 1 2 3 4
NO JAFFA!
3 1 1 1
JAFFA!
Rectangletown is preparing for the biggest heat wave of the year, in the best way possible: free ice cream for everyone!
Rectangletown can be represented as an $$$n$$$ by $$$m$$$ grid of houses, each of which is allowed to order some amount of ice cream. To simplify the ordering, production, and delivery process, the following rules were put in place:
All you have to work with are some of the orders that have already been sent in by some of the houses. Can you use these orders to recover $$$a_1, \ldots a_n$$$ and $$$b_1, \ldots, b_m$$$ uniquely?
The first line of input will contain two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n \cdot m \leq 1000$$$, representing the number of rows and columns of Rectangletown, respectively.
Then, $$$n$$$ lines follow, where the $$$i$$$th row contains $$$m$$$ orders: $$$x_{i,1}, \ldots, x_{i,m}$$$. Each order $$$x_{i,j}$$$ will either be the character '?', denoting an unknown order, or an integer ($$$1 \leq x_{i,j} \leq 10^9$$$), denoting the number of ice cream buckets the house at row $$$i$$$ and column $$$j$$$ ordered.
If there exists a unique sequence of values $$$a_1, \ldots, a_n$$$ and $$$b_1, \ldots, b_m$$$ that are consistent with the orders, output "YES" on its own line, followed by $$$a_1, \ldots, a_n$$$ on the second line, and $$$b_1, \ldots, b_m$$$ on the third.
Otherwise, output "NO".
2 2 ? 2 2 ?
NO
3 3 2 ? 3 ? 1 ? 4 ? ?
YES 1 1 2 2 1 3
In the mountainous country of Puddia, different cities trade pudding with each other. To traverse through the mountains, there are a number of mountain passes which directly connect two cities together. It is possible to reach every city starting from any city through some sequence of mountain paths.
However, as the leader of the country, you have recently received news on an upcoming storm! Initially, all of the mountain passes are open, but because of the storm, some of these mountain passes might close! In addition, a closed mountain pass could reopen after some time. You have a list of these mountain pass openings and closings, and you want to know the total pairs of distinct cities that can still trade pudding after each event.
The first line of contains two integers $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) and $$$m$$$ ($$$n - 1 \leq m \leq \min(2 \cdot 10^5, \frac{n(n - 1)}{2})$$$), indicating the number of cities and the number of mountain passes, respectively.
The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n, x \neq y$$$) indicating that there is a mountain pass between cities $$$x_i$$$ and cities $$$y_i$$$. It is guaranteed that there do not exist two indices $$$i$$$ and $$$j$$$ where $$$1 \leq i \lt j \leq n$$$ and either $$$(x_i, y_i) = (x_j, y_j)$$$ or $$$(x_i, y_i) = (y_j, x_j)$$$.
The next line contains a single integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$), indicating the number of updates.
The $$$i$$$-th of the next $$$q$$$ lines contain a single integer $$$c_i$$$ ($$$1 \leq c_i \leq m$$$). If the $$$c_i$$$-th mountain pass was previously open, then the mountain pass is marked as closed in this update. If the $$$c_i$$$-th mountain pass was previously closed, then the mountain pass is marked as open instead.
For each of the $$$q$$$ updates, print the number of pairs of distinct cities that are still connected by some sequence of mountain passes after the update.
4 4 1 2 2 3 3 4 4 1 8 1 2 3 4 1 2 3 4
6 3 1 0 1 3 6 6