In a spark of creative genius, Remi has constructed a powerful laser that shoots out a beam of highly concentrated raisin energy. Many interested parties, including government contractors, have already reached out about the raisin laser, but first Remi wants to make sure that her 'raiser' is fully operational and functions just like a regular laser. To test the raiser, Remi has constructed a grid maze or 'mais' with deflective mirrors to see if she can place the raiser somewhere in the mais and have its beam reflect off of the angled mirrors and eventually hit a target receptor. Help Remi figure out all of the places where she could place the raiser such that its beam will eventually hit the receptor if it behaves like a regular laser.

Catherine the Grape has an immense responsibility: to build power lines so that all of the citizens of Raisin Metropolis have guaranteed access to power. There are $$$n$$$ locations throughout the city that Catherine must ensure have power, numbered $$$1$$$ through $$$n$$$, with the power plant located at location $$$1$$$. A location has power if it is connected to the power plant via some sequence of power lines.

As part of her grape responsibility, Catherine must ensure that all citizens receive power without costing the city too much. The power company has offered Catherine $$$m$$$ quotes for power lines they might build, where the $$$i$$$th quote lists the cost $$$c_i$$$ to build a power line connecting locations $$$u_i$$$ and $$$v_i$$$. (Connecting two locations allows power to flow in either direction between them.)

The owner of the power company wants to help Catherine and offers her a coupon that allows her to swap the costs of any two quotes before building any power lines. Seeing that using the coupon can never increase the minimum cost of powering the city, Catherine agrees to the deal, and selects the two costs to swap and the set of power lines to build in a way that minimizes the overall total cost of connecting all locations to the power plant. She wonders, though, if there were other possible swaps that also would have yielded this same optimal cost?

Compute how many different quote swaps Catherine could have picked so that the optimal cost to connect power to the city is minimized. Two swaps are identical if they involve the same two quotes.

The power company guarantees that if Catherine chooses to build all of the power lines, then all $$$n$$$ locations will be connected to the power plant (though doing so is not necessarily the cheapest way to power the whole city).

The Sun-Maid is at her raisin factory, where this season's $$$n$$$ raisins are ready to be packaged and shipped worldwide to all the eager consumers.

All the raisins are lined up on the conveyor belt, one after the other, where raisin $$$i$$$ has size $$$s_i$$$. Since every raisin is special and unique, no two raisins have the same size ($$$s_i \neq s_j$$$ if $$$i \neq j$$$).

The first raisin box of the year is created by selecting a contiguous group of raisins of any size. Each potential raisin box (with distinct endpoints) can be made with equal probability.

The Sun-Maid must be careful not to upset the raisins by following a very specific set of traditions. The Sun-Maid has a tradition of eating the first box of raisins every year. When she opens the box, she carefully selects the largest raisin, awarding it the Specialest Raisin of the Year Award, sparing it from consumption.

Of course, each raisin would like to receive this incredibly prestigious award. Given each raisin's size, determine the probability that it's selected as the Specialest Raisin, multiplied by the total number of possible boxes, $$$\binom{n + 1}{2}$$$.

Note: Watch out for integer overflows.

In order to make raisins, Farmer Joe has a $$$r$$$ x $$$c$$$ grape field that consists of $$$r \cdot c$$$ patches of grass. Each patch of grass has a certain number of grapes in it at the end of the harvest. When it is time to harvest, Farmer Joe will start in the top left patch of grass. He will collect all grapes from this patch of grass, add them to a container (will start as container 0), and will continue moving right. He will repeat this process and add the grapes to container 1, 2, 3, etc. Once he has finished packaging the grapes from the top right patch of grass, he will continue this process but move downwards until he hits the bottom right patch of grass. He will then continue moving left, and then upwards. Once he has visited a patch of grass, he will never come to it again. For example, when Joe is traversing upwards on the left side of the field, he will turn right again once he reaches the second row (as he has already visited the first row). He will continue in this spiraling motion until he has packaged all grapes.

Farmer Joe is now ready to sell his grapes to Sun-Maid. However, Sun-Maid is very picky. They will buy all the grapes in container 0, container $$$k$$$, container $$$2k$$$, etc. More generally, they will buy a container if the container number $$$mod$$$ $$$k = 0$$$. How many grapes will Farmer Joe sell to Sun-Maid?

Every year in September, the town of Binissalem, Spain celebrates Festa des Vermar, a two-week-long festival starring – what else? – grapes. The celebration includes everything from wine-parades to grape-stomping.

You, in particular, are interested in the grape battle, which is exactly what it sounds like. You know that to be effective in the grape battle, you should choose the juiciest grapes to throw. Unfortunately, your brother gets to pick which grapes he wants first.

