Олимпиада

Материалы для подготовки к олимпиадам по программированию.

Вкратце об олимпиадном программировании

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

Во-первых, вы ничего не пишете на русском языке. Все решения записываются сразу на компьютере (без бумаги) и сразу на языке программирования. Конечно, черновые записи делаются на бумаге, но это производится на усмотрение самого участника и не влияет на его оценку. Важно, что в решении могут использоваться любые математические свойства и закономерности, и вам нет нужды их доказывать. Если вы уверены, что какое-то простое, за минуту придуманное правило позволяет верно решить задачу, записывайте его, и истина вас рассудит: если идея была верной, такое решение будет оценено независимо от того, доказывали вы для себя это правило или нет.

Во-вторых, проверка решений на таких олимпиадах обычно является, в своем роде, самой справедливой и самой несправедливой. (Вообще-то программистских олимпиад много, и есть среди них и такие, к которым этот пункт не относится, но в дальнейшем речи о них идти не будет.) Дело в том, что жюри не смотрит вашу программу, а проверяет ее (обычно в автоматическом режиме, с помощью компьютера) на тестах. Вообще, по условию задач, в программу вводятся некие входные данные, она их обрабатывает и выдает ответ. Тесты жюри — это варианты входных данных и соответствующих правильных ответов. При тестировании жюри «подсовывает» вашей программе свои тесты, а затем проверяет, правильный ли ответ ваша программа выдает. Справедливость (по сравнению с проверкой задач по математике, физике) здесь заключается в том, что от решения требуется только одно — правильность, соответствие условиям, только то, не требовать чего было бы нельзя. Неважно, понятно решение или нет, если оно работает. Неважно, каким способом вы получили ответ, если он правильный. В любом случае вы получите причитающиеся баллы. Несправедливость же здесь в том, что за глупую ошибку, вроде тех, за которые снимают 1—2 балла на других олимпиадах, здесь задача может вполне быть аннулированной. Далее мы подробно рассмотрим популярные ошибки и методы борьбы с ними.

Есть два основных подхода к оценке решений. При одном подходе, который я буду далее называть «Пан или пропал», задача либо получает максимум баллов, если все тесты успешно пройдены, либо 0, если хотя бы на одном из тестов она «завалилась». Так чаще всего оценивают на командных олимпиадах. На большинстве других олимпиад, в том числе обычных школьных (на всех этапах: городском, региональном и более крупных), используется более гуманная система оценки. Проверочные тесты имеют определенный вес в баллах. Если тест пройдет, то эти баллы прибавляются к счету участника. Бывает дополнительный «бонус», то есть баллы, которые начисляются, только если все тесты пройдены. Действия олимпиадника различаются в двух этих случаях (особенно, если задачи сложные), но об этом речь пойдет позже.

  Чтобы программа прошла тест, она должна не просто выдать правильный ответ, но еще и справиться с этим за определенное время, указанное в условии задачи. (Помимо этого, там указывается максимальная память, но ее в любом случае трудно превысить на TP, а кто пишет на более совершенных языках, тот сориентируется сам.) Дело здесь в том, что многие задачи можно решить простым алгоритмом, который работает слишком долго, и поэтому на больших тестах простой алгоритм будет нерабочим. Грубо говоря, чем оптимальнее (практически — быстрее) работает алгоритм, тем больше баллов (при «гуманном» подходе) получит участник на данной задаче. На всех серьезных олимпиадах решения тестируются автоматически, с помощью специальной программы, поэтому нужно следить за корректностью вывода. Личность участника тестирующая программа идентифицирует по имени файла, содержащего решение, поэтому ошибка в имени файла аннулирует задачу — будьте внимательны.

II (муниципальный) этап Всероссийской олимпиады школьников по информатике в Башкортостане

3 декабря в Башкортостане прошел 2 муниципальный этап олимпиады школьников по информатике. 

