Vargas has opened a new ice cream stand on the shores of New Atlantis, for all the tourists to enjoy. For the small price of 14.99 spuds, customers get two scoops of ice cream (which may be different flavors), their choice of a drizzle, and their choice of a topping.
Vargas has seen many interesting combinations of desserts, and is curious to know – given a particular day's selection of flavors, drizzles, and toppings, how many possible (distinct) ice cream cones could be served?
Note that the order of the scoops does not matter.
The first line contains a list of space-separated words, representing the flavors of ice cream. There will be at least 1 and at most 100 flavors.
The second line contains another list of space-separated words, representing the available drizzles. There will be at least 1 and at most 100 drizzles.
The third line contains yet another list of space-separated words, representing the available toppings. There will be at least 1 and at most 100 toppings.
All flavors, drizzles, and toppings will be distinct.
Output a single integer, the number of possible desserts. Note that customers must purchase exactly two scoops (which may or may not be the same flavor), one drizzle, and one topping.
The order of the scoops does not matter.
Grass Licorice Motor-Oil Bone-Dust
3
There are three possible ice cream cones in this first example. They are:
In betrayal of the ice cream cone tradition, Luogu is enjoying ice cream lasagna, consisting of a total of $$$n$$$ layers of ice cream, split by $$$n+1$$$ layers of crackers.
For the $$$i$$$th layer of ice cream, there are $$$c_i$$$ pieces of candies, each being either red or green, sprinkled in a certain order determined by Luogu's mysterious ways.
Luogu has a few rules he sets for himself when he enjoys his ice cream lasagna:
- The ice cream is always eaten top to down, i.e., from the $$$1$$$st layer to the $$$n$$$th layer,
- One layer of ice cream must be finished before eating the next layer,
- He will record the candies found in each layer in his mysterious order, that is, he will lift the $$$1$$$st layer of cracker, record the candies he see, put it back, lift the $$$2$$$nd layer of cracker, and so on until the candies observed from lifting the $$$n$$$th layer of cracker has been recorded.
Using the record, Luogu asks that you help him understand the uniformity of the dessert: specifically, the maximum amount of candies of the same color that he can eat consecutively (i.e., no skipping or reordering the layers of lasagna) as he enjoys his ice cream lasagna while adhering to the rules.
The first line consists of an integer, $$$n\ (1 \leq n \leq 2 \cdot 10^5)$$$, denoting the number of layers of ice cream found in the lasagna.
The next $$$n$$$ lines record details of the candies cound in the $$$i$$$th layer. Each line consists of a string, consisting of either 'R' or 'G', denoting red or green candy, respectively. It is guaranteed $$$c_i \geq 1$$$ for $$$1\leq i \leq n$$$, and $$$\sum_{i=1}^{n} c_i \leq 2\cdot 10^5$$$.
A single integer denoting the uniformity of the dessert.
4 RGR GGGG GR RRR
6
5 RGGGGGGG GGGRGRGRGRG GRGRGRGRGRGRGRGRGRGR RRRRRRRRR G
19
Cassidy runs an unorthodox ice cream shop! Each day before the store opens she lines up all of her food coloring dyes of various colors and shades in order to paint each waffle cone with a unique design. In particular, Cassidy has exactly $$$N$$$ dyes of various colors. Each of the dyes has a beauty rating assigned by the regular customers, with the beauty rating of the $$$i$$$th color represented by a positive integer $$$b_i$$$.
Today Cassidy is feeling especially creative. She would like to paint one of the cones in the most beautiful way possible! The beauty score of a cone is calculated as the sum of the beauty ratings of the dyes used to paint it. Moreover, Cassidy cannot use two dyes to paint the cones if they are directly adjacent to each other in the lineup of colors.
Based on the ordering of her dyes and their respective beauty ratings, can you help Cassidy calculate the most beautiful (in terms of beauty score) cone that she can paint?
The input will begin with a line containing a single integer, $$$N\ (1 \leq N \leq 10^5)$$$, representing the number of dyes that Cassidy has to paint with in the ice cream shop. The second and final line will contain exactly $$$N$$$ space-separated positive integers, $$$b_i\ (1 \leq b_i \leq 10^9)$$$, the $$$i$$$th of which represents the beauty rating of the $$$i$$$th dye in Cassidy's lineup of dyes.
The output should consist of a single line containing a single integer representing the highest beauty score Cassidy can attain for a single cone. Note again that the only restriction on the dyes Cassidy can use is that they may not be adjacent in her lineup.
5 5 10 9 10 7
21
Bing is icecreamtarian (meaning he only eats ice cream). He needs to combine some ingredients to make his favorite ice cream flavor. He can buy each ingredient at a certain price, but he can also choose to make certain ingredients from other ingredients (which might be cheaper). Everytime Bing uses an ingredient to make another ingredient, it is consumed. Please help Bing determine the cheapest cost to make his favorite ice cream flavor.
The first line of input contains $$$N$$$ and $$$M$$$: the number of ingredients needed to make the ice cream flavor and the total number of ingredients available in the store. $$$(1 \leq N \leq M \leq 100,000)$$$
The next line contains $$$N$$$ strings separated by spaces: the names of the ingredients needed to make his favorite ice cream flavor.
Each of the next $$$M$$$ lines will be $$$s_i$$$, $$$p_i$$$, $$$g_i$$$, $$$[\text{ingredient names}]$$$: a string denoting name of the $$$i^{th}$$$ ingredient, an integer denoting the price of the $$$i^{th}$$$ ingredient, an integer denoting the number of ingredients needed to make this ingredient, followed by $$$g_i$$$ space-separated strings, the names of the ingredients needed to make this ingredient. The total character length of all $$$g_i$$$ strings across all ingredients will not exceed $$$3 \times 10^5$$$. If $$$g_i = 0$$$, the ingredient must be purchased. $$$(0 \leq p_i \leq 10^9, 0 \leq g_i \leq M)$$$
$$$\textbf{Note}$$$: it is guaranteed that all ingredients can be purchased unlimited times and have unique, single-word names consisting of alphanumeric characters.
$$$\textbf{Also Note}$$$: it is guaranteed that ingredients will not be able to make themselves either directly or their component ingredients.
Output a single integer, the minimum cost needed for Bing to make his favorite ice cream flavor (this value may not be able to fit within a standard 32-bit signed integer).
3 5 milk vanillaExtract cream milk 10 0 vanillaExtract 5 1 sugar cream 30 2 sugar milk butter 5 1 milk sugar 6 0
31
1 6 flavorX2 flavorX2 100 4 skittles milk salt cream cream 10 2 milk sugar skittles 10 0 milk 5 0 salt 10 0 sugar 4 0
34
You and your friend Greg are running an ice cream stand at a local fair.
Now, you know chocolate-mint-flavored ice cream is the best flavor. Since it is the best flavor, there are $$$N\ (1\leq N\leq 10^5)$$$ customers lined up outside your stand who only want chocolate-mint ice cream, and the $$$i$$$-th customer will offer you $$$r_i\ (0\leq r_i\leq 10^9)$$$ dollars for a single cone of chocolate-mint ice cream.
While on your break, Greg found $$$M\ (1\leq M\leq 10^5)$$$ mystery-flavored ice cream cones on the ground. Greg, being greedy, decides to pick up all the ice cream cones, and offers to sell you the $$$i$$$-th ice cream cone for $$$c_i\ (0\leq c_i\leq 10^9)$$$ dollars.
Now, you also have a friend Alex, who absolutely loves gambling, and will bet any amount that any ice cream cone that Greg picked up is chocolate-mint or not.
However, you have just run out of chocolate-mint ice cream, and so instead sell your customers a mystery-flavored ice cream cone: if the mystery flavor turns out to be chocolate-mint, then you profit $$$r_i\ (0\leq r_i\leq 10^9)$$$ dollars, otherwise, you profit $$$0$$$.
Being the talented owner you are, you want to find the maximum profit you can guarantee and the number of ways you can maximize both the number of customers and profit at the same time.
The first line contains two integers, $$$N$$$ and $$$M$$$.
The second line will contain $$$N$$$ integers, where the $$$i$$$-th integer is $$$r_i\ (1\leq r_i\leq 10^9)$$$, the amount that you will profit if you're able to sell a cone to the $$$i$$$-th customer.
The third line will contain $$$M$$$ integers, where the $$$i$$$-th integer is $$$c_i\ (0\leq c_i\leq 10^9)$$$, the cost that you can buy the $$$i$$$-th ice cream cone for.
Print the following separated by a space:
2 2 100 100 20 20
60 2
3 3 1 2 3 0 0 0
3 6
2 1 100 100 1
49 2
You are the proud owner of an ice cream cone factory, where ice cream cones are produced by pouring batter into cone molds. The cone-producing process can be modeled as follows:
1. Cone molds are placed at integer points along the X-axis.
2. For each integer X-coordinate, there exists a batter dispenser located at height $$$\infty$$$.
3. The batter dispensers are activated, dispensing batter in a downward stream and filling the cone mold beneath it if there is one.
Normally, this process works quite well, and you are able to fill all your cone molds regardless of where they are placed. However, due to some events beyond expectation, your factory only has enough power to activate exactly one dispenser!
To alleviate this problem, you have acquired $$$m$$$ batter spreaders. The $$$i$$$th spreader exists as a horizontal line segment [$$$l_i$$$, $$$r_i$$$] at height $$$h_i$$$. Whenever a stream of batter hits anywhere on the spreader, it will evenly distribute the flow to cover the entire length of the spreader.
Despite the setbacks you've encountered, you would still like to fill as many cone molds as you can. Given the locations of your cone molds and batter spreaders, what is the maximum number of molds you can fill by activating exactly one batter dispenser?
The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1\leq n\leq 10^5, 1\leq m\leq 10^5$$$) — the number of cone molds and the number of batter spreaders.
The second line of input contains $$$n$$$ distinct integers $$$p_1,\dots,p_n$$$ ($$$1\leq p_i\leq 10^6$$$), denoting a cone mold located at $$$(p_i, 0)$$$.
The next $$$m$$$ lines contain three integers $$$l_i, r_i, h_i$$$ ($$$1\leq l_i \leq r_i,\leq 10^6, 1\leq h_i\leq 10^9$$$, $$$l_i \leq r_i$$$), denoting a batter spreader covering the interval $$$[l_i,r_i]$$$ located at height $$$h_i$$$. It is guaranteed that no two spreaders intersect.
Output a single integer — the maximum number of cone molds you can fill by activating exactly one batter dispenser.
5 2 1 2 3 4 5 1 2 1 3 5 2
3
2 2 1 1000000 1 500000 1 500000 1000000 2
2
Bob loves ice cream. In fact, he loves ice cream so much that he often dreams about it! In a recent dream, Bob was standing at the origin of a two-dimensional plane made of ice cream, as one would typically do. However, this wasn't an ordinary two-dimensional universe, since there were $$$N$$$ sprinkles scattered around the plane ($$$1 \leq N \leq 2*10^5$$$). These sprinkles come in two colors: red and blue. Bob loves the color red and despises the color blue, so he will do anything in order to not eat a blue sprinkle. The sprinkles are also magical, so they cannot move under any condition. He also has the capability to construct an ice cream cone of infinite size, but he is too lazy to move from the origin, so the vertex of the ice cream cone must be located at the origin. In Bob's two-dimensional world, ice cream cones are equivalent to geometric sectors. They can be defined by their radius, along with two angles, as seen in the image below:
Each sprinkle is located at integer coordinates $$$(x_i, y_i), (|x_i| \leq 10^9, 1 \leq y_i \leq 10^9)$$$. Note that all $$$y_i$$$ must be positive. Every sprinkle is either red or blue. Sprinkles have negligible width, and no two sprinkles have the same position. A sprinkle is considered to be inside a cone if it is inside or on the boundary of the sector representing the cone. Also, negative y coordinates typically have many blue sprinkles, so Bob will not make a cone which covers any point below the x-axis.
Bob wants to capture as many red sprinkles as he can inside of a single ice cream cone, without capturing any blue sprinkles. Help Bob determine the maximum number of red sprinkles he can collect!
The first line of input will contain $$$N$$$, the number of sprinkles. ($$$1 \leq N \leq 2 \cdot 10^5$$$) The next line will contain a string $$$C$$$ of length $$$N$$$, where $$$C_i \in \{'r', 'b'\}$$$, denotes the color of the $$$i$$$th sprinkle. The $$$i$$$th of the next $$$N$$$ lines will each consist of two integers $$$x_i$$$ and $$$y_i$$$, representing the position of the $$$i$$$th sprinkle. ($$$|x_i| \leq 10^9, 1 \leq y_i \leq 10^9$$$) Furthermore, it is guaranteed that any pair of sprinkles will differ in either their x or y coordinates.
Output a single integer, representing the maximum number of red sprinkles which Bob can capture, without capturing any blue sprinkles.
7 rrbrrbr 1 1 2 3 1 4 3 1 4 2 4 3 4 4
4
In this case, Bob can capture 4 red sprinkles without capturing any blue ones, shown by the yellow sector in the image. It can be shown that there is no way to collect all 5 red sprinkles in this case.
Patrick is trying to create a magical starfruit ice cream with his special blend of magical starfruit-flavored milk. Making starfruit ice cream is a very delicate process, which means he must follow a very specific procedure. Patrick has $$$n$$$ ($$$4 \leq n \leq 2000$$$) pints of starfruit milk. He is pouring them into a special square-grid-shaped bowl of size $$$n$$$ by $$$n$$$ before he freezes the milk to turn into ice cream. However, he can't just pour the milk into a random location. He must follow a specific set of rules to avoid magical disaster. Foremost, he must pour exactly one pint of milk into a grid location, no more, no less. Additionally, magical starfruit milk doesn't spread in a typical fashion. Starfruit milk poured at location will spread in 8 directions (like a star) until it hits the edge of the bowl: the four cardinal directions (up, down, left, right) and the four ordinal directions (northwest, northeast, southeast, southwest). Once again, to avoid magical disaster, starfruit milk cannot spread into another cell where milk was poured into. Finally, for larger bowls, there are $$$k\ \left(0 \leq k \leq \lfloor\frac{n}{400}\rfloor\right)$$$ specific locations that Patrick cannot pour milk into in order to appease the starfruit gods. However, it is fine if starfruit milk spreads into these locations. Help Patrick figure out which $$$n$$$ locations in the bowl he should pour the starfruit milk in order to avoid magical disaster and appease the gods.
The first line will contain an integer $$$n$$$ ($$$4 \leq n \leq 2000$$$) specifying the pints of starfruit milk and an integer $$$k\ \left(0 \leq k \leq \lfloor\frac{n}{400}\rfloor\right)$$$ specifying the number of grid locations that Patrick must avoid pouring milk into. The next $$$k$$$ lines will contain two integers, $$$r$$$ and $$$c$$$, ($$$1\leq r,c \leq n$$$) which represent a location $$$(r,c)$$$ that Patrick cannot pour milk into.
Print $$$n$$$ lines where each line has two space separated integers: $$$r$$$ and $$$c$$$ which represent the row and column that Patrick should pour milk into. Note that there are multiple solutions, but any valid solution will pass.
4 0
2 1 4 2 1 3 3 4
8 0
6 1 3 2 1 3 8 4 5 5 2 6 4 7 7 8
The following illustration shows one possible solution to sample test 1. Note how none of the milk spreads into another cell where milk was poured into.