One more site on olympic programming

Введение

Здесь собран материал, который относится не к конкретным алгоритмам, а к олимпиадному программированию в целом.

Ввод-вывод

Обычно написание решения олимпиадной задачи начинается с кодирования операций с файлами. Мы поясним это на примере простой задачи - на входе даются два числа A и B, надо вывести их сумму.

Самое очевидное решение этой задачи выглядит так:

program Sum;

var
  A,B : Integer;

begin
  Assign(Input,'input.txt');
  Reset(Input);
  Assign(Output,'output.txt');
  Rewrite(Output);
  Read(A,B);
  Writeln(A+B);
  Close(Input);
  Close(Output);
end.

Заметьте, что в этом примере не объявляются файловые переменные, так как операции ввода/вывода проводятся через стандартные файлы Input и Output, которые есть в любой реализации Паскаля. Это позволяет также не указывать имя файловой переменной в вызовах функций Read и Write. Кроме того, в Турбо Паскале последние две строки кода можно опустить, так как в нем файлы Input и Output автоматически закрываются в конце выполнения программы. (К сожалению, к Free Pascal это не относится). Наконец, если вы хотите тестировать программу для ввода с клавиатуры, то достаточно закомментировать строки, связанные с вызовами Assign(), Reset(), Rewrite() и Close(), и не требуется изменять инструкции чтения/записи.

В реализации более сложных задач может потребоваться разделить процесс выполнения на три: ввод, решение и вывод. В этом случае решение задачи "A+B" будет выглядеть так:

program Sum;

var
  A,B,C : Integer;

procedure Inp;
begin
  Assign(Input,'input.txt');
  Reset(Input);
  Assign(Output,'output.txt'); 
  Rewrite(Output);
end;

procedure Run;
begin
  C := A+B;
end;

procedure Outp;
begin
  Writeln(C);
  Close(Input);
  Close(Output);
end;

begin
  Inp;
  Run;
  Outp;
end.

Реализация таким способом решения задачи "A+B" может показаться странной, но для более сложных задач она часто бывает удобнее. Кроме, того, она позволяет использовать разные переменные цикла для чтения, решения и записи и не делать их глобальными.

Символ O()

Время работы алгоритмов сильно зависит от языка программирования, процессора, операционной системы. Поэтому для оценки времени работы (cложности) алгоритма применяется асимптотическая оценка - говорят, что алгоритм работает за время O(f(x)), где x - переменная, связанная с размером входных данных, а f(x) - некоторая функция. Например, алгоритм обхода в глубину работает за время O(N^2), где N - число вершин графа. Что же означает символ O?

Пусть функции f(x) и g(x) больше нуля при x>0. f(x) называется O большим от g(x) (f(x)=O(g(x))), если найдется такие числа C>0 и x0>0, что f(x)<Cg(x) при всех x>x0. Обозначение f(x)=O(g(x)) фактически означает, что порядок функции f(x) при больших x не больше, чем функции g(x). Ясно, что f(x)=O(f(x)) и из f(x)=O(g(x)) и g(x)=O(h(x)) следует f(x)=O(h(x)).

Приведем несколько примеров: x=O(x^2), x^2=O(x^3), log x=O(x), ax=O(x), log(x!)=O(x log x).

Соотношение с O показывает, как быстро будет расти время работы алгоритма при больших x, что весьма важно. Пусть, например, у нас есть два алгоритма, один из которых работает за время f(x)=x^2, а второй за время g(x)=10000x. Ясно, что f(x)=O(x^2), g(x)=O(x). При малых x f(x) будет намного меньше g(x), но при больших x, например при x=100000, f(x)=10^10, а g(x)=10^9<f(x), и при увеличении x разница между этими двумя функциями будет быстро расти.

Отсечение по времени

В большинстве задач есть ограничение по времени, и в случае его превышения за тест ставится 0 баллов, даже если программа в процессе перебора уже нашла правильный ответ. В таких случаях применяется отсечение по времени - в начале выполнения программы записывается текущее время, и перебор прерывается в том случае, если время выполнения программы превышает критическое значение; в этом случае выводится наилучший полученный к этому моменту результат.

В Турбо Паскале для реализации отсечения по времени используется переменная типа Longint по абсолютному адресу $0:$46c; ее значение увеличивается на единицу каждые 55 миллисекунд:

program TheTime_TP;

const
  CriticalTime = 4.8; {seconds}

var
   Ct : Longint absolute 0:$46c;
   Ot : Longint;

begin
  Ot := Ct + CriticalTime*1000/55;
  ...
  while ... do
  begin
    if Ct>Ot then
      Break;
    ...
  end;
  ...
end.

В Free Pascal для реализации отсечения по времени используется функция Now() из модуля SysUtils; она возвращает текущее время и дату в формате TDateTime; Now() становится больше на единицу через 1 сутки:

program TheTime_FP;

uses
  SysUtils;

const
  CriticalTime = 4.8; {seconds}
  CriticalD : TDateTime = CriticalTime/(24*60*60);

var
  Ot : TDateTime;

begin
  Ot := Now + CriticalTime;
  ...
  while ... do
  begin
    if Now>Ot then
      Break;
    ...
  end;
  ...
end.

Пишите мне