Sample Questions from the 2013 Contest

Matching Special Characters

Problem Description

In this problem you must scan a line of characters and determine if each of three special characters occur in pairs. The special characters are parenthesis, brackets, and braces. These are ( ), [ ], and { }. The order is not important. Any other characters should be ignored.

Detailed Requirements

• Read a line of characters. This line will not exceed 80 characters. You must allow the user to enter all the characters at one time. You cannot require the user to hit enter after each character.
• Determine if there is one left parenthesis for each right parenthesis.
• Determine if there is one left bracket for each right bracket.
• Determine if there is one left brace for each right brace.
• Ignore any other character.
• Display "All special characters have a match" if each special character has a match. Display "Not all special characters have a match" if any special character does not have a match.
• The judges will enter additional test data not provided below to further test your application. You don't need to validate the input. The judges will only enter valid data.

Output

Display a single line indicating whether all special characters have a match for each test case. Format the output exactly as shown in the test data below.

Test Data

InputOutput
{)(} All special characters have a match.
}){( All special characters have a match.
{ae{)} Not all special characters have a match.
({{{asas[sad])}}dsas} All special characters have a match.
{tt}tt((t Not all special characters have a match.

A sample console interface is provided below. Your user interface is not being judged. Each set of data can be tested by rerunning the application.

Enter characters:
{)(}
All special characters have a match.

Figure 1

A sample graphical user interface is provided below. Your user interface is not being judged. Each set of data can be tested by rerunning the application.

Moving Averages

Problem Description

A moving average is often used to “smooth” a series of numbers to see if a trend exists. For example you could plot a series of stock prices taken daily for a year and see if there is a trend. Alternatively you could plot the moving average of those same stock prices. The moving averages should give a truer representation of the actual trend.

Create an application that will display the moving averages of a series of numbers. There will be n numbers in this series. The subset of numbers to average will be fixed at some value called s. When n = 10 and s = 4 we would want to calculate a moving average of 10 numbers 4 at a time.

Assume the numbers are 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10.
The moving averages would be 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, and 8.5.
These are calculated by averaging (1 + 2 + 3 + 4), then averaging (2 + 3 + 4 + 5), then averaging (3 + 4 + 5 + 6) and so on.

Detailed Requirements

1. Read a value for the number of items in the series. This will be a positive integer greater than 1 and less than 101.
2. Read a value for the subset size. This will be a positive integer. It will be less than the number of items in the series.
3. Read each number in the series. The numbers can be any floating point value – positive, negative, or zero. You must allow all the numbers to be entered at once. In other words, you cannot require the user to press enter after each number is entered. Separate each number by a space.
4. Calculate and display the moving averages. Separate each number by a space.
6. The judges will enter additional test data not provided below to further test your application. You don't need to validate the input. The judges will only enter valid data.

Output

Display a single line containing the moving averages as shown in the Output column of the Test Data section below.

Test Data

Numbers in SeriesSize of SubsetNumbers in SeriesOutput1
10 3 .5 1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5 9.5 1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5
3 2 10 20 30 15.0 25.0
8 4 1 2 3 4 5 6 7 8 2.5 3.5 4.5 5.5 6.5
11 6 10 20 30 40 50 60 10 20 30 40 50 35.0 35.0 35.0 35.0 35.0 35.0

1Your output may have additional decimal positions. Correct output will be judged only to the decimal precision shown in the sample output. Additional numbers of decimal output after that will not be considered incorrect.

A sample console interface is provided below. Your user interface is not being judged. Each set of data can be tested by rerunning the application.

Enter number in series:
10
Enter subset size:
3
Enter numbers:
.5 1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5 9.5

1.52.53.54.55.56.57.58.5

Figure 1

A sample graphical user interface is provided below. Your user interface is not being judged. Each set of data can be tested by rerunning the application.

Figure 2

Meal Deal

Problem Description

A group of self-employed business associates often travel together and don’t want to be bothered splitting their food bills at every meal. During the trip they take turns paying the daily food bills. For example John may pay all the bills on Monday, Jane all the bills on Tuesday, and so on. When they return they have to determine who owes money so they all end up spending the same amount for food. You have been asked to automate this process.

Detailed Requirements

1. Prompt for and read the number of travelers on a trip. This will be a positive integer greater than one ( > 1 ) and less than 100. (Sometimes a lot of people travel together!)
2. Read the amount each person paid for food. This will be a floating point number greater than zero. It will have no upper limit except the maximum value that can be stored. Enter all the amounts on a single line separated by one space.
3. Display the minimum amount of money that must change hands so that every traveler ends up paying the same amount. For example, assume four workers travel and have daily food bills of \$10, \$20, \$30, and \$40. This means traveler 1 must repay \$15 and traveler 2 must repay \$5 for a total that must be repaid of \$20. We don’t care who the money goes to or who the money comes from; only the total amount that must be collected which is \$20.
4. Display the output rounded to two decimal positions.
6. The judges will enter additional test data not provided below to further test your application. You don't need to validate the input. The judges will only enter valid data.

Output

Display a single numeric value representing the minimum amount that must change hands so that every traveler paid the same amount. The number of decimals in the output doesn’t need to be rounded.

Test Data

Number of TravelersDaily Food BillsOutput
4 10.00 20.00 30.00 40.00 20.00
3 10.00 20.00 30.00 10.00
5 1500.00 3.00 3.01 1500.01 255.34 1695.47
7 27.55 303.44 67.99 203.00 1998.00 234.66 3.50 1592.55
2 100.55 110.12 4.79

A sample console interface is provided below. Your user interface is not being judged. Each set of data can be tested by rerunning the application.

Enter the number of travelers:
5
Enter the daily meal costs:
1500.00 3.00 3.01 1500.01 255.34

1695.47

Figure 1

A sample graphical user interface is provided below. Your user interface is not being judged. Each set of data can be tested by rerunning the application.

Figure 2

Palindrome

Problem Description

A palindrome is a word that is the same forward as backward: “mom” and “bib” are examples. Positive integers can be palindromic. For example the numbers 3, 484, 12621, and 458854 are all palindromic. How many palindromic integers are there between x and y inclusive given that x will be > 0 and y will be <= 1,000,000?

Detailed Requirements

1. You will enter an x value and a y value within the above constraints. The x value will be less that the y value. Each will be an integer. You do not need to edit these numbers.
2. The application must calculate and display the number of palindromes within that range.
3. Include x and y as potential palindromes. For example, if x = 343 and y = 6226 then the number of palindromes is at least two because x and y are both palindromes.
5. The judges will enter additional test data not provided below to further test your application. You don't need to validate the input. The judges will only enter valid data.

Output

Display a single number indicating how many palindromes exist in the range for each test case. Format the output exactly as shown in the test data below.

Test Data

InputOutput
X valueY Value
55 757 71
1 1000000 1998
11111 100000 889
1 100 18

A sample console interface is provided below. Your user interface is not being judged. Each set of data can be tested by rerunning the application.

Lower bound:
55
Upper bound:
75
The number of palindromes is 2

Figure 1

A sample graphical user interface is provided below. Your user interface is not being judged. Each set of data can be tested by rerunning the application.

Figure 2

Stacking Blocks

Problem Description

In this problem you will be given X number of blocks. You must programmatically determine the highest level to which the blocks can be stacked and how many blocks, if any, are left over. For example, with 3 blocks I can build a pyramid of 2 rows (2 levels) and have 0 left over as shown below.

With 8 blocks I can build a pyramid of 3 rows (3 levels) and have 2 left over.

Detailed Requirements

1. Read the number of blocks. This will be an integer value greater than zero ( > 0 ) and less than largest size an integer can be.
2. Determine the highest level to which the blocks can be stacked and how many blocks are left over.
3. Display the level and the number of blocks left over.
5. The judges will enter additional test data not provided below to further test your application. You don't need to validate the input. The judges will only enter valid data.

Output

For each test case display a single line indicating the highest level possible and the number of blocks left over. Format the output exactly as shown in the test data below.

Test Data

InputOutput
1 1 level(s) with 0 block(s) left over
8 3 level(s) with 2 block(s) left over
1500 54 level(s) with 15 block(s) left over
1000000 1413 level(s) with 1009 block(s) leftover

Your user interface is not being judged. Each set of data can be tested by rerunning the application.

Number of blocks:
1500
54 level(s) with 15 block(s) leftover

Figure 3

A sample graphical user interface is provided below. Your user interface is not being judged. Each set of data can be tested by rerunning the application.

Figure 4

Gather Points

Problem Description

The goal of this exercise is to navigate through an array accumulating “points”. You can only move forward (to the right or down). Diagonal moves are not allowed. You enter the array at the top left corner and exit at the bottom right corner. You must always move to the next square with the largest value. The array will be of various sizes and the values will be given to you. You will not encounter a choice between two numbers that are equal. One choice will always be greater than the other.

The path accumulating the most points is highlighted below.

The total points accumulated are 37. This is based on the following:

1. Add 5 from starting point. Then “move” right or down to the larger of 6 or 8.
2. Accumulate 8 by “moving” to that square.
3. Then “move” to the larger of 2 or 10.
4. Accumulate 10 by “moving” to that square.
5. Continue the process arriving at a total of 37.

If we repeat the same process on another sample array below we arrive at a total number of 51 accumulated points.

The points accumulated were calculated based on the following “path” through the array: 3 + 7 + 10 + 8 + 9 + 5 + 9 = 51.

Detailed Requirements

1. Only integers will exist in the array. The array will not necessarily have the same number of rows and columns but it will always be rectangular. You may hard code the array - no user input is required.
2. The array will never have a combination where the choice where to move will be between two equal numbers. One move will always have more points than an alternative move.
4. The judges will use additional test data not provided below to further test your application.

Output

Display a single number that is the maximum sum of the digits representing a path from the upper left corner to the lower right corner.

You Are It

Problem Description

Kids at a birthday party want to play a favorite game modeled after the game of tag. Unfortunately it is raining so they can’t go outside. They can’t run in the house so you decide to write a computer application to simulate the game. In the game the children sit in a circle and one person outside the ring (the leader) sings a song with a fixed number of words. Moving clockwise around the circle, the leader points to a new child in the ring for each word in the song. The child being pointed to on the last word of the song is out and must leave the circle. The leader then repeats the process with the smaller circle. The game continues until the last child is eliminated. This child is then the leader to start the next game.

Detailed Requirements

1. Read an integer value representing the number of kids who will be playing the game. The number will be greater than one and less than 1001.
2. Read an integer value representing the number of words in the song. The number will be greater than one and less than the maximum size an integer can store.
3. Display the list, in order, of the players eliminated.
5. The judges will enter additional test data not provided below to further test your application. You don't need to validate the input. The judges will only enter valid data.

Output

Display a single line indicating the order of players eliminated. Separate each number by a single space.

Test Data

Number of KidsWords in SongOutput
11 4 4 8 1 6 11 7 3 2 5 10 9
6 3 3 6 4 2 5 1
25 8 8 16 24 7 17 1 11 21 6 19 5 20 10 25 15 12 4 3 9 14 23 22 13 2 18
4 5 1 3 4 2
10 12 2 5 9 6 4 8 7 3 1 10

A sample console interface is provided below. Your user interface is not being judged. Each set of data can be tested by rerunning the application.

Enter number of kids:
6
Enter number of words in song:
3
3 6 4 2 5 1

Figure 1

A sample graphical user interface is provided below. Your user interface is not being judged. Each set of data can be tested by rerunning the application.

Figure 2

The Snail in the Well

Problem Description

A snail is at the bottom of a well and wants to climb to the top. The snail can climb X feet while the sun is up, but slides down Y feet at night while sleeping. The snail has a fatigue factor of F%, which means that on each successive day the snail climbs F% feet less than it did the previous day. The distance lost to fatigue is always F% of the first day's climbing distance. Given the height of the well, X, Y, and F, on what day does the snail leave the well? An alternative fate is the snail will not be able to climb out of the well and slides back to the bottom. In that case you will need to determine the day when the snail returns to the bottom of the well. Consider the example below.

Height of well = 6; X (distance climbed the first day) = 3; Y (distance slipped each night) = 1; F (fatigue percent) = 10

 Day Initial Height Distance Climbed Height After Climbing Height After Sliding 1 0' 3' 3' 2' 2 2' 2.7' 4.7' 3.7' 3 3.7' 2.4' 6.1' -

Example 1

The snail’s height on the third day (6.1 feet) exceeds the height of the well (6 feet) and this indicates it has climbed out of the well.

Another example demonstrates the snail failing back to the bottom.

Height of well = 1; X (distance climbed the first day) = 1; Y (distance slipped each night) = 1; F (fatigue percent) = 1.

 Day Initial Height Distance Climbed Height After Climbing Height After Sliding 1 0' 1' 1' 0' 2 0' 0.99' 0.99' -0.01'

Example 2

The snail’s height on the second day (-0.01 feet) is negative and this indicates it has slid back to the bottom of the well.

1. A day consists of a period of sunlight followed by a period of darkness.
2. The snail escapes the well when its height exceeds the height of the well.
3. The snail hits the bottom of the well again when its height becomes negative (< 0).
4. Input will consist of four integer numbers separated by a single space. Each number will be greater than 0 and less than 101. The first number will be the height of the well. The second number will be how far the snail climbs on the first day. (The snail will never climb a negative distance.) The third number will be how far the snail slips each night. The fourth number will be “fatigue factor”.
5. All the numbers input will be considered to be in feet.
6. The fatigue factor is used to determine how much the snail’s climbing ability is reduced. The reduction amount is the same for each day and is based on the climbing distance of the first day. In the example 1 above, the fatigue factor is 10. This means the snail will climb .3 feet less each day. This is calculated as the first day climbing distance (3 feet) times 10 percent.
7. If the fatigue factor drops the snail's climbing distance below zero, the snail does not climb at all that day.
8. The snail always slides the same amount at night regardless of how far it has climbed during the day.
9. The snail never climbs a negative distance. If the fatigue factor drops the snail's climbing distance below zero, the snail does not climb at all that day.
10. The snail leaves the well when the height it has climbed exceeds the height of the well. Your solution should print “Success on day X” where X represents the numerical count of the days.
11. The snail hits the bottom of the well again when its height becomes negative (< 0). Your solution should print “Failure on day X” where X represents the numerical count of the days.
13. The judges will enter additional test data not provided below to further test your application. You don't need to validate the input. The judges will only enter valid data.

Output

For each test case display a single line indicating whether the snail succeeded (left the well) or failed (slid back to the bottom) and on what day. Format the output exactly as shown in the test data below.

Test Data

Height of WellInitial Climbing DistanceSliding DistanceFatigue FactorOutput
6 3 1 10 Success on day 3
10 2 1 50 Failure on day 4
50 5 3 14 Failure on day 7
50 6 4 1 Failure on day 68
50 6 3 1 Success on day 20
1 1 1 1 Failure on day 2

A sample console interface and a graphical user interface are provided below. Your user interface is not being judged. Each set of data can be tested by rerunning the application.

Figure 1

Figure 2