Олимпиады

М.С. Густокашин,
Москва

От редакции. Этой статьей мы открываем цикл публикаций, посвященных основам олимпиадной информатики. Последние систематические материалы на эту тему были напечатаны в “Информатике” в далеком уже 2002 г. (речь идет о лекциях Е.В. Андреевой “Олимпиады по информатике: пути к вершине”). Учитывая этот факт, а также возросшую роль олимпиад (в частности — с точки зрения поступления в вузы), уверены, что эти статьи будут интересны нашим читателям, а многие сумеют непосредственно применить их в своей практической работе.

Организация ввода-вывода из файла для использования в олимпиадных задачах

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

В статьях мы будем рассматривать программы на Си и, при необходимости, на Паскале. В частности, мы рекомендуем использовать библиотеку stdio.h для реализации ввода-вывода в Си вместо iostream и других библиотек для работы с потоками, используемых в С++. Этот выбор связан со значительно более высокой производительностью библиотеки stdio.h.

Там, где это потребуется, мы будем давать пояснения к конструкциям языка Си, так, чтобы программирующие на Паскале (везде мы будем иметь в виду под языком Паскаль версию, реализованную в Delphi) имели возможность понимать приведенные листинги или даже перейти на язык Си при решении олимпиадных задач. Отметим, что комментарии будут касаться лишь специфичных, интуитивно не очевидных конструкций языка.

Итак, перейдем к рассмотрению организации ввода-вывода. Допустим, перед нами стоит задача сложить два целых числа, не превосходящих по модулю 10 000. Входные данные находятся в файле input.txt, вывод должен осуществляться в файл output.txt.

Рассмотрим программу на Си:

1. #include <stdio.h>

2. int main(void) {

3. int i, j;

4. freopen("input.txt", "r", stdin);

5. freopen("output.txt", "w", stdout);

6. scanf("%d%d", &i, &j);

7. printf("%d", i+j);

8. return 0;

9. }

В 4-й строке функция freopen перенаправляет стандартный поток ввода (stdin) на файл input.txt для чтения (r). Полностью аналогично в 5-й строке перенаправляется стандартный поток вывода.

Перейдем к рассмотрению программы на Паскале:

1. var

2. i, j : integer;

3. begin

4. assign(input, 'input.txt');

5. reset(input);

6. assign(output, 'output.txt');

7. rewrite(output);

8. read(i, j);

9. write(i+j);

10. end.

Здесь перенаправление ввода-вывода осуществляется с помощью строк 4–7. В 4-й строке поток стандартного ввода input перенаправляется в файл input.txt, а в 5-й строке файл открывается на чтение.

Стоит заметить, что при использовании этого метода нет необходимости использовать fclose или close для закрытия файлов, так как стандартные потоки закрываются автоматически в конце работы.

Для отладки достаточно закомментировать строки, перенаправляющие ввод-вывод в файл, и тогда программа будет считывать и выводить данные на консоль. Обратите внимание, что следует не забывать убрать комментарий перед отправкой решения на проверку.

0-символика. интуитивное понятие сложности алгоритма

Оценкой эффективности реализации решения принято считать время работы программы и количество используемой памяти. Стандартные сообщения тестирующей системы о превышении максимальных лимитов обычно носят вид TL (Time Limit exceed, превышен лимит времени) и ML (Memory Limit exceed, превышен лимит памяти).

Эффективность программы обычно определяется, исходя из сочетания времени работы программы и используемых ресурсов, причем важность каждого из компонентов определяется в зависимости от задачи. В случае же олимпиадного программирования следует использовать еще один решающий компонент оценки эффективности — время, затраченное на написание программы. Таким образом, наиболее эффективным решением олимпиадной задачи по информатике можно считать решение, укладывающееся в TL и ML, и написанное за кратчайшее время.

