ACM Programming Contest

October 19, 2016, 6:00 - 9:00 PM

Instructions for handing in a program

When you have finished a program, demonstrate it directly to a judge. Raise your hand, and a judge will come to you. The judge will compile and run your program from the command line on your machine. If a judge is not available, work on the next program until one is available. Programs may be written in Java, C/C++, or C#, and must compile and run from a command prompt to be counted.


Problem 0 : Name

Write a program that prints your name diagonally on the screen. For example, if your name is “Grace Hopper”, a run of the program might go like the following:

Example Input:
    java Name

Example Output:
    G
     r
      a
       c
        e

          H
           o
            p
             p
              e
               r

Note that no input is required. You can just hard-code your name into the program. When you are finished with the program, show it to one of the judges.


Problem 1 : Word Up

Given a set of words read in from the keyboard, print out the words from bottom to top with one space between the words. An example run of the program is shown below:

java WordUp
Enter some words on one line:  
OSU Go Pokes

    s
    e
U   k
S o o
O G P

Problem 2 : Word Count

Given an input file, strip off the punctuation (which we will consider to be period, and comma), and make a list of words in the file and how many times the word was used in the file. Display only those words that appear more than once in the file, and list by order of frequency. For example, suppose the input file contains the text:

    The sky calls to us.  If we do not destroy ourselves,
    we will one day venture to the stars.  How lucky we
    are to live in this time, the first moment in human
    history when we are in fact visiting other worlds.

    Carl Sagan

Then your program should print the following:

    we   4
    the  3
    to   3
    in   3
    are  2

Problem 3 : Set

In the game Set, the player is presented with up to twelve cards, each of which has four characteristics: shape, number, color, and Fill. Each characteristics has three possible values, listed below:

    Shape:      oval, diamond, squiggle
    Number:     1, 2, 3    
    Color:      red, green, blue
    Fill:       filled, outline, striped

We can specify a card as a string with 4 characters, using the first letter of the value for each characteristic. For example o1rf means a card with one oval shape that is red and filled.

The goal for the player is to find “sets” of three cards from the cards presented. A set is defined as 3 cards that all have the same value, or all have different values, for all 4 attributes. The cards below make a set, with the shape and color attributes being all the same, and the number and fill attributes being all different:

    o1rf, o3ro, o2rs

Write a program that will take in a list of cards from a file and print all of the sets that can be made from the cards (without listing a given set more than once). When you are finished, pass off your program to one of the judges.


Problem 4 : Getting your X’s in a row

Given a grid of X and dot characters read in from a file, write a program that will read the grid, and determine the position of the longest linear chains of X characters in the file, which may be listed horizontally, vertically, or diagonally. Your program must print the length of the longest linear chain, and print coordinates of at least one of these longest chains.

For example, consider the input file shown below:

    X...
    XXXX
    ..XX
    ...X

We consider the top left position to be (0,0), and the position below this to be (0,1). When run, your program could print:

    4: (0,1)-(3,1)

Since the longest linear chain is of length 4.


Problem 5 : Follow the X

Given a grid of X and dot characters read in from a file, write a program that will read the grid, and determine the position of the longest path of X characters in the file, where a path can be followed by going up, down, right, or left in the grid. For example, consider the input file shown below:

    X...
    XXXX
    ..XX
    ...X

In this case, the longest chain is of length 7, and your program might print:

    7: (0,0), (0,1), (1,1), (2,1), (3,1), (3,2), (2,2)

Problems from ACM-ICPC