Mock CCC '24 Contest 1 S4 - Tommy's Lemonade Stand

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Tommy's passion for lemons led him to embark on a delightful venture – running a lemonade stand! Driven by his desire to create not just a refreshing beverage but also an economically savvy concoction, Tommy meticulously crafts a collection of N lemonade recipes. Each recipe is a carefully balanced blend of lemons, sugar, and mint, contributing to both the overall cost and flavour of the lemonade.

Tommy's curiosity has now turned to understanding the intricate relationship between the cost of ingredients and the flavour ratings of his lemonade recipes. The i^{th} recipe is characterized by three constants – L_i, S_i, and M_i – that influence how the flavour ratings evolve after adding x mL of water. Specifically, the flavour ratings can be calculated as -L_ix^2 + S_ix - M_i. Additionally, Tommy can add any amount of water he wants to each recipe, and he will incur a cost of one dollar for every millilitre of water added. Since Tommy is not a wizard, he cannot add a negative amount of water.

Given Tommy's financial constraints, he finds himself in a situation where he can only afford a lemonade stand capable of supporting him to produce lemonade with up to K recipes. Despite the financial challenges, Tommy is determined to ensure that his lemonade stand exudes diversity and uniqueness. Therefore, with careful consideration, he aims to select exactly K recipes that offer a varied and appealing range of flavours to attract a broad customer base.

Tommy, with a keen eye on maximizing his lemonade stand's profit, has defined profitability as the ratio of the sum of flavour ratings to the sum of costs. In his quest for the most sought-after lemonade stand in town, Tommy seeks your expertise to determine the maximum possible profitability. Your task is to assist Tommy in selecting a subset of size K from the N lemonade recipes that will result in the highest achievable profitability.

Input Specification

The first line of input contains two space-separated integers, N and K.

The following N lines of input each contain three space-separated integers, L_i, S_i, and M_i.

The following table shows how the available 15 marks are distributed.

Marks AwardedNKL_iS_iM_i
3 marks3 \leq N \leq 201 \leq K \leq N1 \leq L_i \leq 10^41 \leq S_i \leq 10^41 \leq M_i \leq 10^4
12 marks3 \leq N \leq 10^51 \leq K \leq N1 \leq L_i \leq 10^41 \leq S_i \leq 10^41 \leq M_i \leq 10^4

Output Specification

Output the highest achievable profitability of K selected recipes.

Your answer will be considered correct if it is within an absolute or relative error of 10^{-9}.

Sample Input

5 3
1 1 1
3 2 4
4 6 7
6 4 10
4 7 6

Sample Output


Explanation for Sample

Tommy is dealing with five lemonade recipes, and he can afford to choose three recipes for his stand. The recipe 1, 2, and 5 have respective flavor rating of -1(\frac{3\sqrt{233}-11}{19})^2 + 1(\frac{3\sqrt{233}-11}{19}) - 1, -3(\frac{2\sqrt{233}-1}{38})^2 + 2(\frac{2\sqrt{233}-1}{38}) - 4, and -4(\frac{3\sqrt{233}+46}{76})^2 + 7(\frac{3\sqrt{233}+46}{76}) - 6. The profitability is calculated by dividing the sum of flavour ratings by the sum of costs. After thorough evaluation, the highest achievable profitability is \frac{41-6\sqrt{233}}{19} which is approximately -2.662422376, making this combination of recipes the most lucrative for Tommy's lemonade stand.


There are no comments at the moment.