There are $$$N$$$ grapes in a row, with juiciness $$$a_1, a_2, ..., a_N$$$. Grape distribution happens as follows: your brother selects the first two grapes, chooses the juiciest one, and then gives you the remaining grape. He then selects the next two grapes and does the same thing, then the next two, and so on until all the grapes have been distributed.

Luckily, while your brother wasn't looking, you managed to change the order of the grapes in the row. If you permute the grapes optimally, what will be the maximum total juiciness of all the grapes you receive?

Note: Watch out for integer overflows.

Tweedledee and Tweedledum look similar, but their preferences are anything but. In particular, Tweedledee loves raisins but dislikes currants, while Tweedledum loves currants but dislikes raisins. However, both Tweedledee and Tweedledum hate sultanas. We can model this in the following way:

When Tweedledee eats a raisin, his happiness increases by 1; when he eats a currant, his happiness decreases by 1; when he eats a sultana, his happiness decreases by 2. On the other hand, Tweedledum's happiness increases by 1 when he eats a currant, decreases by 1 when he eats a raisin, and decreases by 2 when he eats a sultana.

Tweedledee and Tweedledum are attending a feast hosted by the March Hare and the Hatter. On the table lies a row of raisins, currants, and sultanas. Tweedledee sits on the left side, while Tweedledum sits on the right side. When the feast commences, they begin eating the fruits one-by-one, starting from their side.

Tweedledee and Tweedledum both start with happiness 0. In order to display proper manners they may only eat in the manner described above (no sharing, eating out-of-order, etc.) They may eat any number of fruits (so long as the combined number of fruits eaten does not exceed the total number on the table). What is the maximum total happiness (happiness of Tweedledee + happiness of Tweedledum) that can be attained?

Note that there are two versions of this problem. Read the input section for more details.

