Sample Questions from the 2015 Contest

Description

Develop a program that can determine if each segment (starting from the left) of a number is even divisible by the number of digits in that segment. What? Consider the number 4412. The first segment is 4, the second is 44, the third is 441, and the last segment is 4412. Each of those segments must be evenly divisible by the number of digits in that segment as shown below to be called a magic number.

Detail Requirements

1. Prompt for and accept as input a positive integer having a minimum of two digits and at most nine digits. You do not need to edit this input. Only valid values will be entered.
2. You may use a console application or build a simple GUI application for the input and output.
3. Determine if the number has the property described above.
4. Display the output as shown in the Test Data below.
5. Each input number can be tested by rerunning the application.
6. The judges will enter additional test data not provided below to further test your application.

Test Data

Description

A prime number is a number greater than 1 that is divisible evenly only by 1 and itself. Find each prime number between X and Y that has a palindrome that is also prime. For example the number 17 is prime and its palindrome, 71, is also prime. X and Y will be integers such that X > 1 and Y > 1. Also X < Y.

Detail Requirements

1. Prompt the user to enter X and read it. Prompt the user to enter Y and read it.
2. You do not need to edit the input. Only valid integer values will be entered.
3. You may use a console application or build a simple GUI application for the input and output.
4. Determine each prime number whose palindrome is also prime within the required range of numbers as described above.
5. Display the output as shown in the Test Data below.
6. Each set of input numbers can be tested by rerunning the application.
7. The judges will enter additional test data not provided below to further test your application.

Test Data

Description

A wraparound number occurs when you can use each digit in the number to “locate” the next digit to visit and you can visit all the digits once without visiting any digit more than once. How about an example?

Consider the number 3172. Always start with the left most digit which in this case is 3. Move 3 digits to the right which takes you to the 2. You have now “visited” the 3 and the 2. From the 2 you need to move 2 positions to the right. This means you have to wraparound to the beginning and you’ll end at the 1. You have now visited the 3, 2, and 1. From the one you need to move 1 position to the right which takes you to the 7. You have now visited all the digits exactly once so 3172 is a wraparound number.

Now consider the number 3234. Again you start with the left most digit which is a 3 in this example. Move three positions to the right and you end at the 4. You have now visited the 3 and the 4. Move 4 positions to the right wrapping around as necessary. You end at the 4 again. You have now visited the 4 a second time without visiting all the other digits. Therefore 3234 is not a wraparound number. 
Write a program that accepts as input a positive integer having at most nine digits and that reports whether or not it is a wraparound number. The input will be at least 2 digits long and no digits will be equal to 0.

Detail Requirements

1. Prompt the user to enter an integer and read it.
2. You do not need to edit the input. Only valid integer values will be entered.
3. You may use a console application or build a simple GUI application for the input and output.
4. Determine whether that number is a “wraparound” number as described above.
5. Display the output as shown in the Test Data below.
6. Each set of input numbers can be tested by rerunning the application.
7. The judges will enter additional test data not provided below to further test your application.

Description

In any 2 dimensional array, there can be a maximum of two separate “saddle” points (or cells). Saddle point 1 will contain a value larger than any other in its row and smaller than any other in its column. Saddle point 2 will contain a value smaller than any other in its row and larger than any other in its column.

There can be at most one of each but there could be no saddle points. In addition there could be one type 1 saddle point and no type 2 saddle point or vice versa.

Develop a program that will determine each saddle point, if any, for a given two dimensional array. Display the row and column for each type of saddle point. Read the array values from a text file. The first line in the file will be the number of rows in the array. The second line in the file will be the number of columns in the array. Each line in the remainder of the file will be a value for the array. For example, line 3 will contain array element 0, 0, line 4 will contain 0, 1, etc.

No array will be larger than 20 by 20.

Use the following array as an example. (Input for this array would be as shown in the first sample test data below.)

The value 0 at row 2 column 1 is larger than any other value in its row and smaller than any other value in its column. This is saddle point 1. 

Description

Develop a program that accepts as input a random number of positive and negative integers and zero. There will always be at least one positive integer. Determine the starting and ending point of the contiguous segment of that input that sums to the largest value. Also determine what that largest value is. For example, assume you are given the sequence (S) of numbers below.

S = <2, 5, -1, -7, 12, 5, 3, -10, 5, -5, 20, -5, 0, 3>

Some place in S is a contiguous “segment” of numbers that sums to a value larger than any other contiguous segment. The following are all valid segments of S.

In the examples above, the segment S(5..11) gives the largest value when its elements are summed. In fact, this segment generates the largest possible sum for any segment in the given sequence S.

Detail Requirements

1. The input test files (sequence1.txt, sequence2.txt, sequence3.txt, sequence4.txt, sequence5.txt) will be located on your computer’s Desktop. Use Windows Explorer to get the correct path.
2. Each sequence will contain an unknown number of positive integers, negative integers, or zeros terminated by the end of file. There will be one value per line in the file. Valid values will range from -9000 to 9000.
3. The last number in the sequence will be followed by the end of file marker. No sequence will be longer than 50 numbers.
4. You do not need to edit the input. Only valid integer values will be entered.
5. Each file of input numbers can be tested by rerunning the application.
6. You may use a console application or build a simple GUI application for the input and output.
7. Determine the maximum contiguous segment sum and what that segment is.
8. Display the output as shown in the Test Data below.
9. Each set of input numbers can be tested by rerunning the application.
10. The judges will enter additional test data not provided below to further test your application.