Привожу тексты задач.  Интересно, какими были задачки в других регионах?


 
Задача А.  Два плюс – три. (100 балов)
Входной файл:a.in
Выходной файл:a.out
Ограничение по времени: 1 сек.
Ограничение по памяти: 16 Мб
Вася, скучая на уроке математики, писал в тетради различные числа. Наугад выбирая три числа, он проверял, можно ли, суммируя первые два числа, получить третье. Сосед по парте отличник Иванов, усложнив задачу, написал программу, которая позволяет проверить можно ли перестановкой цифр в числах a и b, записанных Васей, получить их сумму равную c.
Входные данные
Входной файл содержит три целых числа: a, b, c (0 < a, b, c < 109). Числа разделены пробелом.
Выходные данные
Если искомая перестановка цифр невозможна, вывести в выходной файл число 0. При положительном ответе необходимо вывести число x, получаемое перестановкой цифр числа a, и число y, получаемое перестановкой цифр числа b, сумма которых равна c. Числа x и y не должны содержать ведущих нулей и разделяются пробелом. Если вариантов чисел несколько, то вывести любой.
Пример

a.in
a. out
12 31 25
12 13
12 31 26
0
101 2 13
11 2

 
Задача B. Различные числа (80 балов)
Входной файл:b.in
Выходной файл:b.out
Ограничение по времени: 1 сек.
Ограничение по памяти: 32 Мб
Дан массив (достаточно большой), содержащий целые числа из диапазона -15000..15000. Сосчитать сколько различных чисел в этом массиве. Гарантируется, что количество чисел в файле не превышает 106.
Формат входных данных:
Во входном файле b.in содержатся элементы массива. Файл может содержать несколько строк. Все числа в строке разделены пробелом. Каждая строка заканчивается «Enter».
Формат выходных данных:
В первой строке выходного файла b.out содержится число – количество различных чисел. Далее следуют сами эти числа, записанные по 10 в строке в порядке возрастания.
Пример

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

 
Задача С. Театр (80 баллов)
Входной файл:                             с.in
Выходной файл:                          c.out.
Ограничение по времени тестирования: 1 сек.
Ограничение по памяти: 32 Мб
В театре N мест, пронумерованных целыми числами от 1 до N. Некоторые зрители опоздали на спектакль, поэтому после третьего звонка те зрители, которые имели билеты на неудобные места, пересели на более удобные. Опоздавшие зрители, которые пришли уже после третьего звонка, садились на первое попавшееся свободное место.
В антракте один из опоздавших решил сесть на свое место. Если его место до этого было занято, то сидевший там пересаживался на свое место. Если и там кто-то уже сидел, то и этот зритель также вынужден был вернуться на свое место, и так далее. Поскольку в театр попали только зрители с билетами, то начавшийся в антракте процесс пересаживания зрителей обязательно заканчивался.
Требуется составить программу для подсчета количества зрителей, которые были вынуждены пересесть на свои места.
Формат входных данных:
Входной файл c.inсостоит из трех строк. В первой строке содержится целое число N (1 £ N £ 15 000) — количество мест в театре. Вторая строка содержит последовательность из N целых чисел, разделенных пробелами. Первое число определяет номер места в билете у зрителя, занявшего первое место, второе число — номер места в билете у зрителя, занявшего второе место, и так далее. Если место свободно, то соответствующее число равно 0. Третья строка содержит одно целое число K (1 £ K £ 15 000) — номер места в билете опоздавшего зрителя, который решил пересесть в антракте на свое место.
Формат выходных данных:
Выходной файл c.outсодержит одно целое число — количество зрителей, поменявших свои места в антракте, включая опоздавшего зрителя.

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. Змейка (80 балов)
Входной файл:d.in
Выходной файл:d.out
Ограничение по времени: 1 сек.
Ограничение по памяти: 32 Мб
Мальчик Вася на уроке математики, вместо того, чтобы слушать учителя, рисовал числа в тетрадке в клеточку. Да не просто так рисовал, а определенным образом. Сначала он поставил в клетку число 1. Затем справа от нее нарисовал число 2. Затем снизу от числа 2 написал число 3. Затем перешёл на клетку правее и продолжил увлекательное занятие, двигаясь по столбцу вверх, пока число в этом столбце не стало выше самого верхнего числа в предыдущем столбце. Затем он перешёл на клетку правее и опять таки продолжил рисование чисел, начиная с 7, но только уже сверху вниз, пока не нарисовал число, которое оказалось на одну клетку ниже самого нижнего числа в предыдущем столбце. И так далее. Вася не любил числа, заканчивающиеся нулем, и пропускал их при рисовании змейки. Первые его шесть заполненных столбцов мы скопировали из его тетрадки и привели здесь на рисунке. Так как Вася очень любопытный, то он очень хочет узнать, какое же число будет у него стоять в N-ом столбце в той строке, где стоит число 1. Первые 6 таких чисел в этой строке видны на рисунке: 1, 2, 5, 8, 14, 19. Напишите программу, которая поможет Васе.
Формат входных данных:
Вводится одно число N (1 ≤ N ≤ 106) – номер столбца.
Формат выходных данных:
Вывести N-ое число в строке, где стоит число 1.