Основная часть времени работы программы состоит из произведения количества итераций цикла (т.е. сколько раз были выполнены действия) на время выполнения команд в цикле. Время выполнения условно будем называть “константой” (не зависящей от входных данных), а количество итераций — “сложностью” алгоритма. Допустим, алгоритм линейный, т.е., например, на вход дается N чисел, и следует подсчитать их сумму. Тогда сложность алгоритма будет обозначаться как O(N) (O-большое от N). Константа же для этой задачи может различаться в зависимости от конкретных условий. Например, для целых чисел константа будет в несколько раз меньше, чем для вещественных (т.к. целочисленные операции выполняются в несколько раз быстрее). Для квадратичного алгоритма (например, для сортировки пузырьком) сложность записывается как O(N²). Сложность может зависеть и от нескольких параметров, если они определяют количество циклов. Тогда сложность может записываться как O(N² + M³). Если в алгоритме нет циклов, зависящих от входных данных, то говорят, что он “работает за константу”, т.е. за O(1).

Обычно за O-большое обозначают сложность в худшем случае. Некоторые алгоритмы работают очень по-разному в зависимости от входных данных, в этом случае мы будем отдельно указывать “сложность в среднем”.

Очень часто в процессе подсчета сложности алгоритма используется функция logN (“логарифм от N”). В программировании мы обычно будем использовать двоичный логарифм по основанию 2. Он определяется так: 2^logN = N (соответственно, logN будет означать log₂N). Интересная особенность логарифма заключается в том, что он растет очень медленно при росте N. Так, при N = 8: logN = 3, N = 65 536: logN = 16, N = 4 294 967 296: logN = 32. Скорость роста логарифма намного меньше, чем даже у квадратного корня. Поэтому при больших значениях N алгоритм со сложностью logN и большой константой будет эффективнее линейного алгоритма с маленькой константой.

Целочисленные типы данных и их исподьзование

На данный момент на олимпиадах используются в основном 32-битные системы и компиляторы. Приведем таблицу, в которой указаны максимальные и минимальные значения для основных типов переменных:

Следует заметить, что операции с int64 выполняются несколько медленнее, чем с другими типами целочисленных данных.

При программировании следует стараться использовать тип int, кроме ситуации, когда использование другого типа позволит уложиться в ML или требуется заведомо больший тип данных.

Отметим некоторые особенности использования типа int64 в языке Си. Во-первых, в некоторых реализациях он обозначается как __int64, в некоторых других (в основном в UNIX-системах): long long. Кроме того, на различных платформах используется своя форматная строка для ввода-вывода int64. Универсальный вывод программируется с помощью макрокоманд и выглядит следующим образом:

#ifdef WIN32

printf("%I64d", n);

#else

printf("%lld", n);

#endif

Классический пример на тему выбора типа переменных выглядит так: даны два числа X и Y, по модулю меньшие, чем 231, следует вывести их сумму. Участник смотрит на данные, выбирает тип int и получает ошибку, так как результат сложения может не уместиться в этот тип данных.

Если же не хватает и этих переменных, то единственный выход — использование длинной арифметики, т.е. арифметики на массивах, которая рассматривается далее.

Длинные числа и операции над ними

При рассмотрении этой темы нам потребуются знания, полученные в начальной школе. В частности, выполнение арифметических операций “в столбик”.

Идея реализации длинных чисел заключается в использовании массивов чисел. Будем придерживаться соглашения, что числа прижаты к “правому краю”, т.е. младшие разряды стоят в ячейках с большим номером.

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

Удобнее всего определить один раз максимальное значение длины (количества элементов в массиве), чтобы можно было уменьшать его для более удобной отладки. Это делается с помощью следующей макроподстановки:

#define MAXLEN 1000

Мы определили максимальную длину массива в 1000 элементов. Программирующие на Паскале могут использовать константы (const).

Кроме того, удобно определить структуру для хранения числа:

typedef struct {

int val[MAXLEN+1];

int st;

} vlong;

