Sample Questions from the 2019 Contest

Read these instructions but do not open the booklet until instructed to do so.

1. Inside are 8 problems. You may solve the problems in any order.
2. Sample test data is provided for each problem. Sample output is also provided. You must match the sample output exactly for the corresponding input for your application to be considered correct. In addition, the judges will enter additional data not available to you to further test your application.
3. You may use any or all the following computer programming languages: Visual Basic, Java, C++, C#, C, or Python. You can use different languages for different problems or the same language for all the problems.
4. The application design and programming style (use of comments, indentation, white space, etc.) will not be considered when judging your solution. The only criterion for successful completion is that the application works as defined by the problem description, the sample output can be produced using the sample input, and the additional test data entered by the judges produces the required output.
5. Once you have completed a problem, login to the DomJudge system and upload your file. Make sure you attach the correct file for the correct problem number. If you are using Visual Studio, zip your entire project folder and attach that zip file. For other IDEs, like Eclipse, you only need to submit the source code file. Ask your room monitor if you have any questions about what to submit. Submit applications as you complete them. Do not wait to submit all your applications at once.
6. You may change a solution after you submit it. However, the completion time for that problem also will be changed to reflect the later submission. Any changes to a previously submitted problem will cause the completion time for that problem to be extended. This applies to changes made because of oversights such as initially submitting the wrong solution file.
7. You may use the help system within development tool to research language APIs only. Some help systems provide links to programming topics on the Internet. While you can use the help system you cannot use the links to access programming topics on the web. Violations will result in your immediate disqualification.
8. The competition period begins at 1:00 pm and ends at 4:00 pm.
9. Contact a room monitor by raising your hand if you have a question.
10. Contact a room monitor by raising your hand if you need to leave the room. Once the competition begins, do not leave the room without prior permission from a room monitor. You will not be readmitted if you do.
11. If you finish before 4:00 pm, you may wait in the check in area. The competition award ceremony should begin at approximately 4:30 pm.

1.  Number Frequency

In this problem you are given a list of positive integer values between 1 and 100 inclusive. Determine how many times each value is entered. Display each number entered and how many times it was entered. Read each number from the console. Display the output on the monitor. Run your application once for each set of test data. 

Input

Prompt the user as shown in the sample input below. Then enter some number of positive integers between 1 and 100. Any number of values can be entered. Each will be separated by a space. At least one non-zero number will be entered. The last integer in the list will be a zero indicating the end of the data. The zero is NOT part of the list. Read each number from the console.

Output

A listing of each number entered and how many times that number was entered. The output must be in order from the lowest number entered to the highest number entered. You must correctly use the words “times” and “time” as shown in the sample output below. Display the output on the monitor. See the sample output below.

Test Data

Additional Information

• You do not need to edit the input data.
• You do not need to handle exceptions. 
• Add your name as a comment in the first line in your source code. Add the following after your name: “Blue #1”. 
• The judges will test your application with a different set of data that will have a different number of test cases.

2. Consecutive Numbers

In this problem you are given a list of positive and negative integer values (excluding zero). You must determine if the same value was entered 3 times in a row any place in the list of integers. For example, the list:
98 102 -44 16 16 16 98 166 0
contains the number 16 in three consecutive positions. However, the list:
777 56 23 32 23 99 23 0
does not contain any occurrence of the same number appearing three times in a row. When finished processing, display a message indicating no number appeared three times in a row or a message indicating a number did appear three times in a row and what that number was. At least one number will always be entered. Run your application once for each set of test data.

Input

Prompt the user as shown in the sample input below. Then enter some number of integers – positive or negative. Any number of values greater than one can be entered. In other words, at least one number will be entered. Each will be separated by a space. The last integer in the list will be a zero indicating the end of the data. The zero is NOT part of the list. Three consecutive numbers will appear only once if they appear at all. Read each number from the console.

Output

Display the line “Consecutive values not found” if the same number was not found in three consecutive positions. Display the line “Consecutive values found for X” if the same number was found in three consecutive positions. Replace the X with the number. Display the output on the monitor. See the sample output below.

Test Data

Additional Information

• You do not need to edit the input data.
• You do not need to handle exceptions. 
• Add your name as a comment in the first line in your source code. Add the following after your name: “Blue #2”. 
• The judges will test your application with a different set of test cases.

3. Erase the Data

Many operating systems “delete” a file by removing the file’s name and location from an index. The actual data is not deleted. This saves time and eventually the original contents of the file will be overwritten by some other file’s data. More thorough delete programs not only remove the file’s name and location from an index but also write random characters over the file’s data effectively destroying it. In this problem you will be given the size of two files in bytes and how long it takes to write random characters over the data in each. This rate will be given in bytes/second. Determine the total time required to erase the data.