d.in
d.out
5
14

 
 
 
 
 
 
 
Задача E. Склад (60 балов)
Входной файл:e.in
Выходной файл:e.out
Ограничение по времени: 2 сек.
Ограничение по памяти: 32 Мб
Банки с красками нумеруются числами от 0 до 999999. Краски на склад поступают наборами, в каждом наборе содержится по одной банке для каждого номера краски от a до b включительно. Время от времени на склад приходит покупатель и забирает все банки с номерами большими или равными k. В начале дня склад пустой.
Напишите программу для кладовщика, которая вычисляет количество банок, взятых покупателями.
Формат входных данных:
Во входном файле журнал действий кладовщика. Строка "ADDab", где a и b – целые числа (0 ≤ ab ≤ 999999), означает, что на склад поступил набор с номерами банок от a до b. Строка "DELk", где k – целое число (0 ≤ k ≤ 999999), означает, что пришёл покупатель и забрал все банки с номерами большими или равными k. Строка ''END'' является последней строкой в файле и означает конец рабочего дня кладовщика. Количество записей в файле не превышает 2000.
Формат выходных данных:
В выходной файл для каждой записи "DELk" в порядке их следования во входном файле вывести строку, содержащую одно число – количество банок, взятых этим покупателем.
Пример

e.in
e.out
ADD 10 20
ADD 5 15
DEL 7
ADD 3 7
DEL 4
DEL 5
END
20
6
0
 

 

 

ВложениеРазмер
inf09.doc80 КБ

Второй этап олимпиады школьников по информатике

5 декабря прошел второй этап (районный) олимпиады школьников по информатике. Министерством образования республики задачи олимпиады были высланы в 9 часов утра в день олимпиады на почтовые ящики отделов образования (дублируются на ящики отвественных за проведение олимпиады). Условия задач тут же были размножены и в 10 ч школьники приступили к решению.  Всего 6 задач. Решения учащихся проверялись спец. программой и высылались в жюри, которое будет подводить итоги по республике (общий рейтинг). В этом году изменились правила проведения олимпиады, на региональный этап будут приглашены первые 70 учащихся в данном рейтинге.

Не секрет, что большинство учащихся в школе тему "Программирование" изучают в небольшом количестве и на олимпиаде большинство получают НУЛЬ. Поэтому нашим жюри несколько задач олимпиады были подобраны на их уровень. Таким образом количество нулевых баллов в нынешнем году было меньше.  

Задачи во вложении. Task_2_2008.doc

Программа тестирования решений Test_2008.zip

ВложениеРазмер
Task_2_2008.doc79.5 КБ
Test_2008.zip453.05 КБ

