Предисловие оргкомитета и жюри
Уважаемые участники олимпиады!
Предлагаем вашему вниманию задачи 2-го
тура.
Максимальное число баллов, которые можно набрать в этом туре
- 200. Письма с решениями,
оформленные по правилам(!),
отправляйте по адресу olymp@olymp.vinnica.ua в любое удобное для вас время с 22 октября 2000 г. по 7 ноября 2000 г. Наш робот сразу вам сообщит, получено ли ваше письмо. Если по какой-то причине ваше решение не компилируется, робот сообщит вам об этом и попробует объяснить причину. В этом случае можете отправить его повторно. Если же решение будет принято, повторные решения одной и той же задачи робот рассматривать не будет.
Идя навстречу большому числу ваших просьб, мы продолжим прием решений задач
1-го тура до 25 октября
,
а 28 октября планируем огласить результаты 1-го тура
(поместить на сервере www.olymp.vinnica.ua и разослать участникам). Третий тур будет рассылаться предположительно 4 ноября 2000 г.
Оргкомитет и жюри олимпиады.
Задача
BANK2
(
предоставлена коммерческим банком)
В нашем банке два отделения. К началу рабочего дня в каждом из них достаточно средств для проведения денежных операций. А операции мы проводим нетрадиционно – сумма денег, перечисляемых за одну операцию, всегда одна и та же. Мы можем выдавать деньги клиентам, получать их от клиентов и переводить из одного нашего отделения в другое. В конце каждого дня директор банка требует отчет о том, как изменились наши активы (то есть с прибылью мы или убытком). Вчера впервые оказалось так, что ни прибыли, ни убытков не было
– мы остались при своих… Я долго не верил в это, перепроверял каждую операцию и их следование друг за другом. Сколькими возможными способами могли быть проведены операции.
Ограничения
:
1<=N<=15, где N – количество проведенных операций.
Ввод-вывод :
Программа должна ввести с клавиатуры число проведенных операций, и вывести на экран количество вариантов.
Пример:
Ввод
> 2
Вывод
> 6
[Было проведено две операции. Вариантов проведения
: 6.
Эти варианты
:
1. 1) Перевод из первого отделения во второе, 2) Перевод из первого во второе;
2. 1) Перевод из первого во второе, 2) Перевод из второго в первое;
3. 1) Перевод из второго в первое, 2) Перевод из первого во второе;
4. 1) Перевод из второго в первое, 2) Перевод из второго в первое;
5. 1) Выдача денег, 2) Получение денег;
6. 1) Получение денег, 2) Выдача денег.]
Задача
MILITARY2
(вновь предоставлена министерством обороны)
Герой задачи Military, сержант с необычайными математическими способностями, решил все-таки обучить новобранцев становиться в колонну по одному. Он взял шестерых бойцов разного роста, и грозным голосом крикнул "Становись!". Стали новобранцы, разумеется, вновь, как попало. Но сержант на этот раз решил действовать строго по науке. Он долго и старательно объяснял широко открывшим рот новобранцам смысл новых команд. По команде "1" первые четыре новобранца должны перестроится в обратном порядке, по команде "2" перестроится в обратном порядке должны новобранцы, начиная со второго и, заканчивая
пятым, а по команде "3" в обратном порядке перестраиваются те, кто в колонне занимает места, начиная с третьего по шестое. Сержант громовым голосом выкрикивал номера команд в какой-то одному ему известной последовательности, а испуганные рекруты аккуратно их выполняли. В конечном итоге колонна стала такой, какой она должна быть по уставу, т.е. солдаты стояли по росту.
Сколько команд и в какой последовательности подавал сержант?
Ограничения:
Рост новобранцев измеряется в сантиметрах и не превышает 250.
Решение всегда существует, т.е. солдат всегда можно выстроить по росту. При этом первым должен стоять самый высокий, а последним – самый низкий солдат. Если существует несколько решений, можно вывести любое из них.
Ввод-вывод:
Программа должна прочитать с клавиатуры шесть чисел – рост шестерых новобранцев. Программа должна вывести в первой строке количество команд, а в следующих строках – сами команды.
Пример:
Ввод> 170 172 178 196 189 185
Вывод> 3
Вывод> 1
Вывод> 2
Вывод> 3
[В этом примере новобранцы перемещаются так:
Начальное положение
: 170 172 178 196 189 185;
После первой команды
: 196 178 172 170 189 185;
После второй команды
: 196 189 170 172 178 185;
После третьей команды
: 196 189 185 178 172 170.]
Задача DOMINO2
(предоставлена дворовым клубом любителей игры в "козла")
Один наш активист Семен Семенович Настойкин, коротая время в ожидании очереди на игру, учудил следующее. Из стандартного набора домино он изъял все кости, на одной половинке которых есть более чем
N точек. Из оставшихся костей он сложил на столе прямоугольник, а потом начертил все это в виде таблицы, каждая ячейка которой – половинка кости домино, а содержимое – число точек на этой половинке. Семен Семенович показал нам рисунок и предложил сложить исходную картинку из костей, которыми мы играли. Ненужные кости мы отложили в сторону быстренько, а вот разложить оставшиеся не можем уж который день. Даже в "козла" забросили играть – все раскладываем. Помогите нам.
Ограничения:
1<=N<=6. Решение всегда существует. Если существует несколько решений, достаточно найти любое из них.
Ввод/вывод:
Программа должна прочитать с клавиатуры: с первой строки – число N, со второй строки – размеры таблицы H и W, а со следующих H строк по W чисел – количество точек на половинке кости домино.
Программа должна вывести на экран H строк по W чисел в каждой. Каждое число – код той кости домино, которой принадлежит половинка, находящаяся в данной клеточке таблицы. Кость "X:Y" кодируется числом X*10+Y, если X<=Y.
Пример:
Ввод
> 2
Ввод
> 3 4
Ввод
> 0 0 1 2
Ввод
> 0 1 1 1
Ввод
> 0 2 2 2
Вывод
> 0 1 11 12
Вывод
> 0 1 11 12
Вывод
> 2 2 22 22
Задача GAME2
(вновь предоставлена читателем популярных книг по информатике)
Предлагаю Вашей программе поиграть со мной в такую игру. Я (или Ваша программа) называет натуральное число от 2 до 9, противник умножает его на любое натуральное число от 2 до 9, тот, кто начинал
– опять умножает результат на натуральное число от 2 до 9, и т.д. Выигрывает тот, кто первый получит произведение, больше заданного положительного числа С.
Ограничения:
10<=C<=50000
Ввод/вывод:
Сперва программа должна прочитать с клавиатуры два числа: C и P, где P равно 1, если программа должна начинать игру, или 2, когда программа должна играть за второго игрока. Затем программа должна поочередно выводить свой ход или вводить ход противника с клавиатуры. Программа должна закончить работу, когда игра завершится.
Пример:
Ввод
> 50 1
Вывод
> 3
Ввод
> 4
Вывод
> 5
[Программа начала игру и победила, получив последним ходом произведение
3*4*5=60>50]
Задача GRAPH2
(предоставлена дизайнером фирмы "GraphSoft")
Получил я вчера задание нарисовать картинку размером H на W пикселей, обертку
для конфет "Сосиска в шоколаде". Творчество
– процесс тонкий, вдохновение требуется. А тут – как топором отрубило, ничего не выходит… От безысходности я нарисовал на белом экране красную замкнутую линию, толщиной в один пиксель. Сколько пикселей оказалось в области, ограниченной красной линией?
Для тех, кто не знаком с компьютерной графикой
– пиксель имеет форму квадратика.
Ограничения
:
1<H,W<=100
Каждый красный пиксель имеет общие стороны ровно с двумя красными пикселями.
Ввод
/вывод:
Программа должна прочитать с клавиатуры
: с первой строки – два числа H и W, а со следующих H строчек по W чисел. Красный пиксель обозначается единицей, белый – нулем.
Программа должна вывести на экран результат - число пикселей, ограниченных линией.
Пример
:
Ввод
> 5 7
Ввод
> 0 0 0 1 1 1 0
Ввод
> 0 1 1 1 0 1 0
Ввод
> 0 1 0 0 0 1 0
Ввод
> 0 1 1 1 1 1 0
Ввод
> 0 0 0 0 0 0 0
Вывод
> 4