Rays Rais (short for Ray's Raisins) has been a big name in family owned raisin business around the area for a long time. So long, in fact, that apparently their name has been changed a few times since its creation!

As you read through ancient business records, you learn that Rays Rais was actually created by a man named Ray, who originally named the company after himself: Rays. But it wasn't very clear what a business named Rays sold, so he decided to double the name to get "Rays Rays", where the second Rays was supposed to be short for Raisins.

As time passed, it wasn't very clear that the second "Rays" was supposed to stand for Raisins, so it was eventually changed to "Rais", which caused a bit of confusion for a couple years as people adjusted to the new name.

Turns out, lots of family businesses did a similar thing to slowly rename their business. Namely, they would apply one of two operations to their business name:

• Operation 1: Repeat the name by concatenating a copy of it to the end.
• Operation 2: Change a single letter in the name.

As you study these names, you quickly realize that businesses tended to avoid changing their name, as it would get confusing for their customers!

Currently, you are trying to piece together the name of your favorite raisin business over time, but some of the details are missing; in fact, you only know of some of the names they've used, and when they were in use. Given this list of names, can you determine the minimum number of operations the business could've performed that would be consistent with the names you observe?

Note that there are two versions of this problem. Read the input section for more details.

Rays Rais (short for Ray's Raisins) has been a big name in family owned raisin business around the area for a long time. So long, in fact, that apparently their name has been changed a few times since its creation!

As you read through ancient business records, you learn that Rays Rais was actually created by a man named Ray, who originally named the company after himself: Rays. But it wasn't very clear what a business named Rays sold, so he decided to double the name to get "Rays Rays", where the second Rays was supposed to be short for Raisins.

As time passed, it wasn't very clear that the second "Rays" was supposed to stand for Raisins, so it was eventually changed to "Rais", which caused a bit of confusion for a couple years as people adjusted to the new name.

Turns out, lots of family businesses did a similar thing to slowly rename their business. Namely, they would apply one of two operations to their business name:

• Operation 1: Repeat the name by concatenating a copy of it to the end.
• Operation 2: Change a single letter in the name.

As you study these names, you quickly realize that businesses tended to avoid changing their name, as it would get confusing for their customers!

Currently, you are trying to piece together the name of your favorite raisin business over time, but some of the details are missing; in fact, you only know of some of the names they've used, and when they were in use. Given this list of names, can you determine the minimum number of operations the business could've performed that would be consistent with the names you observe?

Long ago, in Ancient Greek times, there lived a great conqueror, Alexander the Grape. He was known for his ability to expand his empire, all while planting miles and miles of grape vines along the way to mark where he had already been so as not to conquer the same civilization twice.

As Alexander's second-in-command, you are tasked with keeping up a ledger of the grape vines which have been laid across the lands. For each vine, you keep track of which two civilizations the vine connects (we will call these civilization $$$A$$$ and civilization $$$B$$$). You also keep track of which type of grapes will eventually grow on the vines since each vine can grow into either red or green grapes. A red grape vine indicates that Alexander's army can choose to travel from civilization $$$A$$$ to civilization $$$B$$$, but not from civilization $$$B$$$ to civilization $$$A$$$. Conversely, a green grape vine indicates that Alexander's army can choose to travel from civilization $$$B$$$ to civilization $$$A$$$, but not from civilization $$$A$$$ to civilization $$$B$$$.

Originally, Alexander the Grape was entirely certain that this, albeit complex, system of grape vines would be the key to directing his army from civilization to civilization so as to conquer as many of them as possible. Unfortunately, Alexander was quite hasty while planting the grape vines, and he does not remember with certitude which type of grapes were planted at the location of each vine.

Instead, Alexander only tells you with what probability the grapes will grow to be red. If Alexander dictates to you that a particular vine has probability $$$p$$$ to grow to be a red grape vine, then it also has a $$$1 - p$$$ probability to grow to be a green grape vine. It is assumed that $$$0 \leq p \leq 1$$$, of course.

Now, it is finally spring time and this means two things: firstly, it means that all grape vines now bear grapes and have grown according to probabilities dictated by Alexander the Grape, and secondly, it means that it is time for Alexander's army to conquer!

The lands are denoted by a collection of $$$N$$$ civilizations and $$$N - 1$$$ grape vines laid by Alexander and his army. It is guaranteed that, without the consideration of grape types, there is a unique path between every pair of civilizations. The remaining information available to you is the ledger of the grape vine information as dictated by Alexander. As its almost time to embark on another conquest, Alexander needs to consider his options on which civilization to begin his conquest from. The success of a conquest (measured in the number of unique civilizations visited) is quite important to Alexander, and as such, he would like you to calculate the following quantity: given that he chooses a starting civilization uniformly at random, and that the grape vines will grow with their predetermined probabilities, what is the expected number of reachable civilizations?

It's imperative that Alexander learns the result of this calculation as soon as possible in order to prepare the correct amount of weaponry, water, and food (in the form of raisins, of course) to pack for his army. Can you aid him in his calculations?

For generations, the Grape and Raisin factions were the greatest of allies. Each night at dinnertime, both factions would sit down and enjoy a meal together at their shared circular table. The factions had a very particular seating manner in order to ensure peaceful relations. As both factions have an equal number of members, no two members of the same faction may sit next to each other. This seating method ensures the maximum number of healthy conversations between members of different factions.

One day, a nasty feud broke out between the factions. It began with a brawl, during which the members of both factions were scrambled about. This means that the rule governing their seating pattern may have been violated to a large degree!

As the impromptu peacemaker between the two factions, it is your job to reunite the Grape and Raisin factions to their former glory. To do so, you may perform a series of swaps. In any given swap, you may choose two distinct faction members (possibly from different factions), and swap their positions at the table.

Eventually, your goal is to return the table to a state such that no two members from the same faction are sitting in an adjacent manner. If that is the case, then the Grapes and the Raisin may begin peace talks and become allies once again.

You must be prepared for the worst, though. Namely, given that each faction has $$$N$$$ members, you must report the maximum number of swaps required over any possible arrangements of faction members assuming that you act optimally (that is, you always perform the minimum number of swaps).

You are part of the production crew for a new brand of trail mix, featuring The World's Best Raisins$$$^{\text{TM}}$$$. The producers have a grand idea in mind: they will feature a bunch of hikers enjoying their trail mix on a picturesque mountain range!

Formally, the mountain range can be thought of as a collection of $$$n$$$ triangles resting on the number line, each centered horizontally at $$$x_i$$$ with height $$$h_i$$$. All mountains have a slope of +1 on the left and -1 on the right, and might intersect other mountains.

A mountain range containing 5 mountains.

The producers are very picky about what "picturesque" means in this context. In fact, they claim this mountain range looks too crowded, and they will do anything to realize their dream ad, including demolishing some of the mountains!

In an attempt to protect the mountain range from reckless destruction, you offer them a middle ground: they will specify $$$k$$$, the number of mountains to remove, but you get to pick which ones to remove. To preserve the landscape, you'd like the remaining $$$n-k$$$ mountains to cover as much area as possible. Can you figure out how much area will be left after the demolitions?

Carter owns a world-famous winery and realizes that demand for their wines has grown to such a point that they need to hire some help.

As their newest employee, they ask you to help them with the very secret recipe. The winery gets $$$n$$$ distinct types of grapes and to make a single bottle of wine, Carter uses one pound of $$$n - 1$$$ distinct grape types (so if $$$n = 4$$$, they will use $$$3$$$ different grapes, and one pound of each type to make the single bottle of wine). The big secret Carter lets you in on is that it doesn't actually matter which set of $$$n - 1$$$ grape types you pick, the blend will always turn out perfect so long as there are $$$n - 1$$$ different grape types used.

Carter has a big order of new grapes coming in so they want to clear up some inventory space. For grape type $$$i$$$, they would like to use at least $$$a_i$$$ pounds in making bottles of wine that day (since they have so much inventory, you can use as many pounds of $$$a_i$$$ you want, Carter just insists that you use at least $$$a_i$$$ pounds). Figure out the minimum number of bottles of wine you need to make so that for all grape types $$$i$$$, you have used at least $$$a_i$$$ pounds of it today.

While the COVID-19 pandemic is not over just quite yet, Mark had decided to make the most of his time during the pandemic by studying abroad in France. While France is known for its fine dining, Mark happened to visit a famous winery one day and was inspired to have some raisins as a snack.

Mark decided that he wanted to eat $$$n$$$ raisins today, and every few minutes or so, he picks out two raisins $$$i$$$ and $$$j$$$, and with some probability, decides to eat raisin $$$i$$$. If he does not eat raisin $$$i$$$, then he will eat raisin $$$j$$$. Regardless, the raisin that he did not eat is put back into the bowl. As it turns out, while it is completely random which two raisins Mark will pick out of the remaining raisins, the probability he picks any raisin $$$i$$$ over a raisin $$$j$$$ is predetermined. In the end, when there is only $$$1$$$ raisin left, that raisin has a brief momentary victory before being gobbled up by Mark.

Mark of course is satisfied with his raisins, but given the probabilities that he picks any raisin $$$i$$$ over any other raisin $$$j$$$, help him determine the probabilities of each raisin being the last one left!

Grape Juice Country is one of the world's great destinations, especially for lovers of wine grape juice, fantastic food, and beautiful views. However, the $$$N$$$ ($$$1 \leq N \leq 1000$$$) vineyards of the country (conveniently numbered from $$$1$$$ to $$$N$$$) have recently been getting ransacked by thieves! The government has decided to hire Red (Grape) and Green (Grape) armed guards to patrol the $$$M$$$ ($$$1 \leq M \leq 1000$$$) directed roads (conveniently numbered from $$$1$$$ to $$$M$$$) connecting the vineyards. Each guard is stationed at a vineyard, but Red and Green guards perform different duties. While Red Guards protect all roads that are directed out of the vineyard they are stationed at, Green Guards protect all roads that are directed into the vineyard they are stationed at. A road is considered "safe" if at least one guard of either type is protecting it. The loss of stolen goods avoided by keeping road $$$i$$$ safe is $$$s_i$$$. Both types of guards are obviously not free to hire, with Red Guards and Green Guards costing $$$r_i$$$ and $$$g_i$$$, respectively, to station at vineyard $$$i$$$. The government would like to maximize the value of saved goods minus the cost of hiring guards to protect roads. Can you help as their (definitely not hungover) domestic affairs intern?

Farmers all around the world have been freaking out over an all new brand of fertilizer, which claims to exponentially grow your grapes!

According to the advertisements, applying a fertilizer with growth factor $$$f$$$ to a grapevine causes it to immediately grow $$$f$$$ grapes, and wither directly afterwards.

You aren't very convinced that the fertilizer works that well, but the only thing you hate more than false advertising is manual labor. Clearly, the only sensible thing to do is to test the fertilizer by using your programmable army of robot farmers to apply the fertilizer, harvest the grapes, and replant them over and over.

You have sectioned off $$$n$$$ fields for the tests you plan on running, with the $$$i$$$th field initially having $$$x_i$$$ grapevines.

To test the fertilizers, you have settled on the following procedure:

1. For every field $$$i$$$ where $$$l \leq i \leq r$$$, the robots apply a fertilizer with growth factor $$$f$$$ to every grapevine.
2. The robots harvest the grapes and replant all of them, so that each grape sprouts into a new grapevine.
3. The robots manually plant $$$g$$$ extra grapes, to make sure that there is always something growing in the field (in case the fertilizer didn't work).
4. For consistency, steps 1 through 3 are repeated $$$t$$$ times.

However, all of this testing would be pointless without some kind of data measurement, so you'll also sometimes have the robots to count the number of grapevines currently growing in a specific field.

These tests will take quite a while to run, but it's gotten you thinking: if all the fertilizers work exactly as advertised, what would the measurements look like?