Programming Competition Preparation Notes

From Student ACM Wiki
Revision as of 09:26, 18 February 2015 by Brylow (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Contest programs are expected to read from System.in and write to System.out and be in the default package. Programs should not prompt for input. Given a program Ex1.java, we judge it by using the following command lines:

 javac Ex1.java
 java Ex1 < judge_in1 > my_out1

and comparing my_out1 to the expected output file.

Participants should be able to handle simple parsing of input. For instance, using Scanner methods next(), nextInt(), nextDouble(), nextLine() and the corresponding hasNext(), ... should be sufficient. You should know how to detect end of file. In testing programs that use end of file to determine the end of the input, it's useful to know that you can generate an end of file on the console using a appropriate control character. In Windows, this is ctrl-Z. In Unix/Linux, ctrl-D.

Some problems will require formatted output. System.out.printf() is one of the simplest ways to do this.

Many problems will require working with Strings, especially methods length(), charAt(), substring(), equals(), compareTo() and split(). In particular, Scanner.nextLine() combined with String.split() is often an effective way to process lines of unknown length.

You should know how to convert a String to a corresponding number using methods such as Integer.parseInt().

We assume a basic familiarity with 1-dimensional and 2-dimensional Arrays.

Contest problems will *not* involve file I/O other than System.in and System.out. There will be no command line arguments, graphical interface programming, or networking/web programming.

Many teams find using a development environment such as Eclipse or NetBeans helpful.

Exercise 1

Problem: Given a list of strings of the same length, flip around the main diagonal (topleft to bottomright). In other words, the symbol in row r, columm c of the input should be in row c, column r of the output. Input will have at most 20 rows and 20 columns.

Input:

  ..##@@..$
  .##.@@.$.
  ##..@@$..
  #...$$...
  #..$@@...
  #.$.@@...

Output:

  ..####
  .##...
  ##...$
  #...$.
  @@@$@@
  @@@$@@
  ..$...
  .$....
  $.....

Sample solution:

  import java.util.Scanner;
  public class Ex1
  {
     public static void main(String[] args)
     {
         Scanner keyboard = new Scanner(System.in);
         String[] rows = new String[20];
         int num_rows = 0;
         while (keyboard.hasNextLine())
         {
             rows[num_rows] = keyboard.nextLine();
             num_rows++;
         }
         int width = rows[0].length();
         for(int c = 0; c < width; c++)
         {
             for(int r = 0; r < num_rows; r++)
                 System.out.print(rows[r].charAt(c));
             System.out.println();
         }
     }
  }

Exercise 2

Problem: First row of input gives the number of cases. Each following row consists of the number of values for this case followed by the list of values. Print the maximum value and number of entries equal to this maximum for each case as shown below.

Input:

  5
  3 0 2 1
  5 12 12 14 14 14
  6 -2 -4 -4 -3 -3 -4
  1 100
  8 10 11 12 11 12 11 10 9

Output:

  Case 1: 2,1
  Case 2: 14,3
  Case 3: -2,1
  Case 4: 100,1
  Case 5: 12,2

Sample solution:

  import java.util.Scanner;
  public class Ex2
  {
     public static void main(String[] args)
     {
        Scanner keyboard = new Scanner(System.in);
        int num_cases = keyboard.nextInt();
        // Output wants cases numbered from 1
        for (int c = 1; c <= num_cases; c++)
        {
           int num_vals = keyboard.nextInt();
           int max_val = Integer.MIN_VALUE;
           int max_count = 0;
           for (int i = 0; i < num_vals; i++)
           {
              	int val = keyboard.nextInt();
              	if (val == max_val)
                   max_count++;
              	else if (val > max_val)
              	{
                   max_val = val;
                   max_count = 1;
              	}
           }
           System.out.println("Case "+c+": "+max_val+","+max_count);
        }
     }
  }

Exercise 3

Problem: Exercise 1 with numbers. Input is given in width 4 fields, ints between -99 and 999. Output should also use width 4 fields.

Input:

  0   0  -2  24
  1   1  -1  25
  1   5   1   0
  2   0   9 -56
  3   0   6   0
  5   0 100   1

Output:

  0   1   1   2   3   5
  0   1   5   0   0   0
 -2  -1   1   9   6 100
 24  25   0 -56   0   1

Sample solution:

  import java.util.Scanner;
  public class Ex3
  {
     public static void main(String[] args)
     {
         Scanner keyboard = new Scanner(System.in);
         int[][] vals = new int[20][20];
         int num_rows = 0;
         int num_cols = 0;
      	  while (keyboard.hasNextLine())
         {
            String line = keyboard.nextLine();
            line = line.trim(); //otherwise, split() gives
                                //empty string at beginning
            String[] line_words = line.split("\\s+");
            if (num_rows == 0)
               num_cols = line_words.length;
            for (int c = 0; c < num_cols; c++)
               vals[num_rows][c] = Integer.parseInt(line_words[c]);
            num_rows++;
         }
         for(int c = 0; c < num_cols; c++)
         {
             for(int r = 0; r < num_rows; r++)
                System.out.printf("%4d",vals[r][c]);
             System.out.println();
         }
     }
  }
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox