Олимпиадные задачи по информатике

9 класса.

Задача 1. Выберем любое целое число и прибавим к нему сумму его цифр. Например, если мы выберем число 47, то сумма его цифр 4+7=11 и 47+11=58. Новое число называется порожденным числом, а исходное число его генератором. Может ли порожденное число иметь более одного генератора? Если да, то привести пример.

Решение. Данная задача решается использованием двух вложенных циклов. Во внешнем цикле будем перебирать все числа до тех пор, пока не встретим число, которое можно породить несколькими способами, а во втором – будем перебирать генераторы от 1 до порожденного числа.

Задача 2. На листе бумаги разлинованной в клетку изображены контуры двух фигур, линия контура лежит на границе клеток. Являются ли фигуры одинаковыми?

Решение. Две фигуры считаются одинаковыми, если они совпадают при наложении. Следовательно, для того, чтобы проверить являются ли фигуры одинаковыми нам нужно написать алгоритм совмещения двух фигур. Один из способов решения данной задачи состоит в следующем:

1. Будем обходить фигуры так, чтобы они всегда находились слева (т.е. против часовой стрелки).

2. Обозначим через 1 – движение вниз; 2 – движение вправо; 3 – движение вверх; 4 – движение влево.

3. Каждую из данных фигур закодируем при помощи введенных обозначений.

4. Если последовательность для первой фигуры можно получить какой-либо циклической перестановкой из последовательности для второй фигуры.

5. Если в шаге 4 фигуры не равны, то нужно проверить можно ли первую фигуру получить при помощи поворота второй фигуры (на 90, 180 или 270 градусов) или симметрии. Для этого опишем преобразования:

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

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

Если ни в одном из предыдущих шагов не был сделан вывод о равенстве фигур, то фигуры не равны.

Задача 3. N человек покупают билеты в четырех кассах. Известно, что на обслуживание k-го человека требуется t_k минут. Распределите людей в 4 очереди таким образом, чтобы общее время, потраченное на покупку билетов, было наименьшим.

Решение. Опишем массив из N элементов, в котором будем хранить время обслуживания каждого человека t_k. Так как по условию требуется распределить людей в 4 очереди, то нам понадобится 4 массива, для описания каждой из очередей. В каждом из последних массивов выделим элемент, в котором будем хранить сумму времен людей, находящихся в очереди в кассу. Исходя из этих допущений, напишем алгоритм решения задачи.

Алгоритм.

Дано: Последовательность чисел t_k, задаваемая с клавиатуры в массив Time, состоящий из N элементов.

Требуется: Построить 4 массива из исходного таким образом, чтобы сумма элементов в каждом из построенных массивов была наименьшей.

Решение:

1. Отсортируем исходный массив по не возрастанию.

2. Расставим первых четырех человек в очереди в кассы.

3. Последующих людей будем расставлять по правилу: если сумма времени тех, кто уже стоит в кассу и вновь добавляемого человека меньше, чем максимальная сумма во всех кассах, то человек добавляется в очередь, иначе проверяется следующая касса по тому же правилу. Если же ни в одной очередей правило не выполняется, то человек помещается в ту очередь, где сумма времени будет наименьшей.

Пример:

Пусть задан массив t_k={5, 4, 3, 3, 3, 2, 2, 2, 2, 2, 1}

Задача 4. Задан алфавит из трех букв a, b, c. С помощью данного алфавита составлены два слова. Определить имеют ли они одно значение. Известно, что при замене ab на ba, ac на ca и cb на bc значение слов не меняется.

Решение. Основа решения данной задачи состоит в тщательном анализе данных. Нетрудно заметить, что при заданных ограничениях на замены любую последовательность символов можно привести к упорядоченной по возрастанию. Таким образом, необходимо:

1. Сравнить количество символов в обеих последовательностях. Если они одинаковой длины, то перейти к шагу 2, иначе сделать вывод о том, что слова разные по смыслу.

2. Сравнить количество вхождений каждой из букв алфавита в последовательности и при равенстве сделать вывод, что одинаковы по смыслу, а иначе – разные.

Задача 5. Задан набор прямоугольников. Из них на плоскости складывается пирамида по следующим правилам:

1. Каждый слой пирамиды состоит из одного прямоугольника.

2. Основание последующего прямоугольника полностью помещается на верхней стороне предыдущего прямоугольника.

3. Размеры прямоугольников заданы.

Какую самую высокую пирамиду можно сложить из этих прямоугольников?

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

1. (Упорядочивание прямоугольников). Повернем все прямоугольники так, чтобы за ширину принималась наименьшая из сторон. Так как в задаче ничего не говорится о выводе порядка построения пирамиды, то их можно не сортировать.

2. Теперь можно найти высоту наибольшей пирамиды путем простого суммирования высот.