Поле st будет указывать на ту позицию, с которой начинается осмысленная часть числа (т.е. начинаются отличные от нуля цифры; в дальнейшем мы увидим, что разумное использование этого поля избавляет нас от огромного количества бесполезных операций). Макроподстановка typedef делается для того, чтобы не писать каждый раз слово struct. Программирующие на Паскале могут использовать записи (record), программирующие на Си++ и Java могут создать класс и дальнейшие функции записывать в виде переопределенных операторов этого класса.

Вспомним, как осуществляется сложение в столбик. Мы начинаем идти с младших разрядов, складываем числа, стоящие на данных позициях, прибавляем то, что было “в уме”, новое значение “в уме” равно целой части от деления полученного результата на 10, в итоговое число на эту позицию — остаток от деления результата на 10. Так мы повторяем до тех пор, пока оба числа не кончатся (т.е. мы не дойдем до начала большего числа), в случае же, если “в уме” не ноль — мы дописываем эту цифру в начало. В реализации длинного сложения — все то же самое, только для экономии времени и места мы можем использовать, например, не систему счисления с основанием 10, а систему с основанием в 10 000 (для сложения мы можем выбрать и большее значение). Для реализации этого метода и, опять же, более удобной отладки удобно задать константу с основанием системы счисления:

#define SYS 10000

Перейдем собственно к описанию функции сложения:

void add(vlong *op1, vlong *op2, vlong *res) {

vlong *mxop, *mnop;

int i, flag=0, st;

mxop = op1->st>op2->st?op1:op2;

mnop = op1->st<=op2->st?op1:op2;

st=mnop->st;

for(i=MAXLEN; i >= mxop->st; i--) {

res->val[i] = mxop->val[i] + mnop->val[i] +

flag;

flag = res->val[i] / SYS;

res->val[i] %= SYS;

}

for(i=mxop->st-1; i >= mnop->st; i--) {

res->val[i] = mnop->val[i] + flag;

flag = res->val[i] / SYS;

res->val[i] %= SYS;

}

if (flag) res->val[--st] = flag;

res->st = st;

}

Сделаем некоторые пояснения к программе. Первым делом она выбирает большее и меньшее число (по количеству знаков). Здесь опять же полная аналогия со сложением чисел в столбик: пока у нас оба числа еще не кончились, мы складываем по всем правилам, а затем переписываем начало большего числа, не забывая про значение “в уме”.

Обычно большие числа инициализируются какими-либо малыми значениями, над которыми затем производятся операции, которые и приводят к росту этого числа. То есть короткое число надо записывать в x.val[MAXLEN], а x.st устанавливать в MAXLEN.

Если a, b и c — переменные типа vlong, то вызов функции должен выглядеть как add(&a, &b, &c). Это сделано для того, чтобы передавалось не само значение структуры, а указатель на нее (и не было необходимости в копировании).

Вывести значение длинного числа можно следующим образом:

printf("%d", c.val[c.st]);

for (i=c.st+1; i<=MAXLEN; i++)

printf("%.4d", c.val[i]);

Обратите внимание на то, что первое число выводится без ведущих нулей, а каждое следующее должно выводиться с ведущими нулями. При изменении базовой системы счисления (в нашем случае это 10 000) надо заменять цифру в выражении "%.4d" на количество нулей в основании этой системы. Просто выводить элементы массива с помощью "%d" нельзя! Такую ошибку достаточно легко допустить и очень сложно найти.

Сделаем некоторые комментарии для программирующих на Паскале. Во-первых, передача по указателю делается в Паскале с помощью указания ключевого слова var перед именем параметра в процедуре. Обращение к полям структуры, для которой есть указатель, осуществляется не как обычно через “.”, а через “->”.

Конструкция вида a=b<c?b:c на Си является сокращенной записью условия на Паскале

if b < c then

a := b

else

a := c;

Циклы на Паскале будут записываться как

for i := MAXLEN downto mxop.st do.

