Reactive Program Example

Sorting Trucks

Your program should start by reading one line from standard input. This line contains the number n of trucks to be sorted (1<=n<;10). The trucks are labeled from 1 to n and all differ in weight. The weights are known only to the environment.

Next, your program should continue the dialog with the environment to sort the labels in order of increasing weight. In the dialog, your program can ask the environment which of two trucks is heavier.

To compare the trucks labeled i and j, your program should write one line to standard output. This line should begin with the uppercase letter `C' followed by i and j. Your program should then read the answer of the environment as one line from standard input, containing the label of the heavier truck (if i=j then the answer is i).

Finally, when your program has established the ordering, it should write one line to standard output. This line should begin with the uppercase letter `L' followed by the n labels in order of increasing weight.

(Extra challenge: Minimize the number of comparisons.)

Example Dialog The figure below presents an example dialog involving three trucks and four comparisons (the first being unnecessary).

+-----------------+----------------+
| Standard Output | Standard Input |
+-----------------+----------------+
 _________________|3               |
|C 1 1            |1               |
|C 1 2            |2               |
|C 2 3            |2               |
|C 1 3            |1               |
|L 3 1 2          +----------------+
+-----------------+

Reactive Program in Turbo Pascal:

var n, i, j, answer: integer;
    s: array [1..10] of integer;
begin
    readln(n) ;
    ...
    writeln('C ', i, ' ', j) ;
    readln(answer) ;
    ...
    write('L') ;
    for i := 1 to n do write(' ', s[i]) ;
    writeln
end.

Reactive Program in Turbo C++:

#include <iostream.h>
int n, i, j, answer, s[11];
int main()
{ cin >> n;
  ...
    cout << "C " << i << ' ' << j << '\n';
    cin >> answer;
  ...
  cout << 'L';
  for (i=1; i<=n; ++i)
    cout << ' ' << s[i];
  cout << '\n';
  return 0;
}

Reactive Program in QuickBasic:

DEFINT A-Z
DIM s(1 TO 10)
INPUT "", n  ' Suppress the prompt!
...
  PRINT "C"; i; j
  INPUT "", answer
...
PRINT "L";
FOR i = 1 TO n
  PRINT s(i);
NEXT i
PRINT
END

IOI 95