General Information for the University of Michigan-Dearborn Programming Contest

Input and Output Specifications

The following represents the normal restrictions to input and output. If exceptions are to be made, they will be explicitly stated in the Input or Output sections of the problem descriptions.

• All input will be read from standard input. The data on each line will be separated by a single space. There will be no white space at the beginning or at the end of a line. Blank lines will contain no characters. Tabs will never be used. Note that lines may contain more than 80 characters (not including "newline" characters). It should be obvious what the maximum length of the input lines can be for each problem.
• You will be given information in the problem statement to determine the end of input without the need to test for end-of-file.
• You may assume that all input data will conform to the input specifications of the problem; we will not try to trip you up by giving you bogus input.
• Input data will be restricted so that all integer arithmetic in "reasonable algorithms" will not cause 32-bit integer overflow. Contestants are advised to use type long for all integer calculations, except in those problems where it is obvious that large precision integers (e.g. integers with hundreds of digits) are needed.
• All output goes to standard output. There should be no additional white space at the beginning or the end of any line. Blank lines should contain no characters. The last line of output should not be a blank line. This means that when requested to "separate items with single spaces" you should not simply follow each item on a line with a space, as that will result in an extra space at the end of the line. Likewise, when requested to "separate output for each problem instance with a blank line" you should not output a blank line after the output of each problem instance.
• If asked to display floating-point numbers to a certain number of places, the system's default round-off will suffice. We will restrict input so that the output produced will not cause round-off problems. If asked to display to n places, display exactly n digits to the right of the decimal, even if there are trailing zeros.

A note on the problem descriptions

Most problems will include a sample instance in order to describe the problem and demonstrate what is being asked. Sometimes, but not always, this sample is included in the Sample Input, that is always given at the end of the problem description, along with the corresponding Sample Output. Do not assume that the Sample Input includes the sample instance discussed in the problem.

Programming Languages

The compilers used are Microsoft C/C++Version 9.0.21022 and Sun JDK 1.6. All standard C/C++ libraries (including STL) and Java API are available, except for those that are deemed dangerous by contest officials (e.g., that might generate a security violation).

Note the following C++ considerations:

•  In C++ your "main" function must have the return type int. If you use "void main()" your program will not compile.
• you must use standard headers, such as <iostream>, <string> and so on.  If you use <iostream.h> <string.h>, and so on, your program will not compile
• Microsoft Compilers sometimes add <stdafx.h> header to your program.  Remove it before submitting, or your program will not compile on judge's machines.

Resource Limits

Your programs will have a limit on the amount of memory and CPU time they can use. Your program is allowed a maximum of 64MB for the data and 64MB for the stack. There is also a limit of 5MB on the amount of output your program is allowed to produce. Since the judging machine is different from the contestant machines, it is meaningless to post the CPU time limit used for judging. Please note that the CPU time limits set on the contestant machines are different from those set on the judging machine.

Judges' Responses

Each submission will receive one of the following responses. The first one that the judges notice will be issued.

    NO - Compilation Error
   NO - Run-time Error
   NO - Time Limit Exceeded
   NO - Wrong Answer
   NO - Security Violation
   NO - Output Format Error
   NO - Excessive Output
   NO - Insufficient Output
   NO - Other - Contact Staff
   YES - Correct Answer

"YES - Correct Answer" means that your program gave the correct output on all test cases, so you can start celebrating! (but not for too long - there are still other problems!)

"NO - Other - Contact staff" is used for an incorrect submission when the judges wish to tell you more information about your submission. For example, perhaps you submitted the solution of problem E for problem F. Upon receiving this response, the contestant should submit a clarification request to the judges. The judges will then reply with a more detailed message.  This response will be rare

"NO - Output format error" means the output included letters in the wrong case (e.g. upper instead of lower case), extra or missing spaces (including extra space at the end of a line), extra or missing blank lines (including extra blank lines at the end of your output), misspellings and missing or extra symbols or punctuation. (See "Problems Involving Floating-Point Precision" below.)

"NO - Wrong answer" means at least one calculated result for at least one problem instance was incorrect. Even if you are correct on 99 problem instances but are wrong on the last one, you will get this response. (See "Problems Involving Floating-Point Precision" below.)

Problems Involving Floating-Point Precision: Incorrect use of precision will only be judged as a Wrong Answer when the resulting value is not equal to the correct value. For example, if the judges' answer is 9.890, then

"NO - Excessive Output" means that your program output results for more test cases than there were in the judges' test file.  Note that this does not mean that there was excessive output for true test cases - this would be a presentation error.  For example, if there were two test cases in the test file, and the output expected looked like "Case n: The answer is x", then the following is a presentation error:

Case 1: The answer is 10 gkjh
Case 2: The answer is 12

while the following is an excessive output error

Case 1: The answer is 10
Case 2: The answer is 12
Case 3: The answer is

"NO - Insufficient Output" means that your program did not process all of the judges test cases.  Continuing with the example above, an insufficient output error would be

Case 1: The answer is 10

"NO - Run-time error" means that your program crashed when run on judges' data. This includes running out of memory.

"NO - Security violation" is explained later in this document.

