Challenge 10: Candies

Because most students find the instructor intimidating¹, he has resorted to all sorts of crazy tricks in an attempt at being more inclusive and making his office a more welcoming place. For instance, to make sure CSE majors feel at home, he keeps the lights off in his office ² and plays soft folk or indie music ³. Moreover, he often has candy stocked in the R2D2 and BB8 containers on his desk ⁴.

Unfortunately, a problem has arisen: too many students are now showing up to his office and eating the candy. Because he wants to reward his favorites⁵, he has decided to give each student a rating⁶ and distributes candies to each student based on this number.

As a big believer in the important of Data Structures, he has visiting students line up in a queue and distributes the candy to the students such that the following constraints are met:

1. Every student gets at least one candy.

2. Every student whose rating is greater than their neighbors in the queue should receive more candy.

For example, suppose the following students were in the office hours queue:

Zephan, Mike, Emory

The instructor may rate the students as:

1, 0, 2

To meet the constraints above, this means he must at least give Zephan 2 candies, Mike 1 candies, and Emory 2 candies, for a total of 5 candies.

After devising this candy distribution scheme, the instructor has become distracted with Clash Royale and asks you to write the code to determine what is the minimum number of candies he needs to distribute given a queue of students and their corresponding ratings.

Input¶

You will be given a series of test inputs where each line consists of a queue of n students (where 1 <= n <= 1000) and their corresponding ratings (where 1 <= rating <= 20).

You should read and process each line of input until the end of the file.

Example Input¶

1 0 2
1 2 2
1 3 2 2 1

Output¶

For each queue of students and their ratings, output the minimum number of candies you need to distribute to the students to ensure that you meant the constraints above in the following format:

{Student Queue #}. You need {Minimum # of candies} candies.

Example Output¶

1. You need 5 candies.
2. You need 4 candies.
3. You need 7 candies.

Submission¶

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa22-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge10               # Create and checkout challenge10 branch

$ $EDITOR challenge10/program.cpp           # Edit your code

$ git add challenge10/program.cpp           # Stage your changes
$ git commit -m "challenge10: done"         # Commit your changes

$ git push -u origin challenge10            # Send changes to GitHub

To check your code, you can use the .scripts/check.py script or curl:

$ .scripts/check.py
Checking challenge10 program.cpp ...
  Result Success
    Time 0.06
   Score 6.00 / 6.00

$ curl -F source=@challenge10/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa22/challenge10
{"result": "Success", "score": 6, "time": 0.06372570991516113, "value": 6, "status": 0}