Candy time
Halloween is a festival where children visit homes in their neighborhood and collect candies from each home.
● Parents want to give children an upper bound on the number of candies they can collect.
● Children want as many candies as they can get.
● We know in advance exactly how many candies each homeowner gives to the children.
● A child has to take all the candies given at a home
● They can’t throw away or eat any candy on the way.
● Children also have to stop at every home in the sequence of homes they are visiting. Write a program in C or C++ to find the best sequence of homes for children to visit with following input/Output. Input:
● First input is an integer, homes, that represents the maximum number of homes in the neighborhood.
● The next input is an integer, max representing the maximum number of candies that the child may collect.
● Next input will be integers, pieces, representing the number of Candies given at each home. Homes are numbered consecutively starting at 1. Output:
● If there is no way to select one or more consecutive homes where the sum of pieces of candy is less than max, then print “NO CANDIES”.
● Otherwise, for the sequence of homes that yield the largest number of candies (<=max) print the number of the first home visit, the number of the last home to visit, and sum of pieces of candy.
● If there is more than one such sequence of homes, select the one with the lowest numbered first home. Sample Input: Sample Output: 5 (No. of homes) First Home: 3 20 (Max no. of candies) Last Home: 5 3 (Candy from Home 1) Total Candies: 19 4 (Candy from Home 2) 2 (Candy from Home 3) 8 (Candy from Home 4) (2+8+9=19) 9 (Candy from Home 5)
0 Comments