Test Data

Description

In this problem you will need to find the longest “subsequence” between two given sequences and how long that subsequence is. You are not looking for substrings that match as subsequences do not have to be contiguous. For example, consider the sequences below.

X = (AGCAT)
Y = (GAC)

We can calculate the longest subsequence of X, Y as 2 and there are three (GA), (AC), and (GC). We can use an array like the one below to determine these values.

Because the longest subsequence of a portion of one string and no portion of the other string (represented by the dash) is zero, the first row and the first column of “data” is 0 as shown below. Each cell will contain the longest subsequence for that combination of X and Y.

To calculate the longest subsequence we calculate a value for each cell following these rules.

• The value of cell X, Y equals 1 plus the value diagonally to its upper left if X equals Y.
• The value of cell X, Y equals the larger of a) the cell immediately to its left or b) immediately above if X does not equal Y.

For example, the value of row 3, column 3 is 0 because X = 3 is G and Y = 3 is A. These are not equal so we take the larger of cell 3, 2 (which is 0) or 2, 2 (which is 0). Following this rule, row 3 values are highlighted below.

The completed table has the values shown below.

The cell value in the lower right corner is the length of the longest subsequence.

To get the actual subsequence you must work backwards determining at each cell how you placed a value there based on the rules above. Starting at 5, 7 (lower right corner) we can determine C is not equal to T so we must have “got there” from either the cell on the left or the cell immediately above, whichever is larger. Since each contains the value 2, you can pick either. I’ll choose to move to the left one cell. I’m now at 5, 6. X and Y are C and A which are not equal so I need to move immediately to the left or immediately up to whichever cell has the larger value. Each cell has the value 2 so I’ll move to the left again. I’m now at cell 5, 5. Now X and Y are equal as both are C. This is the last item in a subsequence! We must move diagonally to the upper left since the values are equal. I’m now at 4, 4. Again the X, Y values are not equal so I will move one cell to the left (I could alternatively move up). I’m now at cell 4, 3. Now X and Y are equal again (both are A). This is the second to last item in a subsequence! Because the values are equal I must move diagonally to the upper left to cell 3, 2. I have no Y value here so I am done.

These two sequences have a longest subsequence of 2 and one of those subsequences is AC. You can see the “backtrack” used to determine the actual sequence in the table below.

Had we taken other alternative paths, still following the two rules above, we would have found (GA) or (GC).

Detail Requirements

1. Prompt the user to enter sequence 1. This must be processed as a single input to read the entire sequence. In other words, enter the data and press the enter key once. You cannot require the user to press the enter key after each character.
2. Prompt the user to enter sequence 2 following the same rules as above.
3. The maximum length of X and Y will be nine characters. The minimum length will be three.
4. You do not need to edit the input. Only valid integer values will be entered.
5. You may use a console application or build a simple GUI application for the input and output.
6. Process the data and display the length of the longest subsequence and an actual subsequence as shown in the Test Data below. You only have to display one subsequence if there is more than one of the longest length.
7. Each set of input can be tested by rerunning the application.
8. Display the output as shown in the Test Data below.
9. The judges will enter additional test data not provided below to further test your application.

Test Data

Description

Mr. Tyler works in a tile shop and is often asked to calculate the number of tiles (full and partial) to tile rectangular floors. To make this easier, he has asked you to write a computer program with the following features.

The user will enter the length and width of the room. All rooms are rectangular or square. The user will also enter the size of the tile. It is always a square. The user will also enter the “grout gap”. Each tile that is next to another tile must have a small space for the tile grout (the grout gap) between them. All numbers entered are in inches, will be greater than zero, and can contain decimals (numbers to the right of the decimal point).

It is standard procedure to have partial tiles “split” so there is equal spacing on each opposite side. For example, assume a tile is 4 inches wide and the floor length used 50 tiles with 3 inches left over. These 3 inches must be divided so there are 1.5 inches of tile on one side and 1.5 inches of tile on the opposite side. Partial tiles will exist only on the outside (or perimeter) of the floor. Partial tiles, if they exist, may be shortened lengthwise or widthwise, or both. Only tiles in the corner will be reduced in both length and width. There will be either 4 reduced size corner tiles or 0 reduced size corner tiles.

Each tile (full or partial) that is next to another tile must have a small space for the tile grout (the grout gap). Tiles that are next to the wall do not have a grout gap.

Detail Requirements

Your computer program must display the following:

1. Prompt the user to enter the length of the room, the width of the room, the length of a tile, and the size of the grout gap.
2. The combination of width, length, tile size, and grout gap size will not leave any remaining space (for partial tiles) that is less two grout gaps plus some additional space for partial tiles.
3. You do not need to edit the input. Only valid decimal values will be entered.
4. You may use a console application or build a simple GUI application for the input and output.
5. You can use the computer’s calculator accessory.
6. Determine
   1. the number of full sized tiles needed,
   2. the number of reduced width tiles needed if any,
   3. the number of reduced length tiles needed, if any,
   4. the number and size of corner tiles needed, if any.
7. Display the output as shown in the Test Data below. The number of uncut (full size) tiles needed.
8. Each set of input numbers can be tested by rerunning the application.
9. The judges will enter additional test data not provided below to further test your application.

Test Data