Because most students find the instructor intimidating1, 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 2 and plays soft folk or indie music 3. Moreover, he often has candy stocked in the R2D2 and BB8 containers on his desk 4.

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 favorites5, he has decided to give each student a rating6 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.
``````

Programming Challenges¶

This is based on the 135. Candy problem on LeetCode.

Algorithmic Complexity¶

For each input test case, your solution should have the following targets:

 Time Complexity `O(N)` where `N` is the number of ratings. Space Complexity `O(N)` where `N` is the number of ratings.

Your solution may be below the targets, but it should not exceed them.

Submission¶

``````\$ 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 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}
``````

Pull Request¶

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 05 TA List.

1. Very weird.

3. Thank you based `lychee`
4. Despite what `bobbit` says, I don't have favorites.