В отличии от обычных программ, создаваемых
программистами повседневно, класс олимпиадных задач достаточно узок, но
практичен с точки критериев выявления способности участников программировать за
короткий срок. Как правило, олимпиадная задача представляет собой некоторую
проблему, для решения которой требуется использовать свой IQ почти на пределе,
однако, сам текст программы может быть совсем незначительным и помещаться на
одной странице.
Если человек не занимался программированием, то
предположительно можно оценить его способности к этой области в случае ее
изучения. Многие полагают, что способности программировать связаны с умением
решать математические и комбинаторные задачи. Другими словами, если у Вас в
школе твердая пятерка по алгебре, геометрии и иным математическим дисциплинам,
а так же умеете хорошо играть в шашки и шахматы, то вполне вероятно, что будете
неплохо программировать, если начнете этим заниматься. И наоборот, если в школе
у Вас тройка по алгебре, как бы вы не старались, то вряд ли программирование -
это то, чем Вам стоит заниматься. Так же следует отметить, что Ваши заслуги в
области освоения гуманитарных предметов мало Вам помогут в освоении
программирования, которое, как Вы уже поняли, относится к точным наукам.
Приведем условную классификацию олимпиадных задач:
- Арифметика -
математические задачи, работа с большими числами (длинная арифметика),
такие задачи, как правило, требуют знания формул, умение их применять, а
код программ может быть небольшим
- Геометрия -
геометрические задачи, здесь может быть описана какая либо ситуация
взаимодействия тел на плоскости и в пространстве
- Динамическое
программирование - задачи, направленные на выявление рекуррентных
соотношений
- Сортировка и
последовательности - работа с данными, представленными в виде
массива
- Графы -
задачи с графами (структурами данных, основаных на вершинах и ребрах)
- Рекурсия -
задачи на поиск с рекурсивным перебором вариантов
Конечно же, задачи могут сочетать в себе сразу несколько направлений, и
часто бывает сложно конкретную задачу отнести к тому или иному разделу.
Любая олимпиадная задача подразумевает входные и
выходные данные. Т.е. в формулировке задания обязательным образом описан формат
входных и выходных данных, а Ваша программа должна считать эти данные,
обработать и вывести результат в установленном формате. Чаще всего чтение
происходит из некоторого файла INPUT.TXT, а вывод в некоторый файл OUTPUT.TXT .
Т.е. для решения олимпиадных задач нужно уметь работать с файлами: читать,
создавать и писать в них, а вот знания графических функций вряд ли Вам
пригодятся. Стоит заметить, что многие системы, например http://acm.timus.ru, используют консольный
режим ввода-вывода и работа с файлами в них не приветствуется. Помимо условия
задачи, правил ввода и вывода информации на каждую задачу накладываются
ограничения на время выполнения и используемую Вашей программой оперативную
память.
При решении олимпиадных задач необходимо уметь
работать с текстовыми файлами, т.к. от участника олимпиады, как правило,
требуется написать программу, которая считывает некоторые данные из одного
файла, производит определенные вычисления, а результат выводит в другой файл.
Для работы с файлами как в языке Паскаль, так и в
языке Си можно обойтись без использования файловых переменных. Добавив две
строчки кода в программу, можно перенаправить ввод данных с консоли на ввод из
файла, а вывод на экран заменить на вывод в файл. Следующие фрагменты кода
реализуют данную возможность:
// Язык Си
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
{Язык Паскаль}
assign(input, 'input.txt'); reset(input);
assign(output, 'output.txt');
rewrite(output);
В этой теме мы предлагаем решить простейшие задачи,
которые помогут ознакомиться с вводом-выводом данных. Подобные задачи обычно
используются на пробных турах олимпиад по программированию.
Задача 1: Неглухой телефон
(Время: 1 сек. Память: 16 Мб
Сложность: 1%)
Возможно, что Вы когда то
играли в игру «Глухой телефон», либо слышали о ней. В этой игре участникам
приходится передавать информацию друг другу различными способами: словесно,
образно, бывает даже приходится писать левой рукой текст, который другой участник
команды должен будет прочитать. Так же известно, что практически никогда
передаваемая информация не доходит до конечного адресата. Обозначим за Fi(x)
функцию, которая преобразует текст передаваемой информации x в ту, которую
получит участник i+1 от участника i. Тогда последний n-й участник получит
данные y, которые будут выражаться следующей формулой:
y = Fn-1(Fn-2(…F2(F1(x))))
Но Вам необходимо исключить
какие-либо внешние факторы, которые могут исказить исходную информацию и Вы
должны реализовать программу «неглухой телефон», которая сможет безошибочно
доставлять исходные данные, т.е. в нашем случае функция Fi(x) = x
для всех i от 1 до n-1.
Входные данные. В единственной
строке входного файла INPUT.TXT записано натуральное число от 1 до 100.
Выходные данные. В выходной
файл OUTPUT.TXT нужно вывести в точности то же число, которое задано во входном
файле.
Пример
№
|
INPUT.TXT
|
OUTPUT.TXT
|
1
|
5
|
5
|
Задача 2: Два бандита (Время: 1 сек. Память: 16 Мб Сложность: 4%)
Бандиты
Гарри и Ларри отдыхали на природе. Решив пострелять, они выставили на бревно
несколько банок из-под пива (не больше 10). Гарри начал простреливать банки по
порядку, начиная с самой левой, Ларри — с самой правой. В какой-то момент
получилось так, что они одновременно прострелили одну и ту же последнюю банку.
Гарри
возмутился и сказал, что Ларри должен ему кучу денег за то, что тот лишил его
удовольствия прострелить несколько банок. В ответ Ларри сказал, что Гарри
должен ему еще больше денег по тем же причинам. Они стали спорить, кто кому
сколько должен, но никто из них не помнил сколько банок было в начале, а искать
простреленные банки по всей округе было неохота. Каждый из них помнили только,
сколько банок прострелил он сам.
Определите
по этим данным, сколько банок не прострелил Гарри и сколько банок не прострелил
Ларри.
Входные данные. В единственной
строке входного файла INPUT.TXT записано 2 числа — количество банок,
простреленных Гарри и Ларри соответственно.
Выходные данные. В файл
OUTPUT.TXT выведите 2 числа — количество банок, не простреленных Гарри и Ларри
соответственно.
Пример
№
|
INPUT.TXT
|
OUTPUT.TXT
|
1
|
4 7
|
6 3
|
Задача 3: Журавлики (Время: 1 сек. Память: 16 Мб Сложность: 7%)
Петя, Катя и Сережа делают из бумаги журавликов.
Вместе они сделали S журавликов. Сколько журавликов сделал каждый ребенок, если
известно, что Петя и Сережа сделали одинаковое количество журавликов, а Катя
сделала в два раза больше журавликов, чем Петя и Сережа вместе?
Входные данные. В единственной строке входного файла INPUT.TXT записано
одно натуральное число S – общее количество сделанных журавликов (S < 106).
Выходные данные. В единственную строку выходного файла OUTPUT.TXT нужно
вывести три числа, разделенных пробелами – количество журавликов, которые
сделал каждый ребенок (Петя, Катя и Сережа).
Примеры
№
|
INPUT.TXT
|
OUTPUT.TXT
|
1
|
6
|
1 4 1
|
2
|
24
|
4 16 4
|
3
|
60
|
10 40 10
|
Задача 4: Игра (Время: 1 сек. Память: 16 Мб Сложность: 4%)
В свободное время одноклассники Вася и Петя любят
играть в различные логические игры: морской бой, крестики-нолики, шахматы,
шашки и многое другое. Ребята уже испробовали и поиграли во всевозможные
классические игры подобного рода, включая компьютерные. Однажды им захотелось
сыграть во что-нибудь новое, но ничего подходящего найти не удалось.
Тогда Петя придумал следующую игру «Угадайка»:
Играют двое участников. Первый загадывает любое трехзначное число, такое что
первая и последняя цифры отличаются друг от друга более чем на единицу. Далее
загадавший число игрок переворачивает загаданное число, меняя первую и
последнюю цифры местами, таким образом получая еще одно число. Затем из
максимального из полученных двух чисел вычитается минимальное. Задача второго игрока
– угадать по первой цифре полученного в результате вычитания числа само это
число. Например, если Вася загадал число 487, то перестановкой первой и
последней цифры он получит число 784. После чего ему придется вычесть из 784
число 487, в результате чего получится число 297, которое и должен отгадать
Петя по указанной первой цифре «2», взятой из этого числа. Петя успевает лучше
Васи по математике, поэтому практически всегда выигрывает в играх такого типа.
Но в данном случае Петя схитрил и специально придумал такую игру, в которой он
не проиграет Васе в любом случае.
Дело в том, что придуманная Петей игра имеет
выигрышную стратегию, которая заключается в следующем: искомое число всегда
является трехзначным и вторая его цифра всегда равна девяти, а для получения
значения последней достаточно отнять от девяти первую, т.е. в рассмотренном
выше случае последняя цифра равна 9-2=7. Помогите Пете еще упростить процесс
отгадывания числа по заданной его первой цифре, написав соответствующую
программу.
Входные данные. В единственной строке входного файла INPUT.TXT задана
единственная цифра К, соответствующая первой цифре полученного Васей в
результате вычитания наименьшего загаданного Васей значения из наибольшего.
Выходные данные. В выходной файл OUTPUT.TXT нужно вывести значение
полученной Васей разности.
Примеры
№
|
INPUT.TXT
|
OUTPUT.TXT
|
1
|
5
|
594
|
2
|
2
|
297
|
3
|
7
|
792
|
Немає коментарів:
Дописати коментар