Practice Problems
Immediately below is a sample problem. If you would like more
problems to practice with or just get a better idea of the
type of problems you might encounter at a programming contest
here is the 2002 Question Set
[PDF].
Complete Contest Problem Sets
2006 Problem Set complete with
Input and Output files [812KB ZIP]
2005 Problem Set complete with Input and Output files
[453KB zip]
2004 Problem Set complete with
Input and Output files [123KB ZIP]
2002 Problem Set complete with
Input and Output files [183KB ZIP].
Past Contest Questions [PDF]
New Zealand Contest: 2000 Questions
2001 Questions, 2002
Questions, 2003 Questions 2004
Questions 2006 Questions
South Pacific Contest: 2000 Questions,
2001 Questions, 2002
Questions, 2003 Questions
Problem A
Word Finder (10 points)
Word finder puzzles are a popular amusement. In such a puzzle
you are given a rectangular grid of letters, and a list of
words which you are asked to locate. These words may begin
anywhere in the grid and proceed vertically, horizontally,
or diagonally, and either forwards or backwards.
Write a program that will read in a sequence of such grids
and a list of target words for each, and attempt to find each
target word in the grid. If the target word is found, then
specify the start and end positions, as (row, column) pairs,
counting rows from 1 downwards, and columns from 1 leftwards.
Each target word will appear at most once in the grid. If
the target word does not appear at all, this must be reported.
Input will consist of a series of puzzles. Each puzzle will
start with a line containing a pair of integers representing
the number of rows and number of columns in the grid (r and
c, both in the range 1 to 20 inclusive). This is followed
by r rows of the grid, each containing c uppercase letters.
This is followed in turn by a series of lines, each containing
between 3 and the maximum of r and c uppercase letters, representing
the target words, one per line, each consisting of a string
of uppercase characters. This list is terminated by a line
containing a single #. Input is terminated by a line containing
two zeroes (0 0).
For each puzzle, output a header line consisting of the word
“Grid” followed by a single space, and a running
number starting from 1. This is followed by the list of target
words in the order in which they appear in the input, each
on a line by itself, followed by a space and either the words
“not found” if the word was not found in the
grid or the locations of the first and last characters in
the word, formatted exactly as shown below. Separate successive
grids by single blank lines.
Sample Input
3 4
EGAR
TOOL
ATSX
RAGE
FROG
GOT
ROT
#
1 3
ABC
XYZ
#
0 0
Sample Output
Grid 1
RAGE found from (1,4) to (1,1).
FROG not found.
GOT found from (1,2) to (3,2).
ROT found from (1,4) to (3,2).
Grid 2
XYZ not found.
|