For example, assume you were given the values:
2048 1024 50000 10000

These values would indicate:

• the size of file 1 is 2048 bytes
• file 1 can be “erased” at 1024 bytes per second
• the size of file 2 is 500000 bytes
• file 2 can be “erased” at 10000 bytes per second.

Using this data, the total time to erase all the data in the two files would be 7 seconds. This is calculated as 2 seconds to erase the data in the first file. It will take 5 seconds to erase the data in the second file for a total of 7 seconds. Run your application once for each set of test data.

Input

Prompt the user as shown in the sample input below. Then enter four positive integer numbers representing the number of bytes in the file and the erasure rate for two different files. Each integer will be separated by a space. Read each number from the console.

Output

Display the total number of seconds it will take to erase the data in both files. Rounding is not required in this problem. Display the output on the monitor. See the sample output below.

Test Data

Additional Information

• You do not need to edit the input data.
• You do not need to handle exceptions.
• Add your name as a comment in the first line in your source code. Add the following after your name: “Blue #3”.
• The judges will test your application with a different set of test cases.

4. Let’s Make a Call

Given an alphanumeric phone number, convert it to all digits. For example, given 1-800-FLOWERS, your application will convert it to 1-800-3569377. Notice the hyphens maintain their location to match their position in the original phone number. An image of a phone keypad is provided below. All letters in the phone number will be uppercase only. Run your application once for each set of test data.

Input

A valid alphanumeric phone number consisting of the number 1 followed by a dash followed by any combination of the digits 1 through 9, dashes, and uppercase letters in the alphabet. Read the phone number from the console.

Output

The equivalent phone number converted to all numbers. Display the output on the monitor. See the sample output below.

Test Data

Additional Information

• You do not need to edit the input data.
• You do not need to handle exceptions.
• Add your name as a comment in the first line in your source code. Add the following after your name: “Blue #4”.
• The judges will test your application with a different set of test cases.

5. Array Filter

In this problem you will process a list of integers using a “moving filter”. The filter creates a subset of integers from the list. As the filter moves, a new subset of integers is created. For each subset you will need to display the smallest integer value. For example, given the list below:

12 15 11 7 19 5

Using a filter size of 2, the list of integers will be divided into subsets of two and the filter will move one position to the right. The smallest integer for each sub set is displayed. The list of smallest integers would be:

12 11 7 7 5

The result was obtained in the following manner. The initial subset based on a filter size of 2 is 12 and 15. 12 is the smaller integer so it becomes the first entry in the answer. This filter moves one position to the right and the subset becomes 15 and 11. 11 is the smaller integer so it becomes the second entry in the answer. The filter moves one position to the right and the subset becomes 11 and 7. 7 is the smaller integer so it becomes the third entry in the answer. The filter moves one position to the right and the subset becomes 7 and 19. 7 is the smaller integer so it becomes the fourth entry in the answer. The filter moves one position to the right and the final subset becomes 19 and 5. 5 is the smaller integer so it becomes the final entry in the answer.

Input

The size of the filter will be an integer greater than 1 and less than or equal to the number of integers in the list. The user will enter the number of integers in the list. Then each integer value is entered. Read all the data from the console.

Output

The list of the smallest integer from each subset. Display the output on the monitor.

Test Data

Additional Information

• You do not need to edit the input data.
• You do not need to handle exceptions.
• Add your name as a comment in the first line in your source code. Add the following after your name: “Blue #5”.
• The judges will test your application with a different set of test cases.

6. Your Shift Is Over

Given a list of integers, “shift” the list a set number of positions to the left. For example, given the list:

3 6 18 -7 99 12

and a “shift” of 2, the result would be: 

18 -7 99 12 3 6

The result makes it appear each number has been shifted 2 positions to the left. Numbers that shifted off the left edge (3 and 5 in the example) resurface in their proper location on the right end of the list. 

Input

A list of valid integers. There will be at least 1 integer entered and not more than 100. The number 0 will indicate the end of the list. The 0 must not be considered part of the list. The shift number is also entered. This number will be greater than 0 and less than or equal to the number of integers in the list. Read all the data from the console.

Output

The modified list shifted N positions to the left. N represents the shift number as described above. Display the output on the monitor.

Test Data

Additional Information

• You do not need to edit the input data.
• You do not need to handle exceptions.
• Add your name as a comment in the first line in your source code. Add the following after your name: “Blue #6”.
• The judges will test your application with a different set of test cases.

7. Sentence Maker