Задачи 1-го тура регионального этапа Всероссийской олимпиады школьников по программированию 2011 года

Задача 1 «Ролевая игра» Вася готовит инвентарь для ролевой игры. В игре должны принять участие n игроков, каждый из которых будет изображать персонажа фантастического мира. В процессе игры каждый персонаж будет обладать некоторым уровнем x, который представляет собой целое число от 1 до m. Для обозначения уровня планируется использовать специальные значки двух цветов. Белый значок обозначает один уровень, а красный значок — k уровней. Игрок, изображающий персонажа с уровнем x, должен иметь a белых значков и b красных значков, чтобы сумма (a + bk) была равна x. При этом персонажу не разрешается иметь более чем (k – 1) белых значков. Значки для игры готовятся заранее, однако уровни персонажей заранее неизвестны. Для успешного проведения игры всем персонажам необходимо выдать соответствующее их уровням количество значков. Возникает вопрос: какое минимальное суммарное количество значков необходимо подготовить для успешного проведения игры при любых уровнях участвующих персонажей. Требуется написать программу, которая по заданным числам n, m и k вычисляет минимальное количество значков, которое необходимо подготовить для успешного проведения игры. Задача 2 «Колесо Фортуны» азвлекательный телеканал транслирует шоу «Колесо Фортуны». В процессе игры участники шоу крутят большое колесо, разделенное на сектора. В каждом секторе этого колеса записано число. После того как колесо останавливается, специальная стрелка указывает на один из секторов. Число в этом секторе определяет выигрыш игрока. Юный участник шоу заметил, что колесо в процессе вращения замедляется из-за того, что стрелка задевает за выступы на колесе, находящиеся между секторами. Если колесо вращается с угловой скоростью v градусов в секунду, и стрелка, переходя из сектора X к следующему сектору, задевает за очередной выступ, то текущая угловая скорость движения колеса уменьшается на k градусов в секунду. При этом если v ≤ k, то колесо не может преодолеть препятствие и останавливается. Стрелка в этом случае будет указывать на сектор X. Юный участник шоу собирается вращать колесо. Зная порядок секторов на колесе, он хочет заставить колесо вращаться с такой начальной скоростью, чтобы после остановки колеса стрелка указала на как можно большее число. Колесо можно вращать в любом направлении и придавать ему начальную угловую скорость от a до b градусов в секунду. Требуется написать программу, которая по заданному расположению чисел в секторах, минимальной и максимальной начальной угловой скорости вращения колеса и величине замедления колеса при переходе через границу секторов вычисляет максимальный выигрыш. Задача 3 «Форматирование текста» Многие системы форматирования текста, например TEX или Wiki, используют для разбиения текста на абзацы пустые строки. Текст представляет собой последовательность слов, разделенных пробелами, символами перевода строк и следующими знаками препинания: «,», «.», «?», «!», «-», «:» и «’» (ASCII коды 44, 46, 63, 33, 45, 58, 39). Каждое слово в тексте состоит из заглавных и прописных букв латинского алфавита и цифр. Текст может состоять из нескольких абзацев. В этом случае соседние абзацы разделяются одной или несколькими пустыми строками. Перед первым абзацем и после последнего абзаца также могут идти одна или несколько пустых строк. Дальнейшее использование исходного текста предполагает его форматирование, которое осуществляется следующим образом. Каждый абзац должен быть разбит на строки, каждая из которых имеет длину не больше w. Первая строка каждого абзаца должна начинаться с отступа, состоящего из b пробелов. Слова внутри одной строки должны быть разделены ровно одним пробелом. Если после слова идет один или несколько знаков препинания, они должны следовать сразу после слова без дополнительных пробелов. Если очередное слово вместе со следующими за ним знаками препинания помещается на текущую строку, оно размещается на текущей строке. В противном случае, с этого слова начинается новая строка. В отформатированном тексте абзацы не должны разделяться пустыми строками. В конце строк не должно быть пробелов. Требуется написать программу, которая по заданным числам w и b и заданному тексту выводит текст, отформатированный описанным выше образом. Задача 4 «Космические исследования» Отделу космических исследований поступило задание сфотографировать из космоса n объектов в заданной области. Область имеет форму квадрата размером 50×50 километров. Если разделить ее на квадраты размером 1×1 километр, то интересующие отдел объекты окажутся в центрах некоторых единичных квадратов. Введем систему координат, направив ось OX с запада на восток и ось OY с юга на север. Тогда каждому единичному квадрату будут сопоставлены координаты в диапазоне от 1 до 50, как показано на рисунке ниже. Для космической съемки используется специальный фотоаппарат высокого разрешения, установленный на космическом спутнике. Фотоаппарат может делать снимки квадратных участков земной поверхности размером k × k километров. Исходно аппарат наведен на юго-западный угол заданной области, то есть, если сделать снимок, на нем будут видны единичные квадраты с координатами x и yот 1 до k километров. С помощью специальных двигателей можно изменять орбиту спутника, что приводит к изменению участка съемки. За один день орбиту спутника можно изменить таким образом, что участок съемки сместится либо на один километр на запад, либо на один километр на восток, либо на один километр на север. Переместить участок съемки на юг невозможно. Непосредственно между перемещениями спутника можно сделать снимок, временем съемки можно пренебречь. Руководство отдела заинтересовалось вопросом: за какое минимальное количество дней можно сделать снимки всех объектов заданной области. Требуется написать программу, которая по заданному расположению объектов и размеру снимка k определит минимальное время, за которое можно сделать снимки всех объектов заданной области. Все остальное во вложении
ВложениеРазмер
tour01.doc143 КБ

