SEARCC - CSI Computer Programming Competition - Sample Questions

Software Competition Sample Questions

PROBLEM-1
Jack is a man on a mission. He carries a pocket full of change consisting of 5, 10, 20 and 50 paise coins, and whenever he has to pay any amount, he will choose his change so that he uses the minimum number of coins possible. This is because he feels that it is his life’s destiny to carry a lot of change everywhere and would like to spend as few of them as possible.
Given 5, 10, 20 and 50 paise coins in his pocket, your task is to write a program to work out the number of coins of each denomination and the total number of coins used, such that the total number is the minimum that he can use. Note that Jack won’t be able to pay any arbitrary amount of money. For example, if something costs Rs 2.35 and he does not have enough change, he won’t be able to pay this amount.

Input
The input file is named in1.dat. The first line of the input file contains N (N<=10), determines the number of inputs. The second line consists of a single line of numbers, where the first four represent the number of coins with denominations of 5, 10, 20 and 50 paise coins respectively, and the fifth number is an integer representing the amount that Jack has to pay, in paise.

Note: The number that represent the denomination of any type would be smaller than 1, 000, 000 while the amount that is to be paid is smaller than 100, 000, 000 paise.
Example 1: If he has two coins of each type ( 5,10,20,50) and he needs to pay 35 paise, the input would be: 2 2 2 2 35
Example 2: If he has three 5-paise coins, two 10-paise coins and four 50-paise coins, and has to pay Rs 5.35 (or 535 paise), then the input would be: 3 2 0 4 535

Output
The output file is named out1.dat. Your program should output the number of each type of coin that Jack should spend, as well as the total number of coins. Again this total should be a minimum so that Jack can retain as many coins as possible. And your program should output “−1” to indicate if he doesn’t have enough to pay up this amount.

Sample Input
2
2 2 2 2 35
3 2 0 4 535

Sample Output
1 1 1 0 3
-1

PROBLEM-2
You are provided with four sets of integers. Your task consists of selecting one integer from each set, such that their sum is 0. You can assume that exactly one such selection exists.

Input
The input file is named in2.dat. The first line of the input file contains N (N<=10), the second line of input file contains four numbers, a, b, c, and d, separated by a space character, indicating the number of elements in each of the four sets. Each of these numbers is a positive integer 1 ≤ a, b, c, d ≤ 500. The following a + b + c + d lines contain the elements, each not smaller than −10000 and not larger than 10000. The elements of the first set are listed first, followed by the elements of the second set, etc.

Output
The output file is named out2.dat.The output file consists of the four integers, separated by a space character. The numbers must appear in the order in which they are listed in the input file.

Sample Input
1
3 2 4 2
5
17
-8
-13
19
6
-9
10
0
-14
7

Sample Output
17 -13 10 -14

PROBLEM-3
The coach of Sumista, Regional swimmer for India, is concerned about her Butterfly stroke. He records her daily timing in milliseconds (a millisecond is one thousand of a second) and devises a scheme whereby each time she achieves a timing that is lower than the previous day’s timing by at least a certain number of milliseconds, he will reward her with a gift. Given a list of daily timings, determine how many gifts Sumista would have received.

Input
The input file is named in3.dat. The first line contains 2 integers n and k, where n (3 ≤ n ≤ 100) is the number of days, and k (0 < k ≤ 100,000) the desired improvement (in milliseconds). Whenever Sumista’s timing reduces by at least k milliseconds over the previous day’s timing, she will receive a gift from her coach. The first line is then followed by n lines where each line contains a single integer t (0 < t ≤ 100,000) which is Sumista’s daily timing in milliseconds. The n timing records are listed in chronological order.

Output
The output file is named out2.dat. The output file consists of a single integer that indicates the number of gifts Sumista would have received.

Sample Input
6 100
59420
59410
59310
59290
59470
59350

Sample Output
2

PROBLEM – 4
The King of Pallava has a horse which is kept in one of the royal ranches (fields) to graze.
Every time the King wishes to ride his horse, he will order his servants to fetch the horse. However, the King is an impatient man and if his servants take too long to fetch the horse, he will grow angry and punish the servants severely. Also, as the horse like a certain food and if it passes a ranch with those food inside, it will refuse to move for a certain amount of time and hence it will add to the time the servant needs to take to bring the horse to the King.

All the 10 King’s royal ranches are arranged in a single row as shown below. The entrance to the ranches is at the left hand side indicated as A. Assume that it takes 1 minute to move from the entrance to the first ranch and 1 minute from one ranch to the next. If the food that the horse likes in a ranch, the horse will stay there for 2 minutes.
A servant is extremely fearful about the punishment and he knows that you are a brilliant
programmer. So he asks you to write a program to help him arrange his duties such that
he will only be on duty when the horse is kept in a ranch such that no matter where the horse is, the servant will always be able to fetch the horse in time.

Input
The input file is named in4.dat. The first line of the input file contains N (N<=10), the second line of input file contains T, time in minutes before the King grows impatient. Each character in the third line indicates what is in each ranch. “X” indicates the food that the horse likes is in that ranch, “O” denotes an empty ranch and “H” indicates the ranch where the horse is found. The servant must start from the entrance (A) of the ranch and fetch the horse within T minutes. That is, he must be able to reach the ranch where the horse is found and be back at A using no more than T minutes. Note that there may be more than one “X” in the sequence.

Output
The output file is named out4.dat. The output file consists of “YES – Total time is t” if the servant should arrange his duty on that day or “NO – Total time is t” if he should not. “YES” and “NO” must be all uppercase. t is the total time needed by the servant starting at the entrance, goes to the ranch where the horse is found and brings it back to the entrance.

Sample Input
3
10
OOOOHOOXXO
15
OOXXHOOXXX
11
OOOOOHXXXX

Sample Output
YES – Total time is 10
YES – Total time is 14
NO – Total time is 12

These sample questions are taken from http://www.searcc.org