Assignment 3 Divide-and-conquer design and development

Requirements
This third assignment lets you get familiar with greedy and divide-and-conquer design and development. There are two algorithms/programs required. It is worth 5% of your total course marks. Please try and test with your own generated input cases before submitting to the automated marker.
Task 1: Diet Helper
One of the lecturers is going on a carrot and celery diet. Depending on the season a carrot stick and a celery stick can be consumed in m and n seconds, respectively. Furthermore, this diet has an allocated eating period of t seconds for a given day to consume food. We want to know the maximum number of sticks that can be consumed in t seconds. Your lecturer doesn’t want to waste time not eating, so prefers to have the combination of carrot and celery sticks take up as much of the t seconds allocated. He is also not allowed to eat part of a food item (once a stick has been bitten into he must have enough time to finish it).
Since the values of m,n and t change daily we want a program to help him decide the maximum number of sticks that could be eaten, where we first minimize the number of seconds spent not eating. Your input will be a sequence of daily diet triples 1 ≤ m,n,t ≤ 1000000, given on a line separated by one space, and terminated by a line containing m = n = t = 0, which isn’t processed.
Sample Input:
3 2 10 5 41 112 253 234 1919 0 0 0
For each diet triple (m,n,t), you should output the maximum number of carrot and celery sticks that can be consumed provided that the maximum amount of time t0 ≤ t is used eating. Also on the same line print the minimum time t−t0 that is wasted to get this count (separated by one space). Sample Output for program name diet.ext
5 0 8 0 8 9
1
Task 2: k-selection
You have been asked by the obnoxious and impatient statistician to write a program that given a data set (an array of 32-bit integers of size n ≤ 108) and an integer k in the range 1..n will output the k-th smallest element. If a long delay occurs when the program is running, this person will start yelling serious abuse at you (but won’t destroy your career outright). He is just as likely to give you data that is already sorted as data that is completely random-looking, and there may be many duplicate entries in the data.
Input format: The first line gives the value of n followed by the value of k. The next n lines give the integers in the array, one per line. This repeats and a case where n = 0 terminates the file.
Sample Input:
2 2 1 3 5 1 5 8 4 12 10 5 3 7 1 6 8 9 0 0
Sample Output for program name select.ext
Data set 1: element 2 is 3 Data set 2: element 1 is 4 Data set 3: element 3 is 7
Submission Procedure
For this assignment, there are two marks awarded for Task 1 and three marks awarded for Task 2, where Task2 has an easy test case (one mark) and harder test case (two marks).