Предпоследние строки должны иметь следующий вид:

if flag <> 0 then begin

dec(st);

res.val[st] := flag;

end;

Сложность полученного алгоритма получилась O(n), где n — количество разрядов в большем числе. Если бы мы не использовали поля st, то нам каждый раз пришлось бы складывать все MAXLEN разрядов, а с учетом того, что очень часто используется не весь массив (в процессе вычисления числа растут, или мы не можем точно определить длину заранее), то сложность программирования оправдывается производительностью.

Длинное вычитание осуществляется аналогично. Используются те же идеи, что и в вычитании в столбик.

Теперь рассмотрим умножение длинного числа на короткое (коротким числом будем называть то, квадрат которого помещается в переменную элементарного типа, т.е. меньшее SYS). При этом функцию умножения на короткое будем писать сразу с прицелом на использование в умножении длинного на длинное.

void mul(vlong *op1, int sh, int offs,

vlong *res) {

int i, flag=0;

int st = op1->st;

for(i=MAXLEN-offs+1; i <= MAXLEN; i++)

res->val[i] = 0;

for(i=MAXLEN; i >= st; i--) {

res->val[i-offs] = op1->val[i] * sh +

flag;

flag = res->val[i-offs] / SYS;

res->val[i-offs] %= SYS;

}

if (flag) res->val[--st-offs] = flag;

res->st = st-offs;

}

Сложность алгоритма умножения длинного числа на короткое составляет O(n), где n — количество разрядов в длинном числе. С использованием двух предыдущих функций умножение длинного числа на длинное реализуется очень просто.

void mul_long(vlong *op1, vlong *op2,

vlong *res) {

int i;

vlong temp;

res->st = MAXLEN;

res->val[MAXLEN] = 0;

for (i=MAXLEN; i>= op1->st; i--)

{

mul(op2, op1->val[i], MAXLEN-i, &temp);

add(res, &temp, res);

}

}

Вызов функции mul(&x, sh, 0, &res), где x — это длинное число, sh — короткое, res — результат. Вызов функции умножения длинного числа на длинное осуществляется так: mul_long(&op1, &op2, &res), где op1 и op2 — длинные числа, а res — их произведение.

Инициализация значений и вывод осуществляется аналогично сложению.

Сложность умножения длинного числа на длинное получилась O(n х m), где n и m — количество разрядов в операндах. Существуют более быстрые методы умножения длинных чисел (например, метод Карацубы), однако в школьных олимпиадах их применение требуется крайне редко.

Длинное деление используется гораздо реже и реализуется аналогично делению в столбик. Длинные вещественные числа также оставим без внимания (интересующиеся могут найти способы хранения вещественных чисел в памяти компьютера и реализовать нечто подобное на массивах).

На этом закончим рассмотрение длинных чисел.

Простые и составные числа. Проверка простоты числа, разложение числа на два множителя

Напомним, что простым числом называется натуральное число, большее 1, которое делится нацело только на себя и 1 (имеет два натуральных делителя). Составными числами, соответственно, называются все остальные натуральные числа, большие единицы.

Простые числа имеют множество полезных применений, а также и сами по себе нередко являются сутью задачи. Наиболее известно применение простых чисел в шифровании RSA с открытым ключом.

В первую очередь нам необходимо уметь проверять, является ли число N простым. То есть нам необходимо узнать, существуют ли такие натуральные числа x, y (1 < x, y < N), что x х y = N. Кроме того, условимся, что x y, тогда можно сказать, что x меньше либо равен квадратному корню из числа N (если это условие не выполнено, то произведение будет заведомо больше N).

Таким образом, можно написать следующую функцию, которая будет довольно эффективно проверять число на простоту:

1. int isprime(int n) {

2. int i, j;

3. if (2 == n) return 1;

4. j = (int)sqrt((double)n) + 1;

5. for (i = 2; i <= j; i++)

6. if (!(n%i)) return 0;

7. return 1;

8. }

Для программирующих на Паскале следует знать следующие вещи: “!=” — это “не равно”, аналог “<>”; “%” — операция взятия остатка от деления, аналог mod; кроме того, любое значение, отличное от нуля, считается за истину, а 0 — за ложь. Таким образом, !0 — это истина.

Чтобы функция sqrt работала, необходимо подключить библиотеку math.h.

Пользуясь теми же соображениями, очень просто написать функцию, находящую все разложения числа на два множителя. Для этого достаточно убрать строку 3 и в строке 6 заменить return 0 на обработку двух найденных делителей i и n/i.

Оба этих алгоритма имеют сложность, пропорциональную квадратному корню.

Нахождение НОД и НОК с помощью алгоритма Евклида. Элементы теории остатков

Наибольшим общим делителем (НОД) двух натуральных чисел называется такое наибольшее натуральное число, которое является делителем и первого, и второго числа. Наименьшим общим кратным (НОК) двух натуральных чисел называется такое наименьшее натуральное число, которое делится нацело на оба этих числа.

Аналогично вводятся понятия НОД и НОК многих чисел. На практике НОД и НОК многих чисел считаются с помощью последовательного попарного подсчета НОД и НОК.

Задачи, в которых необходимо посчитать НОД или НОК, возникают довольно часто, особенно для НОД. Так, например, в подсчете количества точек с целыми координатами на отрезке используется НОД координат отрезка.

В курсе математики изучается алгоритм Евклида, который позволяет найти НОД двух чисел. В нем используются следующие соотношения:

1) НОД(a, 0) = a

2) НОД(a, b) = НОД(b, a%b,)

Запишем функцию подсчета НОД (GCD — Greatest Common Divisor):

int gcd(int a, int b) {

int c;

while (b) {

c = a % b;

a = b;

b = c;

}

return a;

}

Сложность алгоритма составляет O(logN), где N — наибольшее из чисел. На самом деле алгоритм часто работает даже быстрее.

НОК можно искать исходя из соотношения НОД(a, b)хНОК(a, b) = a х b.

В олимпиадных задачах довольно часто требуется найти что-либо “по модулю” какого-то числа. То есть посчитать остаток от результата проведения каких-либо операций. Здесь нам помогут следующие свойства остатков: (a+b)%n = (a%n +
+ b%n)%n и (a ґ b)%n = (a%n ґ b%n)%n. Эти свойства часто бывают полезными, так как обычно в задачах, где требуется посчитать остатки, возникают довольно большие числа, и уменьшение размерности операндов в промежуточных вычислениях намного облегчает задачу.

Также довольно часто требуется найти удовлетворяющий условию элемент какой-либо последовательности по модулю данного числа. В этом случае можно составить “таблицу умножения” по модулю n или другую таблицу с правилами перехода — это может значительно облегчить решение задачи.

Разложение числа на простые множители

Вернемся к простым числам. Любое число можно представить в виде произведения простых чисел, причем это представление будет единственно.

Обычно такое представление выглядит в виде одномерного массива, содержащего простые числа, и еще одного одномерного массива для непосредственного представления числа, в каждой ячейке которого содержится степень соответственного простого числа.

Например, пусть у нас есть массив простых чисел [2, 3, 5, 7, 11, 13], тогда массив с представлением числа 2600 будет выглядеть как [3, 0, 2, 0, 0, 1], из которого можно получить 2³ х 5² х 13¹ = 2600.

Такое представление неоправданно генерировать для одного числа (если это не является необходимым условием для решения задачи). Однако если чисел много, то приведение их в такое представление и обратно может быть весьма полезным.

Например, с помощью такого представления очень просто реализовать умножение. Рассмотрим наше число 2600 и число 11 858, которое представляется массивом [1, 0, 0, 2, 2, 0]. Чтобы получить произведение этих чисел, достаточно сложить соответствующие элементы массивов. Результатом будет массив [4, 0, 2, 2, 2, 1], т.е. 2⁴ х 5² х 7² х 11² х 13¹ = 30 830 800, что совпадает с результатом умножения.

