|
The Southern California Region policy regarding contest problems is that we do not publish the judges' data, nor do we publish a "solution set." For further reference, additional problem sets can be found at the ICPC "Preparing for the Competition" site and at various sites on the web using your favorite search engines.
while not end-of-file
read some lines of input
process the data
if appropriate, print line(s) of output
end
Because GUIs react principally to human interaction rather than input data, their structure is roughly
initialize GUI
do forever
e=wait_for_event()
process_event(e)
end
The vast majority of problems in this region fall squarely within the 'while not end-of-file' category.
A submission for judging is a single program, written in a single programming language.
A submission for judging is a single file that contains all classes, functions, definitions, etc. for the program. C, C++, and Java permit the specification of an entire program, even supporting code, as a single monolithic file. The Southern California Region requires a monolithic file so that we can track submissions by a single file.
C and C++ programmers form monolithic files often, but Java is usually taught as a one-file-per-class language. To make a monolithic source file in Java, one must avoid declaring classes as public. Furthermore, the Southern California Region requires that the class containing the main() method be called aout.
A source file is a text file that contains compilable code. You may use a text editor or integrated development environment (IDE) such as Eclipse to develop your code. Note that Eclipse wants to follow the Java one-file-per-class model and tries to make classes public. You should remove the reserved word "public" from each Java class declaration.
This is slightly contrived, but otherwise illustrative.
import java.io.*;
class Point { // note that the class is NOT public
private double x;
private double y;
public Point(double x, double y) { // however, the constructor method needs to be public
this.x=x;
this.y=y;
}
private double square(double x) { // methods internal to a class may be private or protected
return x*x;
}
public double GeometricMean() { // this is a public method for use by instances of Point
return Math.sqrt(square(x) + square(y));
}
}
// aout is NOT public and contains the main() method
class aout {
// standard declaration for the main() method
public static void main (String [] args) throws IOException
{
Point p;
String s;
BufferedReader stdin;
String [] token;
double x;
double y;
stdin=new BufferedReader(new InputStreamReader(System.in));
while ( (s=stdin.readLine()) != null) {
token=s.split(" ");
x=Double.parseDouble(token[0]);
y=Double.parseDouble(token[1]);
p=new Point(x,y);
System.out.println("(" + x + "," + y + "), geometric mean=" + p.GeometricMean());
}
System.exit(0);
}
}
In general, test input to programs is
To prepare contestants for competition in the Southern California Region, we offer the following discussion and examples.
During the 2007 and 2008 regional contests, the judges encountered contestants' questions and problem submissions indicating an incomplete understanding regarding what constitues a line of text. A line of text on a Unix-like host is
Producing the ASCII 0x0A (line feed) for output depends upon the programming language. See the solutions below for examples.
Decades ago, computer programs never directly interacted with humans. A human would load a stack of punch cards or paper tape containing the program and data for processing. The computer would then be started, and it would not stop working until the program finished or aborted with an error. There were no such things as file names—or operating systems, for that matter. The program didn't even have to open a file to read its data; it was assumed that programs took input, processed the input, then spewed output. This concept of unnamed input and output, ready for reading and writing, evolved into standard input and standard output.
Standard input isReading from standard input and writing to standard output differ according to the programming language. See the solutions below for examples.
Unnamed standard input and standard output also make repeated program executions against different files possible without having to recompile the program or rename files. The judges make extensive use of this by producing multiple files with differing test cases.
Unix, DOS, Windows, and some other operating systems have added a powerful abstraction that can be used with programs that read from standard input and write to standard output. This abstraction views a program like an electric circuit, with standard input seen as an incoming signal and standard output as an output signal. Circuits can be cascaded, feeding the output signal of one circuit to the input signal of another—without needing to record any of the signals. Similarly, the output of one program can be fed to the input of another program without having to save intermediate files; this is commonly known as piping. Originally, this allowed complex sequential processing to consume small amounts of disk space. With symmetric multiprocessing, each program can potentially execute in a separate CPU, permitting pipeline parallel processing.
End-of-file is a testable condition. In this region, contestants are expected to know how to read a file until end-of-file, without attempting to read beyond end-of-file.
We offer an explanation in the form of examples. Below is the warmup problem from the 2002/2003 Southern California Regional contest. We solve it six times: in Python 3, C, C++ using a seed read, Java, Kotlin, and again in C using a seed read. The "seed read" technique is used in languages that cannot perform assignments within condition tests nor perform look-ahead input. The seed read technique often shows up in shell scripting languages.
Unary NumbersWhat could be simpler than binary numbers? Unary numbers! A Unary number, n > 0, is coded as n-1 one bits followed by a zero bit. Thus the code for 5 is 11110. Here are some unary numbers.
Input consists of decimal numbers, one per line, with no leading or trailing whitespace. Each number will be in the range 1–76. Input is terminated by end-of-file. For each number, produce a single line of output consisting of the input decimal number, with no leading zeros or spaces, a single space, and the unary equivalent with no leading or trailing spaces. 76 37 5 28 14 8 1 76 1111111111111111111111111111111111111111111111111111111111111111111111111110 37 1111111111111111111111111111111111110 5 11110 28 1111111111111111111111111110 14 11111111111110 8 11111110 1 0 |
Standard input is identified by the class, sys.stdin. The print( ) function writes to standard output.
import sys
for line in sys.stdin:
line=line.replace('\n','') # remove end-of-line present in strings read from input
n=int(line)
print(n, end=' ') # print number in decimal followed by one space
for i in range(n - 1):
print('1', end='') # print '1' without any trailing characters
print('0') # print '0' followed by newline
exit(0) # indicate normal program termination
Standard input is identified by the stream variable, stdin. Standard output is identified by the stream variable, stdout.
#include <stdio.h>
int main()
{
int i;
int n;
char s[4]; /* room for two decimal digits, newline, and a zero-byte to terminate the string */
/* fgets() returns NULL at end-of-file */
while(fgets(s,sizeof(s),stdin) != NULL) { /* read an entire line into s */
sscanf(s,"%d",&n); /* extract n from the input line */
fprintf(stdout,"%d ",n);
for (i=n - 1; i > 0; i--) {
fputc('1',stdout);
}
fputs("0\n",stdout); /* the newline character, \n, emits an ASCII 0x0A */
}
return 0; /* indicate normal program termination */
}
#include <iostream>
using namespace std;
int main ()
{
int n;
cin >> n; // seed read
while(!cin.eof()) { // eof() valid only after attempted read
cout << n;
cout << ' ';
while (n > 1) {
cout << '1';
n--;
}
cout << "0\n"; // the newline character, \n, emits ASCII 0x0A
cin >> n;
}
return 0; // indicate normal program termination
}
Making use of standard output in Java is easy: simply use the methods in System.out. Performing meaningful line-oriented input from standard input requires wrapping a couple of classes around System.in.
import java.io.*;
class unary {
public static void main (String [] args) throws IOException
{
int n;
String s;
BufferedReader stdin;
// wrap BufferedReader around InputStreamReader around System.in
stdin=new BufferedReader(new InputStreamReader(System.in));
// BufferedReader.readLine returns null at end-of-file
while ( (s=stdin.readLine()) != null) {
n=Integer.parseInt(s);
System.out.print(n + " ");
for (int i=n - 1; i > 0; i--) {
System.out.print("1");
}
System.out.println("0"); // println() writes an ASCII 0x0A
}
System.exit(0); // indicate normal program termination
}
}
The kotlin readLine() function reads from standard input. At end-of-file, readLine() returns null. The print() and println() functions write to standard output.
import kotlin.system.exitProcess
fun main() {
var s: String?
s=readLine() // seed read
while (s != null) {
var n=s.toInt()
print(n); print(" ")
while (n > 1) {
print("1");
n -= 1;
}
println("0")
s=readLine()
}
exitProcess(0) // indicate normal program termination
}
Standard input is identified by the stream variable, stdin. Standard output is identified by the stream variable, stdout.
#include <stdio.h>
int main()
{
int i;
int n;
char s[4]; /* room for two decimal digits, newline, and a zero-byte to terminate the string */
/*
* Attempt to read an entire line into s. The fgets() preceding the while loop is the seed read.
*/
fgets(s,sizeof(s),stdin); /* attempt to read an entire line into s */
while( !feof(stdin) ) { /* while not end-of-file ... */
sscanf(s,"%d",&n); /* extract n from the input line */
fprintf(stdout,"%d ",n);
for (i=n - 1; i > 0; i--) {
fputc('1',stdout);
}
fputs("0\n",stdout); /* the newline character, \n, emits an ASCII 0x0A */
fgets(s,sizeof(s),stdin); /* attempt to read an entire line into s */
}
return 0; /* indicate normal program termination */
}
Programming Challenges, Steven S. Skiena and Miguel Revilla, 2003. This book is targeted at contestants in programming competitions and can be used for practice with the web-accessible automated judging system maintained by one of the authors.