Arnold, in his many roles, has opened up an ice pop factory! He makes ice pops by creating a big batch of fresh fruit slurry, freezing it, and then slicing it into individual servings using the ice choppa (pronounced "chaw-pah".)
However, he is worried that the ice blocks will melt before getting to the choppa! In particular, different flavors of ice pops will take a different amount of time to melt, so he needs to prioritize the ice blocks that will melt first.
Given a list of flavors and the time each flavored ice block takes to melt, output in what order Arnold should send the ice blocks to the choppa!
The first line contains a single integer $$$N\ (1 \le N \le 10^5)$$$, denoting the number of flavored ice blocks.
The next $$$N$$$ lines contain an integer $$$a_i$$$ and a word $$$s_i$$$, separated by a space. The word $$$s_i$$$ denotes the flavor of the $$$i$$$th ice block, and the integer denotes how many minutes it will take for the $$$i$$$th ice block to melt $$$(1 \le a_i \le 10^9, N \leq \sum_{i=1}^N|s_i| \leq 2 \cdot 10^6)$$$.
It is guaranteed that all flavors will be distinct, and all times taken to melt will be distinct.
Print out a single line with the flavors of the ice blocks, ordered by time taken to melt.
4 3 Pineapple 4 Grape 19 Strawberry 12 Lime
Pineapple Grape Lime Strawberry
In MilkLand, the market value of a company, heat index, and UV index all go into the sales of ice cream. According to the MLSE (MilkLand Stock Exchange), these three values are modeled by the polynomial functions $$$F_1, F_2, F_3, G,$$$ and $$$H$$$ which are functions of the time $$$x$$$. The biorhythmic status of ice cream at a particular hour is defined to be the sum of these three values.
Trader Yoneda would like to know an ice cream company's biorhythmic status at a particular hour to determine how well it is doing. In MilkLand, there are 3 companies that dominate the ice cream market. The residual effort that a company is making is defined to be the average of the biorhythmic status of all the companies subtracted from the individual companies' biorhythmic status at a particular hour. For each company, please print "company $$$i$$$ not doing well" if it has negative residual, otherwise print "company $$$i$$$ doing well" if it has 0 or positive residual $$$(1 \leq i \leq 3)$$$.
The first line contains an array of coefficients $$$a_{13}\:a_{12} \:a_{11}\:a_{10}$$$ for integers $$$-10^5 \leq a_{1i} \leq 10^5$$$ representing the function $$$F_1(x) = a_{13}x^3+a_{12}x^2+a_{11}x+a_{10}$$$ for the market value of company 1.
The second line contains an array of coefficients $$$a_{23}\:a_{22}\: a_{21}\: a_{20}$$$ for integers $$$-10^5 \leq a_{2i} \leq 10^5$$$ representing the function $$$F_2(x) = a_{23}x^3+a_{22}x^2+a_{21}x+a_{20}$$$ for the market value of company 2.
The third line contains an array of coefficients $$$a_{33}\: a_{32}\: a_{31}\: a_{30}$$$ for integers $$$-10^5 \leq a_{3i} \leq 10^5$$$ representing the function $$$F_3(x) = a_{33}x^3+a_{32}x^2+a_{31}x+a_{30}$$$ for the market value of company 3.
The fourth line has the array of coefficients $$$b_3\: b_2\: b_1\: b_0$$$ for integers $$$-10^5 \leq b_i \leq 10^5$$$ denoting the function for the UV index $$$G(x) = b_3x^3+b_2x^2+b_1x+b_0$$$.
The fifth line has the array of coefficients $$$c_3\: c_2\: c_1\: c_0$$$ for integers $$$-10^5 \leq c_i \leq 10^5$$$ denoting the function for the heat index $$$H(x) = c_3x^3+c_2x^2+c_1x+c_0$$$.
The last line gives a particular hour $$$d$$$ for some integer $$$0 \leq d \leq 10^5$$$.
It is guaranteed that no biorhythmic value will have an absolute value greater than $$$10^9$$$.
Please print 3 separate lines, one per company.
For each line i $$$(1\leq i \leq 3)$$$, print "company i not doing well" if the company has a negative residual at hour $$$d$$$, else "company i doing well" if it has 0 or positive residual.
1 -18 99 -162 1 -22 119 -98 1 -18 104 -192 1 0 11 -6 1 -12 44 -48 5
company 1 not doing well company 2 doing well company 3 not doing well
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:
- Grass, Grass, Motor-Oil, Bone-Dust
- Grass, Licorice, Motor-Oil, Bone-Dust. Note that this is the same as Licorice, Grass, Motor-Oil, Bone-Dust.
- Licorice, Licorice, Motor-Oil, Bone-Dust
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:
- What is the maximum profit you can guarantee? Answers within $$$10^{-9}$$$ of the judge answer will be counted as correct.
- How many ways can you maximize the number of customers and guaranteed profit at the same time? Print this number mod $$$10^9+7$$$. Two ways are considered different if some customer gets a different cone. There is one way to make zero profit for zero customers (by doing nothing).
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