Несколько советов участникам олимпиад
Прежде всего хотим отметить, что для участия в олимпиаде вы должны уметь работать с текстовыми файлами (считывать и записывать информацию): это не сложно - скорее всего, вы с легкостью разберетесь, как это делается, посмотрев приведенный ниже пример. Однако лучше всего попробовать работать с файлами до того, как вы придете на олимпиаду. Если вы участвуете в олимпиаде впервые, советуем вам также заранее посмотреть примеры предлагаемых на олимпиадах задач, например, в архивах олимпиад, представленных на нашем сайте.
На олимпиадах, если иное не указано в условии задачи, все входные данные считаются корректными, то есть файлы, которые подаются на вход вашей программе при проверке строго соответствуют описанным в условии форматам, а все значения - указанным ограничениям. Вы не должны в своей программе проверять корректность входных данных. С другой стороны, выходные данные (результат работы вашей программы) вы должны выводить в формате, описанном в условии задачи, не добавляя никаких посторонних комментариев. Все решения проверяются автоматически, и если выходной файл содержит постороннюю информацию или если его формат не соответствует описанному в условии, он будет признан неправильным.
Ваша программа не должна ничего выводить на экран (если это особо не оговорено в условии задачи), а также ждать какого-либа ввода пользователя. Распространенной ошибкой является ситуация, когда после окончания работы программа ждет нажатия какой-либо клавиши. При автоматической проверке никто эту клавишу нажимать не будет, и программа будет считаться превысившей предел времени (то есть зависшей или неэффективной).
Что делать, если ваше решение проходит не все тесты
Давайте для начала рассмотрим один простой пример. Решим следующую задачу. Во входном файле a.in записаны два натуральных числа, каждое из которых не превышает 32000. Числа во входном файле разделяются пробелами и (или) символами перевода строки. В выходной файл a.out вывести сумму этих двух чисел.
Кажется, что это даже не задача, и любой знакомый с программированием школьник с легкостью может написать ее решение:
var a,b,c:integer;
f,g:text
begin
assign(f,'a.in'); {Связываем переменную f с файлом a.in}
reset(f); {Открываем файл, связанный
с переменной f для чтения}
read(f,a,b); {Считываем данные из файла, связанного с f}
close(f); {Закрываем файл}
c:=a+b; {Решаем задачу :-) }
assign(g,'a.out'); {Связываем переменную g с файлом a.out}
rewrite(g); {Открываем файл, связанный
с переменной g для записи}
writeln(g,c); {Записываем данные в файл}
close(g); {Закрываем файл}
end.
Кажется, что все правильно. На всякий случай запустим нашу программу, чтобы еще раз убедиться, что она работает правильно. Посылаем ее на проверку, и получаем неожиданный результат - несколько тестов прошло, но на некоторых тестах происходит ошибка во время исполнения (или неверный ответ - это зависит от ключей компилятора). Давайте еще раз внимательно прочитаем условие, и особо остановимся на ограничениях. Числа натуральные, не превышающие 32000. У нас для хранения чисел заведены переменные типа integer, диапазон значений переменных этого типа - от -32768 до 32767, так что кажется, что тут все правильно. Однако условию удовлетворяет тест, в котором оба числа равны 32000. Конечно, они входят в тип integer, чего нельзя сказать об их сумме! Меняя в нашей программе тип integer на тип longint получаем уже действительно полное решение задачи (замечание: оказывается, если сделать тип переменной c - longint, а a и b оставить типа integer, то программа работать все равно не будет - подумайте почему).
Таким образом, первый совет, который хочется дать - всегда внимательно читать условие и обращать самое пристальное внимание на ограничения, при этом учитывать не только ограничения на входные данные, но и задумываться о том, какие из них следуют ограничения на выходные данные и промежуточные результаты.
Ограничения важны еще с одной точки зрения. Задумайтесь - а сколько действий выполнит ваша программа в самом худшем случае. Успеют ли все эти действия выполниться за время, отведенное на работу программы на одном тесте? Если ответ заведомо отрицательный - попытайтесь как-то улучшить свой алгоритм, или даже придумать новый.
Обязательно перед сдачей решения проверьте его самостоятельно, введя тесты, приведенные в условиях задач, и придумав свои. Хорошо бы потестировать задачу не только на маленьких тестах, но и на максимальных, удовлетворяющих ограничениям. Это позволит найти ошибки, приводящие к переполнению типов, выходу индекса за границы массива. Эти же тесты дают возможность проверить, укладывается ли ваше решение в ограничения по времени, указанные в условии задачи.
Если вы осуществили все такие проверки, а задача все равно не проходит какие-то тесты, подумайте, быть может, вы не учли какой-то из частных случаев задачи.
Если решение не проходит ни одного теста
Если вы послали решение, которое у вас работает, а оно не прошло ни одного теста, проверьте, правильно ли в вашем решении называются входной и выходной файлы, соблюдены ли форматы входных и выходных данных, заканчивает ли ваша программа свою работу (например, не ждет ли она нажатия клавиши "Enter")? Обратите внимание, имена входного и выходного файла должны писаться маленькими буквами (под Windows это не имеет значения, однако ваши решения проверяются под Linux, а там это существенно).
Ваша программа всегда должна завершаться с кодом возврата 0. То есть функция main в C/C++ должна иметь тип результата int и всегда завершаться командой return 0, если вы используете в паскале процедуру выхода halt, то вы всегда должны делать halt(0) - другие значения недопустимы и диагностируются как Run-time error.
Если вы не знаете, как решать задачу
Если вы не знаете, как решать задачу при указанных ограничениях или в общем случае, но ваша программа работает в каких-то частных случаях, обязательно пошлите ее на проверку - быть может несколько тестов она все-таки пройдет, а любой положительный результат - это лучше, чем ничего.
Занятие 1. Знакомство с олимпиадными задачами.
На этом занятии мы рассмотрим несколько примеров олимпиадных задач. Представленные здесь задачи не требуют никаких специальных знаний для своего решения, а лишь немного сообразительности.
Задача 01-1. Задача Иосифа Флавия
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
3 секунды
|
Существует легенда, что Иосиф Флавий - известный историк первого века - выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным - он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю.
В нашем варианте мы начнем с того, что выстроим в круг N человек, пронумерованных числами от 1 до N, и будем исключать каждого k-ого до тех пор, пока не уцелеет только один человек. (Например, если N=10, k=3, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним - 5-й, и потом 10-й. Таким образом, уцелеет 4-й.)
Задача: определить номер уцелевшего.
Формат входных данных
Во входном файле даны натуральные числа N и k. 1 <= N <= 500, 1 <= k <= 100.
Формат выходных данных
Выходной файл должен содержать единственное число - номер уцелевшего человека.
Пример
input.txt
|
output.txt
|
10 3
|
4
|
Рассмотрим два способа решения задачи. Давайте повторим в памяти компьютера события, происходившие в легенде.
Способ первый. Будем хранить в массиве имена (то есть номера) всех живых на текущий момент воинов. Причем удобно, чтобы номера людей были записаны в элементах массива с 0 по N-1 (чуть позже станет ясно, почему так). Когда воин будет умирать, будем удалять его из массива, и тех, кто стоял за ним, "сдвигать" на один элемент влево.
Заметим, что если мы уже убили L человек, то в живых осталось M=N-L. Пусть мы только что (на L-ом шаге) убили человека, который был записан в нашем массиве в элементе с номером j (и сдвинули людей, которые были записаны в массиве в элементах с j+1 по M на один элемент влево). Тогда следующим нужно убивать человека, который записан в этом массиве в элементе с номером (j+k-1) mod M. (Запись a mod b обозначает остаток от деления числа a на b).
Взятие остатка от деления на M нужно затем, чтобы как бы "замкнуть" наш массив в круг (то есть как только мы достигаем конца массива, мы оказываемся в его начале). Вот тут как раз и важно, что люди в массиве у нас расположены начиная с 0-го элемента - операция взятия остатка от деления на M может дать в качестве результата числа от 0 до M-1. Конечно, можно изначально расположить людей и начиная с 1-го элемента, однако тогда в этом месте формула окажется несколько сложнее.
Способ второй. Заведем массив, где будем помечать мертвых воинов (т.е. в i-м элементе хранится, жив воин i, или уже нет). Пусть у нас на текущем шаге M живых людей и на предыдущем шаге умер воин j. Чтобы найти следующего, будем бежать по массиву, отсчитывая живых и пропуская мертвых. Тот человек, на котором мы насчитаем k mod M и должен умереть следующим. Почему k mod M, а не k? Считалочка сначала проидет k div M полных кругов, а затем остановится на человеке k - (k div M) * M = k mod M. Если k mod M оказалось равно 0, то нужно найти ближайшего живого, считая назад, либо (что то же самое) M-го, считая вперед. Через N - 1 шаг останется один человек.
Задача 01-2. Сортировка времени
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
3 секунды
|
Формат входных данных
Во входном файле записано сначала число N (1 <= N <= 100), а затем N моментов времени. Каждый момент времени задается 3 целыми числами - часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60).
Формат выходных данных
В выходной файл выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не обязательно)
Пример
input.txt
|
output.txt
|
4
10 20 30
7 30 00
23 59 59
13 30 30
|
7 30 0
10 20 30
13 30 30
23 59 59
|
Давайте хранить время в секундах, прошедших с начала дня. Преобразование из обычного времени в такое и обратно не представляет труда (подумайте, как это можно сделать). Но теперь время представлено одним числом и к массиву применима обычная сортировка.
Задача 01-3. Большая сортировка
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
3 секунды
|
Формат входных данных
Дано число N (1 <= N <= 100000), а затем N натуральных чисел из диапазона от 1 до 100.
Формат выходных данных
Выведите N чисел в неубывающем порядке
Пример
input.txt
|
output.txt
|
5
3 1 2 4 2
|
1 2 2 3 4
|
Подсчитаем, сколько раз каждое из натуральных чисел из диапазона от 1 до 100 входит в нашу последовательность. Далее выведем число 1 столько раз, сколько оно встречается во входной последовательности, затем 2 и так далее.
Такой метод сортировки совершает порядка N действий, но он применим только тогда, когда различных чисел во входном массиве может быть очень небольшое количество.
Занятие 2. Метод динамического программирования.
Метод динамического программирования позволяет решать задачи, переборное решение которых работает слишком долго. Идея этого метода заключается в сведении задачи к нескольким меньшим подзадачам, которые в свою очередь разбиваются на меньшие подзадачи. Результаты решения подзадач записываюся в массив и, благодаря этому, никакая подзадача не решается дважды. Давайте рассмотрим применение этого метода на конкретных примерах.
Задача 02-1. Минимальный путь в таблице
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
3 секунд
|
В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).
Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.
Формат входных данных
Во входном файле задано два числа N и M - размеры таблицы (1 <= N <= 20, 1 <= M <= 20). Затем идет N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100).
Формат выходных данных
В выходной файл запишите минимальную сумму, потратив которую можно попасть в правый нижний угол.
Пример
input.txt
|
output.txt
|
3 4
1 1 1 1
5 2 2 100
9 4 2 1
|
8
|
Будем решать более общую задачу (что, как ни странно, зачастую оказывается проще), а именно найдем цену bi,j минимального пути из правой верхней клетки в клетку (i,j). Заметим, что попасть в клетку (i,j) мы могли только из клеток (i-1,j) и (i,j-1). Значит, задачу можно свести к решению подзадач для клеток (i-1,j) и (i,j-1).
Результаты решения подзадач удобно хранить в таблице b размером NxM. Тогда bi,j=min(bi-1,j,bi,j-1)+ai,j ( здесь a - таблица из условия). Применить эту формулу не составляет труда, если bi-1,j и bi,j-1 уже посчитаны. А это легко достигается, если заполнять таблицу b слева направо сверху вниз (т.е. сначала слева направо заполняется первая строка, затем вторая и т.д.). Заметим, что для первой строки и первого столбца формула работает плохо, т.к. там появляются несуществующие элементы таблицы. Их можно заполнить в самом начале, поскольку в каждую из этих клеток можно попасть только одним способом. Ответ на поставленную задачу будет находиться в правом нижнем углу таблицы b.
Количество действий, выполненных этим алгоритмом, пропорционально числу клеток в таблице.
Задача 02-2. "Гвоздики"
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
3 секунды
|
На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.
Формат входных данных
В первой строке входного файла записано число N - количество гвоздиков (1 <= N <= 100). В следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).
Формат выходных данных
В выходной файл нужно вывести единственное число - минимальную суммарную длину всех ниточек.
Пример
input.txt
|
output.txt
|
5
4 10 0 12 2
|
6
|
Сначала отсортируем гвоздики по возрастанию координат. Решим следующую подзадачу: найдем минимальную длину веревочек, необходимую для того, чтобы связать первые k гвоздиков согласно условию (обозначим требующуюся для этого длину веревочек ak).
Можно считать, что любая ниточка связывает два соседних гвоздика (иначе ее можно разрезать на несколько частей, связывающих все гвоздики между теми, которые связывала наша ниточка изначально).
Научимся вычислять ak. Заметим, что в оптимальной конфигурации (для первых k гвоздиков) между последним (k-м) и предпоследним ((k-1)-м) гвоздиками ниточка есть всегда, а вот между предпоследним ((k-1)-м) и предпредпоследним ((k-2)-м) она может либо быть, либо не быть. В первом случае первые k-1 гвоздиков удовлетворяют условию задачи, во втором - первые k-2. Значит ak=min(ak-1,ak-2)+lk-1,k, где lk-1,k - расстояние между k-м и k-1-м гвоздиками (в отсортированном массиве). Для удобства вычислений удобно ввести фиктивные первый и нулевой элементы равные 0 и бесконечности соответственно (в реальной программе в роли бесконечности обычно выступает какое-нибудь достаточно большое число, например для данной задачи вполне подойдет 30000). Теперь последовательно заполняя массив a с помощью данной формулы, мы получим верный ответ на поставленную задачу в элементе aN.
Число действий, выполненных данным алгоритмом, пропорционально N.
Задача 02-3. "Подпоследовательности"
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
3 секунды
|
Дана последовательность, требуется найти длину наибольшей возрастающей подпоследовательности.
Формат входных данных
В первой строке входного файла записано число N - длина последовательности (1 <= N <= 1000). Во второй строке записана сама последовательность (через пробел). Числа последовательности - целые числа, не превосходящие 10000 по модулю.
Формат выходных данных
В выходной файл требуется вывести наибольшую длину возрастающей подпоследовательности.
Пример
input.txt
|
output.txt
|
6
3 29 5 5 28 6
|
3
|
Пусть c1,c2, ... ,cn, - данная последовательность. Покажем, как найти длину максимальной возрастающей подпоследовательности, заканчивающуюся в элементе ck (обозначим ak). Предположим, она уже найдена. Удалим из нее последний элемент. Полученная подпоследовательность является максимальной возрастающей подпоследовательностью, оканчивающейся в некотором элементе cj (j < k). Значит, либо ak = max{j < k, cj < ck}{aj} + 1, либо ak = 1, если таких j не существует. Ответом на поставленную задачу будет максимум из всех ak.
Число действий, выполненных данным алгоритмом, пропорционально N2.
Задача 02-4. "Лесенки"
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
3 секунды
|
Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем предыдущий.
---
| |
---------
| | | | |
-----------
| | | | | |
-----------------
| | | | | | | | |
-----------------
Подсчитать число лесенок, которое можно построить из N кубиков.
Формат входных данных
Во входном файле записано число N (1 <= N <= 100).
Формат выходных данных
В выходной файл вывести искомое число лесенок.
Пример
Переформулируем нашу задачу на язык математики. В каждом следующем слое (считая сверху вниз) кубиков больше, чем в предыдущем, а в сумме их n. Значит, нам требуется представить n в виде суммы возрастающих натуральных слагаемых.
---
1 | |
---------
4 | | | | |
-----------
5 | | | | | |
-----------------
8 | | | | | | | | |
-----------------
n=1+4+5+8
Пусть в качестве первого слагаемого мы взяли L, тогда нам требуется n-L разбить на слагаемые. Но теперь добавляется дополнительное условие - слагаемые должны быть больше либо равны L+1. Значит, нам достаточно научиться считать число разбиений числа n на слагаемые не меньшие k (обозначим an,k). Есть два случая: слагаемое k либо входит в разбиение (таких способов an-k,k+1), либо нет (таких способов an,k+1). Так как никакое разбиение не подходит одновременно под оба эти случая, то an,k=an-k,k+1+an,k+1 Заметим, что для единицы существует единственное разбиение: 1 = 1. Значит a1,0 = a1,1 = 1, a1,f = 0, где f >= 2. an,k удобно вычислять в порядке невозрастания k. При равных k - в произвольном порядке.
Данный алгоритм выполняет порядка N2 действий.
Занятие 3. Метод динамического программирования (продолжение).
На прошлом занятии мы рассмотрели несколько задач на метод динамического программирования. Решения, не сложные в написании, порой напоминали какие-то фокусы, которые непонятно как придумать. Умение видеть, какие дополнительные параметры нужно ввести в задачу приходит с опытом. Поэтому давайте рассмотрим еще несколько примеров задач на динамическое программирование.
Задача 03-1. Восстановление скобок
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
3 секунды
|
Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.
|