program Samples;
{ Borland Pascal 7.

  The sample problems for the 1995 British Informatics Olympiad.

  See the end of this file for copyright notice and disclaimer. }

{-------------------- The Problems -----------------------} {

Problem 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 one 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 to 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 numbers were found in this range.

Problem 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 20000 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.


Problem 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 of 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 different, and
repeatedly goes through the file 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

}
{-------------------- The Solution -----------------------}

procedure Primes;
{ Solves problem 1: find prime numbers from 2 to m. }

  function IsPrime(N: Integer): Boolean;
  { returns True if N is prime.
    This is done by trying to find an integer j between 2
    and the square root of N that divides N exactly;
    N is prime if no such number exists. }
  var
    j, Stop: Integer;
    Factored: Boolean;
  begin
    Factored := False;
    j := 2;
    Stop := Trunc(Sqrt(N)) + 1; { stop at the square root of N }

    { test for factors of N and stop of one is found. }
    while (j <= Stop) and (j < N) and not Factored do
    begin
      Factored := ((N mod j) = 0);
      j := j + 1;
    end;
    IsPrime := not Factored;
  end;

var M, N, I: Integer;
begin
  WriteLn('Find prime numbers.');
  WriteLn;
  { N = total number of primes found }
  N := 0;
  Write('Maximum number to test? ');
  ReadLn(M);
  WriteLn('The following numbers between 2 and ', M:1, ' are prime:');
  { test the numbers 2 to M }
  for i := 2 to M do if IsPrime(I) then
  begin
    N := N + 1;
    Write(i:1, ' ');
  end;
  WriteLn;
  WriteLn('A total of ', N:1, ' numbers were found in this range.');
end;

procedure WordCount;
{ a solution of problem 2: count words in a file. }
{ This is done by reading in characters from the file
  one by one, testing if each character is a space/CR
  or not, and incrementing the word count whenever it passes
  from space to a word. }
var
  F: Text;
  Name: String;
  c: Char;
  Count: Integer;
  InWord, WasInWord: Boolean;
begin
  WriteLn('Count Words');
  WriteLn;
  Write('Name of file for word count? ');
  ReadLn(Name);
  { open the file for reading }
  Assign(F, Name);
  Reset(F);
  Count := 0;
  InWord := False;
  while not EOF(F) do
  begin
    WasInWord := InWord;
    { end of line counts as a word break }
    if EOLn(F) then
    begin
      ReadLn(F);
      InWord := False;
    end
    else
    begin
      Read(F, c);
      InWord := (c <> ' ');
      { not in a word if c is space }
    end;
    if (not WasInWord) and InWord then
    { passed from space into a word }
      Count := Count + 1;
  end;
  Close(F);
  WriteLn('The file ', Name, ' contains ', Count:1, ' words.');
end;

procedure BubbleSort;
{ problem 3: read in and bubble sort numbers. }
const Max = 20;
type List = array[1..Max] of Integer;

  procedure Swap(var A, B: Integer);
  var C: Integer;
  begin
    C := A;
    A := B;
    B := C;
  end;

  procedure Sort(var Data: List; n: Integer);
  var
    i, j: Integer;
    HasChanged: Boolean;
  begin
    { bubblesort works by comparing adjacent values of the
      data and swapping them if necessary. }
    i := 1;
    HasChanged := True;
    while (i < n) and HasChanged do
    begin
      HasChanged := False;
      for j := n - 1 downto i do
        if Data[j + 1] < Data[j] then
        begin
          Swap(Data[j + 1], Data[j]);
          HasChanged := True;
        end;
      i := i + 1;
    end;
  end;

var
  n, x: Integer;
  Data: List;
begin
  WriteLn('Bubblesort of numbers');
  WriteLn;
  WriteLn('Type in up to 20 numbers, ending with -999:');
  n := 0;
  repeat
    ReadLn(x);
    if (x <> -999) and (n < 20) then
    begin
      n := n + 1;
      Data[n] := x;
    end;
  until x = -999;
  Sort(Data, n);
  WriteLn('The ', n:1, ' sorted numbers are:');
  for x := 1 to n do
  WriteLn(Data[x]);
end;

procedure Menu;
{ the program's main menu, allowing choice of problems to test. }
var o: Integer;
begin
  repeat
    WriteLn('Choose a menu option:');
    WriteLn;
    WriteLn('1) Problem 1: Find prime numbers.');
    WriteLn('2) Problem 2: Word Count.');
    WriteLn('3) Problem 3: Bubblesort.');
    WriteLn('4) Exit the program.');
    WriteLn;
    Write('Choice? ');
    ReadLn(o);
    case o of
      1: Primes;
      2: WordCount;
      3: BubbleSort;
      4: WriteLn('Exiting...');
    else
      WriteLn(o, ' is not a valid menu option.');
    end;
    WriteLn;
    if o <> 4 then
    begin
      Write('Press <enter> to continue...');
      ReadLn;
    end;
    WriteLn;
  until o = 4;
end;

begin
  { main program }
  WriteLn;
  WriteLn('*******************************************************');
  WriteLn('*                                                     *');
  WriteLn('*  British Informatics Olympiad 1995                  *');
  WriteLn('*  =================================                  *');
  WriteLn('*                                                     *');
  WriteLn('*  Sample problems        -      (C) Antony Rix 1995  *');
  WriteLn('*  Question statement and example solution in Pascal  *');
  WriteLn('*                                                     *');
  WriteLn('*******************************************************');
  WriteLn;
  Menu;
end.
{ Program copyright (c) 1995 The British Informatics Olympiad (BIO).

  This program may be freely copied by persons or organisations
  involved in the British Informatics Olympiad or the International
  Olympiad in Informatics, on condition that no changes are made and
  this notice is not altered. Distribution for profit is forbidden
  unless permission is first obtained in writing from the BIO.

  This program is for educational purposes only and comes with no
  warranty, implied or otherwise, as to its fitness for any purpose.

  Author:   Antony Rix
  Internet: http://www.christs.cam.ac.uk/bio/
  E-mail:   a.rix@lineone.net
  S-mail:   The British Informatics Olympiad
            Christ's College
            Cambridge CB2 3BU
            United Kingdom
}