In this problem you are given a list of characters followed by a sentence. You must determine if the sentence can be formed using only the letters from the first list. Each letter in the first list can only be used once. There will be no punctuation in either list. For example, given the list “friend icing on the sung” can the sentence “coding is fun” be formed? The answer is yes. However, given the list “please bake umpteen cookies” you can’t form the sentence “bugs are problems”. 

Input 

Two strings with each string having at least one character. The second string may be longer, shorter, or the same length as the first string. All letters input will be lowercase. Read all the data from the console. 

Output

Display the word “possible” if the second string can be created using the letters contained in the first string. Display the word “not possible” if the second string can’t be created using the letters contained in the first string. Display the output on the monitor. 

Test Data

8. Island Hopping

A list of integers is used to represent the “jumping distance” between islands. Use these numbers to determine if you can “jump” from one island to the next and land exactly on the last island. For example, given the list:

3 1 0 1 3

The first entry always represents the starting point. From the starting point you can jump 3 islands. This will take you to the island represented by the number 1. From that island you can jump 1 position to the last island. This represents success.

Now consider a list like:

4 3 2 1 0 2 3

Again, you would start on the first island (4) and could jump 4 islands to the island represented by 0. From this island you can’t jump any further so the last island cannot be reached. This represents failure. It is also a failure if your “jump” would take you past the last island.

Input

 The first integer (N) is the number of integers to follow. The first integer is NOT part of the “jumping” data. After the first integer, N number of integers will follow. Each integer will be greater than or equal to zero. Read all the data from the console. 

Output

“Success” if the last “island” can be reached without going past the end of the list. “Failure” if the last island cannot be reached. Display the output on the monitor.

Test Data

Additional Information

• You do not need to edit the input data.
• You do not need to handle exceptions.
• Add your name as a comment in the first line in your source code. Add the following after your name: “Blue #8”.
• The judges will test your application with a different set of test cases.

Read these instructions but do not open the booklet until instructed to do so.

1. Inside are 8 problems. You may solve the problems in any order.
2. Sample test data is provided for each problem. Sample output is also provided. You must match the sample output exactly for the corresponding input for your application to be considered correct. In addition, the judges will enter additional data not available to you to further test your application.
3. You may use any or all the following computer programming languages: Visual Basic, Java, C++, C#, C, or Python. You can use different languages for different problems or the same language for all the problems.
4. The application design and programming style (use of comments, indentation, white space, etc.) will not be considered when judging your solution. The only criterion for successful completion is that the application works as defined by the problem description, the sample output can be produced using the sample input, and the additional test data entered by the judges produces the required output.
5. Once you have completed a problem, login to the DomJudge system and upload your file. Make sure you attach the correct file for the correct problem number. If you are using Visual Studio, zip your entire project folder and attach that zip file. For other IDEs, like Eclipse, you only need to submit the source code file. Ask your room monitor if you have any questions about what to submit. Submit applications as you complete them. Do not wait to submit all your applications at once.
6. You may change a solution after you submit it. However, the completion time for that problem also will be changed to reflect the later submission. Any changes to a previously submitted problem will cause the completion time for that problem to be extended. This applies to changes made because of oversights such as initially submitting the wrong solution file.
7. You may use the help system within development tool to research language APIs only. Some help systems provide links to programming topics on the Internet. While you can use the help system you cannot use the links to access programming topics on the web. Violations will result in your immediate disqualification.
8. The competition period begins at 1:00 pm and ends at 4:00 pm.
9. Contact a room monitor by raising your hand if you have a question.
10. Contact a room monitor by raising your hand if you need to leave the room. Once the competition begins, do not leave the room without prior permission from a room monitor. You will not be readmitted if you do.
11. If you finish before 4:00 pm, you may wait in the check in area. The competition award ceremony should begin at approximately 4:30 pm.

1. Subtract Leading Digit

In this problem you will create a sequence a numbers. Each new number is calculated by subtracting the first digit from the current number. That process is repeated until the sequence reaches a specified ending number. After calculating the sequence display how many numbers were generated in the sequence. For example, given a starting number of 100 and an ending number of 50, the sequence would be:
99 90 81 73 66 60 54 49

8 numbers in sequence 

The first number in the sequence (99) was calculated as 100 – 1. The second number (90) was calculated as 99 – 9. Each succeeding number was calculated by subtracting the first digit from the number. The sequence stops when the calculated number is equal to or less than then the ending number (50). Another example uses the starting number 50 and the ending number zero. The sequence generates is:
45 41 37 34 31 28 26 24 22 20 18 17 16 15 14 13 12 11 10 9 0

21 numbers in sequence 