Из этого представления также можно получить НОД и НОК этих чисел.

Для нахождения НОД надо выбирать минимум из степеней (это логично, так как число Xⁿ кратно X^k, если n k). Для подсчета НОК надо брать максимум из степеней. Этот же метод работает для произвольного количества чисел.

Для наших чисел 2600 и 11 858 НОД, подсчитанный таким образом, представим массивом [1, 0, 0, 0, 0, 0], т.е. равен 2, а НОК — массивом [3, 0, 2, 2, 2, 1] и равен 15 415 400. С помощью алгоритма Евклида несложно убедиться, что результат верен.

Кроме того, у разложения числа на простые множители существуют более специфичные назначения, которые встречаются в олимпиадных задачах.

Нахождение всех простых чисел до N занимает O(N) времени, подсчет степеней для одного числа занимает около O(N) времени (если степени не слишком большие), и операции умножения, нахождения НОД и НОК занимают также O(N) времени. Таким образом, суммарное время составляет около O(N + N х M), где N — максимальное из чисел, а M — количество этих чисел.

Быстрое возведение в степень

Довольно часто возникает задача быстрого возведения числа или другого объекта, для которого определена операция умножения, в какую-либо степень. Наивный алгоритм, когда мы просто нужное число раз умножаем число на само себя, имеет сложность O(N), где N — степень.

При возведении в степень число растет очень быстро (а значит, наверняка требуются операции с длинными числами). Поэтому научиться возводить число в степень быстрее, чем за O(N), достаточно важная задача.

Рассматривая степени некоторых чисел, можно догадаться о методе, которым следует пользоваться. Например, для возведения 3 в 4-ю степень нам нужно проделать 3 операции умножения. Однако если изменить порядок действий на такой: (3²)², то потребуется всего два умножения. Следует помнить, что при возведении числа в степени еще в какую-либо степень показатели степеней перемножаются. Именно на сокращении четных степеней основывается идея быстрого возведения в степень.

Приведем текст функции, которая возводит число a в степень n:

1. int pow(int a, int n) {

2. int b, c, k;

3. k = n;

4. b = 1;

5. c = a;

6. while (k)

7. if (!(k%2)) {

8. k /= 2;

9. c *= c;

10. } else {

11. k--;

12. b *= c;

13. }

14. return b;

15. }

Для программирующих на Паскале сделаем пояснения. В 8-, 9- и 12-й строках используется сокращенная запись. Они эквивалентны, соответственно, строкам k := k div 2; c := c * c; b := b * c;. В языке Си для целочисленного и вещественного деления используется один и тот же оператор “/”, а какие операнды он принимает, определяется из контекста. В строке 11 выполняется постфиксная операция декремента (в данном случае могла использоваться и префиксная операция декремента), в Паскале существует аналогичная операция dec(k) или k := k – 1.

Каждый раз, когда степень четная, мы возводим вспомогательную переменную в квадрат, а показатель степени делим на 2. Если число нечетное, то умножаем текущее вспомогательное число на результат и уменьшаем показатель степени на 1. Таким образом, хотя бы один раз из двух у нас произойдет уменьшение показателя степени вдвое, и, исходя из этого, мы получим сложность алгоритма O(logN).

Достижение такой сложности очень полезно, особенно при использовании медленных операций с длинными числами. Таким образом, можно выбрать “универсальный” рецепт: использовать быстрое возведение в степень везде, где показатель может превышать 100. С учетом того, что функция достаточно простая, можно использовать быстрое возведение в степень во всех случаях.

В англоязычной литературе алгоритм быстрого возведения в степень обзывают забавным словосочетанием “Russian peasant algorithm”, что переводится как “алгоритм русского крестьянина”.