Задачи 2-го тура регионального этапа Всероссийской олимпиады школьников по программированию 2011 года

Задача 5 «Шахматная доска» Аня разделила доску размера m × n на клетки размера 1 × 1 и раскрасила их в черный и белый цвет в шахматном порядке. Васю заинтересовал вопрос: клеток какого цвета получилось больше — черного или белого. Для того чтобы выяснить это, он спросил у Ани, в какой цвет она раскрасила j-ю клетку в i-м ряду доски. По этой информации Вася попытался определить, клеток какого цвета на доске больше. Требуется написать программу, которая по размерам доски и цвету j-й клетки в i-м ряду определит, клеток какого цвета на доске больше — черного или белого. Задача 6 «Чемпионат по стрельбе» Победитель школьного этапа олимпиады по информатике нашел дома в старых бумагах результаты чемпионата страны по стрельбе из лука, в котором участвовал его папа. К сожалению, листок с результатами сильно пострадал от времени, и разобрать фамилии участников было невозможно. Остались только набранные каждым участником очки, причем расположились они в том порядке, в котором участники чемпионата выполняли стрельбу. Расспросив папу, школьник выяснил, что количество очков, которое набрал папа, заканчивается на 5, один из победителей чемпионата стрелял раньше, а папин друг, который стрелял сразу после папы, набрал меньше очков. Теперь он заинтересовался, какое самое высокое место мог занять его папа на том чемпионате. Будем считать, что участник соревнования занял k-е место, если ровно (k – 1) участников чемпионата набрали строго больше очков, чем он. При этом победителями считались все участники чемпионата, занявшие первое место. Требуется написать программу, которая по заданным результатам чемпионата определяет, какое самое высокое место на чемпионате мог занять папа победителя школьного этапа олимпиады по информатике. Задача 7 «Делители» Натуральное число a называется делителем натурального числа b, если b = ac для некоторого натурального числа c. Например, делителями числа 6 являются числа 1, 2, 3 и 6. Два числа называются взаимно простыми, если у них нет общих делителей кроме 1. Например, 16 и 27 взаимно просты, а 18 и 24 — нет. Будем называть нормальным набор из k чисел (a1, a2, …, ak), если выполнены следующие условия: 1) каждое из чисел ai является делителем числа n; 2) выполняется неравенство a1 < a2 < … < ak; 3) числа ai и ai+1 для всех i от 1 до k – 1 являются взаимно простыми; 4) произведение a1a2…ak не превышает n. Например, набор (2, 9, 10) является нормальным набором из 3 делителей числа 360. Требуется написать программу, которая по заданным значениям n и k определяет количество нормальных наборов из k делителей числа n. Задача 8 «Дом у дороги» Министерство дорожного транспорта решило построить себе новый офис. Поскольку министр регулярно выезжает с инспекцией наиболее важных трасс, было решено, что офис министерства не должен располагаться слишком далеко от них. Наиболее важные трассы представляют собой прямые на плоскости. Министерство хочет выбрать такое расположение для своего офиса, чтобы максимум из расстояний от офиса до трасс был как можно меньше. Требуется написать программу, которая по заданному расположению наиболее важных трасс определяет оптимальное расположение дома для офиса министерства дорожного транспорта. Все остальное во вложенном файле
ВложениеРазмер
tour02.doc86 КБ