"NO - Time limit exceeded" means your program did not terminate after a predefined amount of CPU time. The CPU time limits will be stated on the problem set. Note: The time limits on the contestant machines may not correspond to those on the judging machines because of differences in processor speed.

"NO - Compilation error" means that your program did not compile.

Logging in

When you arrive at your assigned workstation, you should be presented with a PC^2 log in screen. Enter your team ID and password to log in.

Note: If you exit PC^2, you will need to restart PC^2 again and log in. If you did not properly log out, you will not be allowed to log in. If this happens, please inform a proctor.

Environment

You may use any of the text editors or IDEs installed on the workstation to write your programs.  Windows calculator is also allowed.  Use of any internet web browser may be cause for disqualification.

Compiler/IDEs available for C, C++ and Java are:

• Visual Studio .NET
• Visual Studio 2005
• Visual Studio 2008
• Bloodshed Dev 4.9.9.2

 Compilers for Java:

• JDK 1.6

For source code submission to the judges PC2 environment is used.  It is not an IDE.  If you want to get familiarized with PC2, check out http://www.ecs.csus.edu/pc2/doc/v85/team/PC2TeamGuide.htm

You can write code in one of the above IDEs, or use Notepad++, VIM editor (Windows version), or notepad.

Editing Your Programs

Your program source and input files should be named in the following way:

where "PROB" is the problem letter you are trying to solve. The scripts executed by the "Test" button in PC^2 assume that you have used these file names. Your submission should not include more than one file unless you are using Java.

For example, if you are working on problem C, then your program source can be in C.c, C.cpp, C.java or C.cs, and your input file can be C.in.dat.

Java notes: If you are using multiple source files in Java, choose the main class as the "Main File" and any other required files as the "Additional Files". Remember that your file names must correspond to the public class names in the file.

Compiling and Testing Your Programs

To compile and test your programs, select the problem, language, and program source file in the PC^2 window and click on the "Test" button. The source code is compiled using the same compiler settings used by the judges to judge your programs. If the compilation is successful, your program is then executed on each of the input files in your home directory, and the output is displayed in a new editor window on your screen. Exit this window when you are done.  Your program will be killed automatically if it uses too much CPU time. If you wish to terminate the program yourself, go to the window and press Ctrl-c (Control+c).

Note: The time limits on the contestant machines may not correspond to those on the judging machines because of differences in processor speed.

It is highly recommended that you use the "Test" button in PC^2 to do the testing, since this will execute your program in exactly the same way as it would be executed by the judges (on different data, of course).

Submitting Your Programs

To submit your program, select the problem, language, and the program source file (do not submit your executable!) in the PC^2 window and click on the "Submit" button. It is recommended that you click on the "Test" button and make sure that your program works as expected before trying to submit.

Debugging Your Programs

You are not allowed to use debuggers in this contest. You may use output statements to provide information to help you debug your program. Note: Remember to remove this output (even if it is to stderr, cerr, or java.lang.System.err) before submitting your program.

Clarification Requests

All questions about the problem set must be communicated to the judges by sending clarification requests. To do so, click on the "Clarifications" tab in the PC^2 window and click on "Request Clar". Then, select the problem, enter your request, and click "Submit".

Viewing the Scoreboard

The scoreboard will be projected on the whiteboard for all contestants to see during the contest.

Printing

Files can be printed using the application’s print function.  Your name must be on your printout or you will not be allowed to pick it up.

Example

Suppose that you are solving the following problem (real problem descriptions will be more detailed and probably a little harder):

Problem A: Add 1

Write a program that reads input integers and adds 1 to every integer. Every line of input contains one integer, and the output should contain the same number of lines, in which the integer is one more than the corresponding input integer. The end of input is indicated by a line containing only 0.

Sample Input

1
2
3
0

Sample Output

2
3
4

Step 1: Edit your program

If you are using C, you should enter the following program and save it as A.c:

#include <stdio.h>

int main(void)
{
    int n;
    while (scanf("%d", &n) == 1 && n != 0) {
        printf("%d\n", n+1);
    }
    return 0;
}

If you are using C++, you should enter the following program and save it as A.cpp:

#include <iostream.h>

int main(void)
{
    int n;
    while (cin >> n && n != 0) {
        cout << n+1 << endl;
    }
    return 0;
}

If you are using Java, you should enter the following program and save it as A.java:

import java.util.Scanner;

public class A
{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        while (n != 0) {
            System.out.println(n+1);
            n = in.nextInt();
        }
    }
}

Step 2: Edit your input files

You should save the input files under the names A.1.dat, A.2.dat, ... For example, you may want to enter the following into A.1.dat:

1
2
3
0

Step 3: Test your program

In the PC^2 window, select the problem and the language you choose, as well as the program source file. Click the "Test" button. The program is compiled, and if there are no errors, the program is run on the supplied input files. The result is displayed in a new editor window. Quit the editor window when you are done.

You may wish to experiment and see what happens when your program does not compile, or when your program causes run-time errors.

Step 4: Submit your program

In the PC^2 window, select the problem and the language you choose, as well as the program source file. Click the "Submit" button.