The British Informatics Olympiad is the computing competition for schools and colleges. We are proud to present BIO 2004, sponsored by Lionhead Studios.

The 2004 British Informatics Olympiad - Round One

Time allowed: 3 hours

Instructions

You should write a program for part (a) of each question, and produce written answers to the remaining parts. Programs may be used to help produce the answers to these written questions but are not always necessary.

You may use a calculator and the on-line help that your programming language provides. You should have a pen, some blank paper, and a blank floppy disk on which to save your programs. You must not use any other material such as disks, files on a computer network, books or other written information. You may not communicate with anyone, other than the person invigilating this paper.

Mark the first page of your written answers with your name, age in years and school/college. Number all pages in order if you use more than one sheet. All of your computer programs should display your name and school/college when they are run, and the floppy disk you use to submit the programs should also show your name and school/college.

For your programs to be marked, the source code must be saved, along with executables if your language includes a compiler; this includes programs used to help answer written questions. You must clearly indicate the name given to each program on your answer sheet(s).

Sample runs are given for parts 1(a), 2(a) and 3(a). Bold text indicates output from the program, and normal text shows data that has been entered. The output format of your programs should follow the 'sample run' examples. Your programs should take less than 10 seconds of processing time for each test.

Attempt as many questions as you can. Do not worry if you are unable to finish this paper in the time available. Marks allocated to each part of a question are shown in square brackets next to the questions. Partial solutions (such as programs that only get some of the test cases correct within the time limit, or partly completed written answers) may get partial marks. Questions can be answered in any order, and you may answer the written questions without attempting the programming parts.

Hints

• If you can only see how to solve part of a problem it is worth writing a program that solves that part. We want to give you marks and questions are evaluated using multiple tests of differing difficulty. Remember, partial solutions may get partial marks.
• Question 2 is an implementation challenge and question 3 is a problem solving challenge.
• Most written questions can be solved by hand without solving the programming parts.
• Do not forget to indicate the name given to your programs on your answer sheet(s).

• Question 1
• Question 2
• Question 3
• Index of BIO 2004 round one
• Index of BIO 2005 sample paper