Задачи муниципального этапа Всероссийской олимпиады школьников по программированию 2010 года (Башкортостан)

Выкладываю задачки с олимпиады по программированию в Башкортостане, который прошел 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  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;

          }

           

          ВложениеРазмер
          Usloviya_zadach.doc119 КБ

          Задачи муниципального этапа Всероссийской олимпиады школьников по программированию 2011 года (Башкортостан)

          Задачи Муниципального этапа  олимпиады  по информатике, который прошел 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

            Остальные во вложении.

             

            ВложениеРазмер
            _general_standart_inf_11_usl-inf2011.doc130 КБ

            Задачи олимпиады по программированию

            Задачи 2 этапа Всероссийской олимпиады по информатике среди школьников. (районный этап 2007-8 учебного года, Республика Башкортостан).

            ВложениеРазмер
            Statements.doc264.22 КБ

            Задачи олимпиады по программированию

            Задачи республиканской дистанционной олимпиады по информатике среди школьников 2006-2007 учебного года 8 сентября- 8 октября. Республика Башкортостан.

            ВложениеРазмер
            Statements.doc109.5 КБ

            Летние сборы по программированию

            В Башкортостане большое внимание уделяется летнему отдыху детей. Стало традицией каждое лето проводить Республиканские Летние сборы для одаренных школьников по информатике. Организатором сборов является министерство образования республики Башкортостан.

            Лагерь организуется на базе детских лагерей, за городом. Как правило, на базе какой нибудь опорной школы проводятся занятия (или компьютеры собираются в детском оздоровительном лагере).

             

            Срок: 12-14 дней.  Тренерами приглашаются опытные учителя, студенты технических ВУЗов, призеры российских олимпиад. Дети набираются перспективные, т.е. в основном 7-9 классы: призеры региональной олимпиады, дистанционной. Проведение подобных сборов дает большую отдачу, повышается опыт у детей в программировании.

            Хочу предложить часть материалов 2007 года. Тренер: Андрей Банников, призер Всероссийской и Всемирной олимпиады по информатике, член сборной Россий в 2006 году в Мексике.

            Большинство материалов вы можете найти на сайте сборов: groups.google.com/group/bash_sbor

            ВложениеРазмер
            1_тур.doc45.5 КБ
            2_тур.doc50.5 КБ
            3_тур.doc49.5 КБ
            4_тур.doc42 КБ
            5_тур.doc76 КБ
            5_тур.doc76 КБ
            6_тур.doc47.5 КБ
            Пробный+тур.doc27.5 КБ

            Программа визуализации работы алгоритмов на графах

            Программа создавалось мною на дипломную работу. Может кому понадобится когда будут изучать графы. Сделано на Делфи.

            Информатика: 
            Классы: 
            ВложениеРазмер
            SDDemo.rar506.22 КБ