Материалы для подготовки к олимпиадам по программированию.
Начнем с того, что олимпиады по информатике отличаются от всех прочих, например, олимпиад по физике или математике. Если там мы решаем на бумаге задачи, а потом жюри оценивает решения и ставит определенное количество баллов, то здесь система оценки принципиально иная. Отличаются также и принципы решения.
Во-первых, вы ничего не пишете на русском языке. Все решения записываются сразу на компьютере (без бумаги) и сразу на языке программирования. Конечно, черновые записи делаются на бумаге, но это производится на усмотрение самого участника и не влияет на его оценку. Важно, что в решении могут использоваться любые математические свойства и закономерности, и вам нет нужды их доказывать. Если вы уверены, что какое-то простое, за минуту придуманное правило позволяет верно решить задачу, записывайте его, и истина вас рассудит: если идея была верной, такое решение будет оценено независимо от того, доказывали вы для себя это правило или нет.
Во-вторых, проверка решений на таких олимпиадах обычно является, в своем роде, самой справедливой и самой несправедливой. (Вообще-то программистских олимпиад много, и есть среди них и такие, к которым этот пункт не относится, но в дальнейшем речи о них идти не будет.) Дело в том, что жюри не смотрит вашу программу, а проверяет ее (обычно в автоматическом режиме, с помощью компьютера) на тестах. Вообще, по условию задач, в программу вводятся некие входные данные, она их обрабатывает и выдает ответ. Тесты жюри — это варианты входных данных и соответствующих правильных ответов. При тестировании жюри «подсовывает» вашей программе свои тесты, а затем проверяет, правильный ли ответ ваша программа выдает. Справедливость (по сравнению с проверкой задач по математике, физике) здесь заключается в том, что от решения требуется только одно — правильность, соответствие условиям, только то, не требовать чего было бы нельзя. Неважно, понятно решение или нет, если оно работает. Неважно, каким способом вы получили ответ, если он правильный. В любом случае вы получите причитающиеся баллы. Несправедливость же здесь в том, что за глупую ошибку, вроде тех, за которые снимают 1—2 балла на других олимпиадах, здесь задача может вполне быть аннулированной. Далее мы подробно рассмотрим популярные ошибки и методы борьбы с ними.
Есть два основных подхода к оценке решений. При одном подходе, который я буду далее называть «Пан или пропал», задача либо получает максимум баллов, если все тесты успешно пройдены, либо 0, если хотя бы на одном из тестов она «завалилась». Так чаще всего оценивают на командных олимпиадах. На большинстве других олимпиад, в том числе обычных школьных (на всех этапах: городском, региональном и более крупных), используется более гуманная система оценки. Проверочные тесты имеют определенный вес в баллах. Если тест пройдет, то эти баллы прибавляются к счету участника. Бывает дополнительный «бонус», то есть баллы, которые начисляются, только если все тесты пройдены. Действия олимпиадника различаются в двух этих случаях (особенно, если задачи сложные), но об этом речь пойдет позже.
Чтобы программа прошла тест, она должна не просто выдать правильный ответ, но еще и справиться с этим за определенное время, указанное в условии задачи. (Помимо этого, там указывается максимальная память, но ее в любом случае трудно превысить на TP, а кто пишет на более совершенных языках, тот сориентируется сам.) Дело здесь в том, что многие задачи можно решить простым алгоритмом, который работает слишком долго, и поэтому на больших тестах простой алгоритм будет нерабочим. Грубо говоря, чем оптимальнее (практически — быстрее) работает алгоритм, тем больше баллов (при «гуманном» подходе) получит участник на данной задаче. На всех серьезных олимпиадах решения тестируются автоматически, с помощью специальной программы, поэтому нужно следить за корректностью вывода. Личность участника тестирующая программа идентифицирует по имени файла, содержащего решение, поэтому ошибка в имени файла аннулирует задачу — будьте внимательны.
3 декабря в Башкортостане прошел 2 муниципальный этап олимпиады школьников по информатике.
Привожу тексты задач. Интересно, какими были задачки в других регионах?
a.in
|
a. out
|
12 31 25
|
12 13
|
12 31 26
|
0
|
101 2 13
|
11 2
|
b.in
|
b. out
|
5 7 -47 6 -193 5
7 9 14 5485 -193
|
8
-193 -47 5 6 7 9 14 5485
|
1 1 1 1 1 1 2 2 2 2
|
2
1 2
|
1
2
3
1
2
3
|
3
1 2 3
|
c.in
|
c.out
|
8
0 1 3 5 2 0 0 0
5
|
3
|
10
0 2 5 3 4 0 0 0 0 0
2
|
0
|
2
2 1
1
|
2
|
d.in
|
d.out
|
5
|
14
|
e.in
|
e.out
|
ADD 10 20
ADD 5 15
DEL 7
ADD 3 7
DEL 4
DEL 5
END
|
20
6
0
|
Вложение | Размер |
---|---|
![]() | 80 КБ |
5 декабря прошел второй этап (районный) олимпиады школьников по информатике. Министерством образования республики задачи олимпиады были высланы в 9 часов утра в день олимпиады на почтовые ящики отделов образования (дублируются на ящики отвественных за проведение олимпиады). Условия задач тут же были размножены и в 10 ч школьники приступили к решению. Всего 6 задач. Решения учащихся проверялись спец. программой и высылались в жюри, которое будет подводить итоги по республике (общий рейтинг). В этом году изменились правила проведения олимпиады, на региональный этап будут приглашены первые 70 учащихся в данном рейтинге.
Не секрет, что большинство учащихся в школе тему "Программирование" изучают в небольшом количестве и на олимпиаде большинство получают НУЛЬ. Поэтому нашим жюри несколько задач олимпиады были подобраны на их уровень. Таким образом количество нулевых баллов в нынешнем году было меньше.
Задачи во вложении. Task_2_2008.doc
Программа тестирования решений Test_2008.zip
Вложение | Размер |
---|---|
![]() | 79.5 КБ |
![]() | 453.05 КБ |
Вложение | Размер |
---|---|
![]() | 143 КБ |
Вложение | Размер |
---|---|
![]() | 86 КБ |
Выкладываю задачки с олимпиады по программированию в Башкортостане, который прошел 23 ноября 2010 года. Для печати смотрите вложение.
Задача 1. " Сдача" (100 баллов)
Имя входного файла: | a.in |
Имя выходного файла: | a.out |
Ограничение времени | 1 секунда на тест |
Ограничение по памяти | 64 Мб |
Когда Маша и Витя покупали подарок, возникла интересная ситуация. У них была в распоряжении только одна большая купюра, а у продавца – некоторое количество мелочи. Дело происходило утром, поэтому продавцу нужно было экономить мелочь, и он хотел отдать сдачу минимальным количеством монет. Подумав некоторое время, он точно определил, с каким количеством монет ему придется расстаться.
А Вы сможете решить такую задачу?
Формат входного файла.
В первой строке входного файла записано целое число N (1<=N<=10) – количество различных номиналов монет, содержащихся в кассе. Можно считать, что количество монет каждого номинала достаточно.
В следующей строке содержится n целых чисел аi (0<ai<2000) –номиналы монет.
В третьей строке записано одно число k (1 <= k <=1000000) – сумма, которую нужно набрать
Формат выходного файла.
В выходной файл запишите минимальное количество монет, которое придется отдать продавцу, или -1, если продавец вообще не сможет сдать покупателям сдачу.
Примеры файлов входных и выходных данных:
a.in | a.out |
3 1 3 5 13 | 3 |
a.in | a.out |
4 5 6 7 8 9 | -1 |
Задача 2. «Приказ об отчислении» (50 баллов)
Имя входного файла: | b.in |
Имя выходного файла: | b.out |
Ограничение времени | 1 секунда на тест |
Ограничение по памяти | 32 Мб |
В Тьмутараканском университете имени Кота Матроскина начинается очередное отчисление студентов за неуспеваемость. Для отчисления неуспевающих студентов каждой группы готовится отдельный приказ. Более того, теперь ректор требует, чтобы в одном приказе перечислялись только студенты, которые занимают некоторое количество подряд идущих строчек в лексикографически упорядоченном списке группы. Так, если в некоторой группе подлежат отчислению студенты, значащиеся в списке под номерами 1, 2, 5, 7, 8 и 9, то должно быть изготовлено не менее трёх приказов: об отчислении студентов 1 и 2, об отчислении студента 5, об отчислении студентов 7, 8 и 9. Напишите программу, которая находит минимальное количество приказов об отчислении.
Формат входного файла.
В первой строке входного файла записано целое число N – количество отчисляемых студентов (0 <= N <= 106). Во второй строке записаны номера неуспевающих студентов в списке группы S1, S2, …, SN (1 <= Si <= 106). Номера записаны в порядке возрастания.
Формат выходного файла.
В выходной файл запишите минимальное количество приказов, которое необходимо изготовить для отчисления всех неуспевающих студентов.
Примеры файлов входных и выходных данных:
b.in | b.out |
3 3 4 5 | 1 |
b.in | b.out |
6 1 2 5 7 8 9 | 3 |
Задача 3. «Окружность и прямоугольник» (50 баллов)
Имя входного файла: | c.in |
Имя выходного файла: | c.out |
Ограничение времени | 1 секунда на тест |
Ограничение по памяти | 32 Мб |
Вы имеете окружность радиуса R и прямоугольник со сторонами A и B. Ваша задача – определить, можно ли поместить окружность внутрь прямоугольника, или прямоугольник внутрь окружности. Касания разрешены.
Формат входного файла.
Во входном файле с.in записаны целые числа R, A и B (1 <= R, A, B <= 10000).
Формат выходного файла.
Если окружность можно поместить внутрь прямоугольника, то запишите в выходной файл с.out число 1, если прямоугольник можно поместить внутрь окружности, то запишите в выходной файл число 2, если ни то, ни другое нельзя сделать, запишите в выходной файл число 0.
Примеры файлов входных и выходных данных:
c.in | c.out |
3 20 30 | 1 |
c.in | c.out |
100 5 7 | 2 |
c.in | c.out |
10 1 100 | 0 |
Задача 4. «Осмотр лабиринта» (100 баллов)
Имя входного файла: | d.in |
Имя выходного файла: | d.out |
Ограничение времени | 1 секунда на тест |
Ограничение по памяти | 64 Мб |
Разведывательный робот предназначен для исследования опасных лабиринтов. Лабиринт, как обычно, представляет собой прямоугольник размером M на N, состоящий из одинаковых квадратов единичного размера. Некоторые квадраты заняты стенами, остальные свободны. Робот может перемещаться по горизонтали или по вертикали, если этому не препятствуют стены. Кроме того, робот снабжён четырьмя видеокамерами, которые позволяют ему видеть все квадраты лабиринта до ближайшей стены по горизонтали и по вертикали. Робот перемещается по лабиринту в соответствии с заданной ему программой. Программа для робота – это последовательность команд R, L, U, D. Команда R означает переместиться на один квадрат вправо, команда L – переместиться на один квадрат влево, U – на один квадрат вверх, и команда D – на один квадрат вниз. Если робот не может выполнить какую-либо команду (соответствующий квадрат занят стеной), то он пропускает эту команду и переходит к следующей. Ваша задача – по заданному плану лабиринта и заданной программе для робота подсчитать количество невыполненных команд и количество квадратов, осмотренных роботом. Квадрат, в котором находится робот в данный момент, ему не виден.
Формат входного файла.
В первой строке входного файла d.in записаны два целых числа N и M – размер лабиринта по вертикали и по горизонтали (3 <= N, M <= 100). В следующих N строках содержится план лабиринта. В каждой из этих строк записано по M символов ‘.’ или ‘#’ или ‘+’. Символы ‘.’ обозначают свободные квадраты, символы ‘#’ – квадраты, занятые стенами, и символ ‘+’ (который встречается в плане лабиринта ровно один раз) – начальное положение робота. Лабиринт всегда со всех сторон окружён стенами, так что робот не может выйти за его пределы. В следующей строке входного файла записано целое число L – длина программы для робота (1 <= L <= 10000). И в последней строке файла записана программа для робота. Программа состоит только из символов ‘R’, ‘L’, ‘U’, ‘D’.
Формат выходного файла.
Запишите в выходной файл d.out два целых числа через пробел – количество команд, которые робот не смог выполнить и количество квадратов, которые он осмотрел.
Примеры файлов входных и выходных данных:
d.in | d.out |
| d.in | d.out |
3 4 #### #+.# #### 4 RULD | 2 2 |
| 7 7 ####### #.....# #.##.## #.#..## #.#.#.# #+#...# ####### 10 UUUURRRDDL | 0 14 |
Задача 5.«Деление» (50 баллов)
Имя входного файла: | e.in |
Имя выходного файла: | e.out |
Ограничение времени | 1 секунда на тест |
Ограничение по памяти | 32 Мб |
Ваша задача – найти самое маленькое натуральное число, которое записывается в двоичной системе счисления в виде 1…10…0 (n единиц и m нулей, n, m > 0) и при этом делится на заданное число K.
Формат входного файла.
Во входном файле e.in записано натуральное число K (1 <= K <= 109).
Формат выходного файла.
Запишите в выходной файл e.out числа n и m – количество единиц и количество нулей в двоичной записи найденного числа.
Примеры файлов входных и выходных данных:
e.in | e.out |
2 | 1 1 |
e.in | e.out |
3 | 2 1 |
Задача 6. «Банковский кризис» (100 баллов)
Имя входного файла: | f.in |
Имя выходного файла: | f.out |
Ограничение времени | 1 секунда на тест |
Ограничение по памяти | 32 Мб |
В разгаре мировой финансовый кризис. Паника на биржах. Банкротства компаний. Банки лопаются один за другим из-за отсутствия средств. Но, по крайней мере, последнюю проблему – нехватку средств у банков решить очень легко. В наши дни банки кредитуют друг друга на огромные суммы. И когда какой-нибудь банк не имеет достаточно денег, чтобы возвратить взятые кредиты, на самом деле деньги у него есть, но они выданы другим банкам в качестве кредитов. Получается, что почти каждый банк должен огромные суммы другим банкам, но и другие банки должны ему огромные суммы. Рассмотрим в качестве примера денежные отношения четырёх банков, изображённые на рисунке (a). К примеру, A кредитовал B на 50 миллионов и в то же самое время B кредитовал A на 150 миллионов (это вполне обычная банковская практика, когда два банка кредитуют друг друга). Сумма долгов всех банков составляет 380 миллионов. Но можно обойтись существенно меньшей суммой, чтобы вернуть все кредиты. Для этого:
1. C кредитовал D на ту же сумму, что D кредитовал A, поэтому мы можем считать, что C кредитовал A на 30 миллионов, а D вообще исключить из межбанковских расчётов.
2. Поскольку A уже кредитовал C на 100 миллионов, мы можем считать, что A выдал C 70 миллионов.
3. Аналогично будем считать, что B выдал A 100 миллионов. Так мы придём к состоянию, показанному на рисунке (b). Теперь для всех расчётов достаточно 190 миллионов (исходная сумма уменьшилась вдвое).
4. Но можно добиться ещё лучших результатов. Вместо того, чтобы B заплатил A 100 миллионов, и A заплатил 70 миллионов C, B может заплатить 70 миллионов непосредственно С. Так мы придём к графу взаиморасчётов, показанному на рисунке (c). Теперь все банки могут вернуть все свои долги, имея всего 120 миллионов оборотных средств. Исходная сумма уменьшилась на 260 миллионов или 68%. Превосходно!
Напишите программу, которая находит минимальный объём оборотных средств, необходимых для выполнения всех взаиморасчётов между банками.
|
рисунок (a) рисунок (b) рисунок (c) |
Формат входного файла.
В первой строке входного файла записано количество банков N (N < 1000). В остальных N строках записана целочисленная матрица межбанковских расчётов размером N x N. i-я строка матрицы содержит суммы кредитов, выданные i-м банком. Все кредиты не превосходят 1000.
Формат выходного файла.
Запишите в выходной файл два целых числа – размер оборотных средств, необходимых для возврата всех кредитов до оптимизации и после оптимизации.
Примеры файлов входных и выходных данных:
f.in | f.out |
4 0 50 100 0 150 0 20 0 0 0 0 30 30 0 0 0 | 380 120 |
Инструкция участнику
Получите у организатора свой индивидуальный четырехзначный код. Файлы – решения должны быть названы следующим образом: pкод участника_номер задачи.расширение
В качестве расширения допустимо использовать dpr для текстов на Delphi (pascal) или cpp для текстов на C++
Язык программирования | Компилятор | Командная строка |
Паскаль
| Borland Delphi 7.0 | dcc32 –cc !.dpr |
Си | Microsoft Visual C++ .NET 2003 | cl !.cpp |
Например, Ваш код 2301 и Вы пишете на паскале. Тогда решением четвертой задачи должен быть файл p2301_4.dpr (если расширение вашего файла pas, то во время проверки это расширение будет заменено на dpr членами жюри).
Требования к решениям
Программа должна полностью содержаться в одном файле, использование своих модулей не допускается.
Разрешается использование библиотеки STL (для С++).
Программа должна читать входные данные только один раз из файлов, указанных в условии задачи и выводить результат в выходные файлы, указанные в условии задачи. ВНИМАНИЕ имена файлов должны быть точно такими, как в условии. Проследите, чтобы у входных и выходных файлов не было расширений “txt”!
Программа должна считать, что эти файлы находятся в текущем каталоге – не прописывайте пути к файлам в своих программах!
Результаты работы программы проверяются автоматически по тестам и ответам к ним, поэтому программа должна точно соблюдать формат вывода и вывода, указанный в условии.
Если вы работаете в проводнике и не видите расширения файлов, то снимите галочку в меню Сервис – Свойства папки – Вид – Дополнительные параметры – Скрывать расширения для зарегистрированных типов файлов.
Гарантируется, что входные файлы будут соответствовать формату, указанному в условии.
Ввод с клавиатуры и вывод на экран строго запрещен.
Во всех задачах будет указано максимальное время работы на одном тесте. Программа, превысившая допустимый предел времени работы прерывается.
Во всех задачах будет указан максимальный размер доступной памяти. Программа, превысившая допустимый предел памяти прерывается.
Программа не должна:
использовать расширенную память и защищенный режим процессора при использовании 16-битных компиляторов;
осуществлять чтение и запись векторов прерываний;
осуществлять любой ввод/вывод, кроме открытия, закрытия, чтения и записи файлов, указанных в условии задачи, в том числе создание подкаталогов, смену текущего каталога и ввод/вывод через порты;
осуществлять запуск других программ и создание новых процессов;
создавать или работать с любыми GUI объектами (окнами, диалогами и т.д.);
работать с внешними устройствами (принтером, сканером и т.д.);
иметь код завершения, отличный от нулевого.
Пример программы, которая считывает из входного файла “sum.in” два числа и выводит в выходной файл “sum.out” сумму этих чисел.
Borland Delphi 6.0 | Microsoft Visual C++ .NET 2003 |
{$Apptype Console} Program Summa; Const InFile = ‘sum.in’; OutFile = ‘sum.out’; Var A, B : LongInt; Begin Assign(InPut, InFile); ReSet(InPut); Assign(OutPut, OutFile); ReWrite(OutPut); Read(A, B); Write(A + B); Close(Output); End. | #include <vector> #include <string> #include <algorithm> #include <iostream> #include <fstream> #include <sstream> #include <cmath>
using namespace std;
int main() { ifstream infile ("sum.in"); ofstream outfile ("sum.out"); long a, b; infile >> a >> b; outfile << a + b; return 0; }
|
Вложение | Размер |
---|---|
![]() | 119 КБ |
Задачи Муниципального этапа олимпиады по информатике, который прошел 8 декабря 2011 года в Республике Башкортостан.
5 задач по 100 баллов.
Задача 1. Олимпиада MCA. 100 баллов.
Входной файл | test.in |
Выходной файл | test.out |
Ограничение по времени | 1 секунда на тест |
Ограничение по памяти | 16 мегабайт |
Всякому известен регламент ACM, по этому регламенту проходит Всероссийская командная олимпиада школьников по программированию и информатике. Менее известен альтернативный регламент MCA. Согласно этому регламенту каждая задача оценивается определённым количеством баллов. Правильно решённая задача даёт команде именно столько баллов. Выигрывает команда, набравшая наибольшее количество баллов. Если две или более команд набирают одинаковое количество баллов, то выигрывает команда, решившая наименьшее количество задач. Если и таких команд оказывается несколько, то выигрывает команда, имеющая наименьшее количество попыток сдать задачи (как успешных, так и безуспешных). Если по-прежнему победитель не определился, то выигрывает команда с наименьшим номером. Ваша задача - по итогам MCA турнира составить итоговую таблицу.
Формат входного файла.
В первой строке входного файла содержатся два целых числа T - количество команд и P - количество задач (1 ≤ T ≤ 10, 1 ≤ P ≤ 10). Команды пронумерованы от 1 до T, задачи названы первыми P заглавными буквами латинского алфавита. Во второй строке записаны P целых чисел из отрезка [1,100] - количество баллов, которым оценены задачи. Третья строка содержит одно целое число S (1 ≤ S ≤ 200) - суммарное количество сдач за время турнира. В следующих S строках записаны результаты сдач в формате
<номер команды> <код задачи> A|R
буква A (Accepted) означает, что задача принята, буква R (Rejected) означает, что задача не принята. Данные в этих строках разделены ровно одним пробелом.
Формат выходного файла.
Запишите в выходной файл итоговую таблицу турнира. Таблица должна занимать T строк, в каждой из которых должен быть записан номер команды и набранное командой количество баллов.
Примеры файлов входных и выходных данных:
test.in | test.out |
| test.in | test.out |
2 2 5 10 2 1 A A 2 B A | 2 10 1 5 |
| 2 2 5 10 3 1 B A 2 B A 1 A R | 2 10 1 10 |
|
|
|
|
|
test.in | test.out |
| test.in | test.out |
3 3 5 5 5 5 1 A A 1 B R 2 B A 2 C R 3 C A | 3 5 1 5 2 5 |
| 2 3 5 5 10 3 1 A A 1 B A 2 C A | 2 10 1 10 |
Остальные во вложении.
Вложение | Размер |
---|---|
![]() | 130 КБ |
Задачи 2 этапа Всероссийской олимпиады по информатике среди школьников. (районный этап 2007-8 учебного года, Республика Башкортостан).
Вложение | Размер |
---|---|
![]() | 264.22 КБ |
Задачи республиканской дистанционной олимпиады по информатике среди школьников 2006-2007 учебного года 8 сентября- 8 октября. Республика Башкортостан.
Вложение | Размер |
---|---|
![]() | 109.5 КБ |
В Башкортостане большое внимание уделяется летнему отдыху детей. Стало традицией каждое лето проводить Республиканские Летние сборы для одаренных школьников по информатике. Организатором сборов является министерство образования республики Башкортостан.
Лагерь организуется на базе детских лагерей, за городом. Как правило, на базе какой нибудь опорной школы проводятся занятия (или компьютеры собираются в детском оздоровительном лагере).
Срок: 12-14 дней. Тренерами приглашаются опытные учителя, студенты технических ВУЗов, призеры российских олимпиад. Дети набираются перспективные, т.е. в основном 7-9 классы: призеры региональной олимпиады, дистанционной. Проведение подобных сборов дает большую отдачу, повышается опыт у детей в программировании.
Хочу предложить часть материалов 2007 года. Тренер: Андрей Банников, призер Всероссийской и Всемирной олимпиады по информатике, член сборной Россий в 2006 году в Мексике.
Большинство материалов вы можете найти на сайте сборов: groups.google.com/group/bash_sbor
Программа создавалось мною на дипломную работу. Может кому понадобится когда будут изучать графы. Сделано на Делфи.
Вложение | Размер |
---|---|
![]() | 506.22 КБ |