Remember the goal is to display the count of numbers in the sequence not the sequence itself. 

Input

Enter a starting number and an ending number. The starting number will be positive and greater than the ending number. This will insure there is always at least one number in the sequence. The ending number will be greater than or equal to 0. Read each number from the console.

Output

Display a count of numbers in the sequence. Display the output on the monitor. See the sample output below. 

Test Data

Additional Information

• You do not need to edit the input data.
• You do not need to handle exceptions.
• Add your name as a comment in the first line in your source code. Add the following after your name: “Gold #1”.
• The judges will test your application with a different set of data that will have a different number of test cases.

2. Parallel or Intersecting Lines

In this problem you will determine if two lines are parallel (don’t intersect) or intersecting. Each line will be defined by a pair of x, y coordinates: x1, y1 and x2, y2. Even though the x, y coordinates define a line segment, you should assume the segment continues indefinitely in both directions. Parallel lines have the same slope and never intersect. The formula for slope is slope = y2 - y1 / x2 - x1
The output consists of the following indicating the relationship between the lines: intersecting, parallel, parallel - both lines vertical, intersecting - one line vertical.

Below are rules for slope:

• The slope of all vertical lines is undefined. This is because the denominator in the slope calculation would be 0. If both lines are vertical, they will never intersect. This means they are parallel. If only one line is vertical, the lines will intersect.
• Parallel lines never intersect and have the same slope.
• Intersecting lines will have defined slopes and each line will have a different slope.

Input

Prompt for and read four integer values that define the first line. Prompt for and read four integer values that define the second line. Each integer will be separated by a space. No combination of points will describe the same line. Read each number from the console.

Output

Display intersecting, parallel, parallel - both lines vertical, or intersecting - one line vertical depending on the slopes of the lines. Display the output on the monitor. See the sample output below.

Test Data

Additional Information

• You do not need to edit the input data.
• You do not need to handle exceptions.
• Add your name as a comment in the first line in your source code. Add the following after your name: “Gold #2”.
• The judges will test your application with a different set of test cases.

3. Weighted Sum 

The goal in this problem is to sum all the digits in a number. However, each number must be “weighted” by its relative position in the number. For example, given the number 57 the weighted sum is 19. The weighted sum is calculated as:
(5 * 1) + (7 * 2).
Given the number 482178, the weighted sum is 113. The weighted sum is calculated as:
(4 * 1) + (8 * 2) + (2 * 3) + (1 * 4) + (7 * 5) + (8 * 6).

Input

Enter a positive integer number. Read the number from the console.

Output

Display the weighted sum of the number. Display the output on the monitor. See the sample output below.

Test Data

Additional Information

• You do not need to edit the input data.
• You do not need to handle exceptions.
• Add your name as a comment in the first line in your source code. Add the following after your name: “Gold #3”.
• The judges will test your application with a different set of test cases.

4. Equivalent Strings

In this problem you will determine if two strings are "equivalent". Equivalent means one string can be transformed into the other by substituting one letter for another. For example, consider the two strings “cocoon” and “zyzyyx”. These would be considered equivalent because: c-> z, o -> y, n -> x. Each letter in one string maps to one and only one letter in the second string and vice versa. 

On the other hand, the two strings “banana” and “orange” are not equivalent. This is because ‘a’ in banana would have to map to ‘r’, ‘n’, and ‘e’ in orange. There is no one to one substitution that works. Based on the definition of “equivalent” for this problem, strings of different lengths cannot be equivalent. 

Input

The first string will be entered on line 1. The second string will be entered on line 2. Each string will have one or more lowercase letters. The strings will not necessarily be the same length. Read the input from the console. 

Output

Display “equivalent” if the strings are equivalent based on the description above. Display “not equivalent“ if the strings are not equivalent. Display the output on the monitor. See the sample output below. 

Test Data

Additional Information

• You do not need to edit the input data.
• You do not need to handle exceptions.
• Add your name as a comment in the first line in your source code. Add the following after your name: “Gold #4”.
• The judges will test your application with a different set of test cases.

5. Vigenere Cipher 

Vigenere Cipher is a method of encrypting alphabetic text. It uses a simple form of polyalphabetic substitution. A polyalphabetic cipher is any cipher based on substitution, using multiple substitution alphabets. The encryption of the original text is done using the Vigenère square. Below is the Vigenere square for this problem.

A line of text to be encrypted will be entered followed by the encryption key. each combination of text character and key character provide the col, row index value into the Vigenere square to find the encrypted character. For example, assume the text to encode is “no pets” and the key is “dog”. The first letter of the encrypted text is located at [d][n] or q from the square above. The second coded letter is located at [o][o] or c from the square above. The third coded letter is located at [g][p] or v from the square above. The remaining letters in the encrypted text are listed below.

