## The British Informatics Olympiad Sample Problems

15 March 1995

You should try to write computer programs to solve the following problems. The exact details of what your programs ask for or print does not matter, but they should clearly be able to do what is required.

It is in your interest to work on your own, as you will have to if you enter the British Informatics Olympiad; but you may consult other people if there are features of the programming language that you don't know how to use. You may have access to written notes, programming manuals, books or printed programs, and you may spend as long as you want on the problems (although they should only take you a few hours in total). Any programming language or computer system may be used, although Turbo Pascal on the PC is the recommended language for the BIO.

Don't worry if you make small mistakes, as it is the methods you use that are important.

If you can solve these problems without too many mistakes, you should enter for the British Informatics Olympiad.

Solutions to these problems can be found in samples.pas.

## 1. Prime Numbers

A prime number is defined as any integer greater than one which contains no factors other than one and itself - that is, if there is no number between (and not including) 1 and N which can divide N with no remainder, then N is prime.

Your program should ask for a maximum number, M, and search for and print all prime numbers in the range 2..M. You should also display the number of prime numbers found. M will not be greater than 2000.

### Sample Output for Problem 1

Maximum number to test? 21

The following numbers between 2 and 21 are prime:

2 3 5 7 11 13 17 19

A total of 8 prime numbers were found in this range.

## 2. Word Count

You should write a program which asks for the name of a file and then counts the number of words in the file. A word is defined as any sequence of symbols separated by any combination of space characters and/or line breaks.

The file will not contain lines more than 127 characters long and will have a maximum of 20,000 words.

(Take care when creating a test file to make sure it ends with at least one blank line, otherwise it may be ignored by your programming language.)

### Sample file for Problem 2: sample.fil

The cat sat on the mat.

The cow jumped over the moon.

She sells sea shells on the sea shore.

### Sample Output for Problem 2

Name of file for word count? sample.fil

The file sample.fil contains 20 words.

## 3. Bubble sort

To solve this problem you should write a program to sort numbers. It should read in integers from the keyboard, ending with and ignoring the number -999, sort them and print them in order, smallest first. There will be between 2 and 20 numbers to be sorted.

You may use a simple sorting method called bubblesort. This simply compares each number with its next neighbour in turn, swapping them if they are out of sequence, and repeatedly goes through the data until no more changes can be made.

### Sample Output for Problem 3

Type in up to 20 numbers, ending with -999:

23

12

45

32

8

-1

2

-999

The 7 sorted numbers are:

-1

2

8

12

23

32

45

Antony Rix