Connection Status:
Competition Arena > CandyAddict

CandyAddict

SRM 629 · 2014-07-26 · by dreamoon

SRM 629 · 2014-07-26 · by dreamoon · Simple Math, Simulation
Class Name: CandyAddict
Return Type: long[]
Method Name: solve
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

Alice is a candy addict! She doesn't eat any food except for candy. More precisely, the only thing she eats on any day is one piece of candy in the evening.

Alice receives an allowance of x dollars every morning. One piece of candy costs y dollars. We will follow Alice for z days. The days will be numbered 1 through z. At the beginning of day 1, Alice has no money and no candies.

Each day looks as follows:

  1. In the morning, Alice receives her allowance.
  2. At noon, Alice checks whether she has some candies. If she still has some candies, she does nothing. If she has no candies, she uses her money to buy as many candies as she currently can.
  3. In the evening, Alice eats one candy.

For the given x, y, and z, we want to calculate the amount of money Alice has left at the end of day z. (Alice may also have some candies at the end of day z. We are not interested in those.)

You are given multiple queries (x,y,z) and you have to process all of them. More precisely, you are given int[]s X, Y, and Z, each with Q elements. For each valid i, you must answer the query with x=X[i], y=Y[i], and z=Z[i]. Return a long[] with Q elements: the answers to the queries, in the same order.

Constraints

  • The number of queries will be between 1 and 100, inclusive.
  • X, Y, Z will contain same number of elements.
  • Each element of X, Y and Z will be between 1 and 1,000,000,000, inclusive.
  • For each valid i, Y[i] <= X[i].
Examples
0)
{5}
{3}
{3}
Returns: {6 }

There is only one query. In this query, Alice receives 5 dollars each day, a candy costs 3 dollars, and there are 3 days. The entire process will look as follows: Day 1 morning: Alice receives 5 dollars. She now has 5 dollars and 0 candies. Day 1 noon: Alice has no candies, so she buys one. She now has 2 dollars and 1 candy. Day 1 evening: Alice eats a candy. She now has 2 dollars and 0 candies. Day 2 morning: Alice receives 5 dollars. She now has 7 dollars and 0 candies. Day 2 noon: Alice has no candies, so she buys two. She now has 1 dollar and 2 candies. Day 2 evening: Alice eats a candy. She now has 1 dollar and 1 candy. Day 3 morning: Alice receives 5 dollars. She now has 6 dollars and 1 candy. Day 3 noon: Alice still has some candies, so she does nothing. She still has 6 dollars and 1 candy. Day 3 evening: Alice eats a candy. She now has 6 dollars and 0 candies. Hence, at the end of day 3 Alice will have 6 dollars.

1)
{5,5,5,5,5}
{3,3,3,3,3}
{1,2,3,4,5}
Returns: {2, 1, 6, 2, 7 }
2)
{1000000000,1000000000,1000000000,1000000000,1000000000}
{1,2,3,999999998,999999999}
{342568368,560496730,586947396,386937583,609483745}
Returns: {342568367000000000, 60496729000000000, 253614062000000001, 773875166, 609483745 }
3)
{1,2,3}
{1,2,3}
{1,2,3}
Returns: {0, 0, 0 }
4)
{1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}
{1,999999999,2,999999998,3,999999997,4,999999996,5,1000000000}
{1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}
Returns: {999999999000000000, 1000000000, 499999999000000000, 1000000002, 666666666000000001, 2000000003, 749999999000000000, 2000000008, 799999999000000000, 0 }

Submissions are judged against all 31 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CandyAddict with a public method vector<long long> solve(vector<int> X, vector<int> Y, vector<int> Z) · 31 test cases · 2 s / 256 MB per case

Submitting as anonymous