[d][e] →h 

[o][t] → h 

[g][s] → y 

Input

Two lines of text will be entered. The first line represents the text to encrypt. The text will have at least one letter. Only lower case letters and spaces will be entered. The second line represents the encryption key. The key will have at least one letter. The key may have fewer letters, the same number of letters, or more letters than the text. The key will not have any spaces. Read all the data from the console 

Output

The encrypted text. Spaces in the original text will be duplicated in the encrypted text. Display the output on the monitor. See the sample output below. 

Test Data

Additional Information

• You do not need to edit the input data.
• You do not need to handle exceptions.
• Add your name as a comment in the first line in your source code. Add the following after your name: “Gold #5”
• The judges will test your application with a different set of test cases.

6. Excel Lent Notation

The spreadsheet software application Excel identifies cells by a combination of letters and numbers. The first cell (row 1 column 1) is A1. The cell name for the first row and column 26 is Z1. Row 5 column 27 is AA5. In summary, columns 1-26 convert to the letters A-Z. Each group of 26 adds another letter. For example: 

• columns 27 - 52 converts to AA to AZ
• columns 53 – 78 converts to BA to BZ
• columns 79 - 104 converts to CA to CZ
• ....
• columns 703 – 728 converts AAA to AAZ

In this problem you will be given a row number and a column number. Your application must convert that combination into an Excel cell address. Process each combination of row and column until r0c0 is found (row 0 column 0). r0c0 indicates end of data.

Input

One or more lines of the format rxcy where r indicates a row number follows and x will be an actual row number from 1 to 1,048,576. The c indicates a column number follows and y will be an actual column number from 1 to 16,384. The end of the data will be signified by input of r0c0. The r0c0 is NOT part of the data. Read each number from the console.

Output

The matching Excel cell name. Display the output on the monitor. See the sample output below.

Test Data

Additional Information

• You do not need to edit the input data.
• You do not need to handle exceptions.
• Add your name as a comment in the first line in your source code. Add the following after your name: “Gold #6”.
• The judges will test your application with a different set of test cases.

7. Alphabetized Substring

In this problem you need to determine the largest alphabetized substring. Given a string of characters, determine which contiguous group of characters has the largest number of characters that are in ascending alphabetical order. For example, given the string “adfjabcghl” the largest substring in alphabetical order is abcghl. 

Every string will have at least one alphabetized substring. Display the first substring if the string has more than one substring of the same length. 

Input

Prompt for and read a list of lower-case letters. No spaces, numbers, or special characters will be entered. There will always be at least one character entered. There is no upper limit to how many characters can be entered. Read the data from the console. 

Output

The characters in the largest substring. Display the output on the monitor. See the sample output below. 

Test Data

Additional Information

• You do not need to edit the input data.
• You do not need to handle exceptions.
• Add your name as a comment in the first line in your source code. Add the following after your name: “Gold #7”.
• The judges will test your application with a different set of test cases.

8. Overlapping Rectangles 

Given two rectangles that overlap, determine the total area of the two rectangles and the shared area of the two rectangles. A rectangle can be defined by the x and y coordinates of its lower left corner and its upper right corner. In this problem you will be given the coordinates to define two rectangles. The rectangles will intersect (overlap) in some way. For example, given the rectangles defined by rectangle 1 (-3, -0) and (3, 4) and rectangle 2 (0, -1) and (9, 2). 

The area of a rectangle equals its width times its length. The area of the rectangle on the left is 24 (6 times 4). The area of the rectangle on the right is 27 (9 times 3). The area of the overlap section is 6. This means the total area of the rectangles is 45 (24 + 27 – 6).

This second example uses the rectangles defined by rectangle 1 (0, 0) and (3, 3) and rectangle 2 (2, 2) and (4, 4).

The area of the rectangle on the left is 9 (3 times 3). The area of the rectangle on the right is 4 (2 times 2). The area of the overlap section is 1. This means the total area of the rectangles is 12 (9 + 4 – 1). The rectangles will always overlap in some way. The rectangles will never be the same rectangle.

Input

The first line of input will be four integer values each separated by a space. The second line of input will be four integer values each separated by a space. Read each number from the console.

Output

Display the area where the rectangles overlap. Display the total area of the two rectangles. Display the output on the monitor. See the sample output below.

Test Data

Additional Information

• You do not need to edit the input data.
• You do not need to handle exceptions.
• Add your name as a comment in the first line in your source code. Add the following after your name: “Gold #8”.
• The judges will test your application with a different set of test cases.