Решения олимпиадных задач

Теоретический тур (6 задач)

 

Задача 1. “Электронная почта”.

Какие две клавиши нужно нажать в MS Word, чтобы из фразы с выделенным фрагментом «электронная почта» получить фразу «эл. почта»?

 

Точка и пробел.

 

Задача 2. “Скорость”.

За какое время модем со скоростью 14400 bps (бит в секунду) передаст файл размером 52.7 Кбайт?

 

 

 

Задача 3. “Безопасность файлов”.

Имеется программа-архиватор, умеющая разбивать архив на тома любого выбранного размера не менее 1000 байт. Даны две дискеты размером 1.44 Мбайт, вероятно, имеющие по несколько сбойных кластеров. Требуется сохранить архив размером 1 Мбайт на эти дискеты. Предложите метод записи, обеспечивающий наибольшую защиту данных от потерь из-за порчи кластеров при длительном хранении дискет. (Файл, записываемый на дискету, разбит на кластеры размером 512 байт, последний кластер обычно не заполнен. В корневой каталог можно поместить 63 файла или подкаталога, в подкаталог же можно поместить сколько угодно файлов.)

 

Наибольшую сохранность имеет разбиение архива на тома размером с кластер и с дублированием каждого тома на все дискеты в возможно большем количестве экземпляров. Но архиватор позволяет создавать тома размером не менее 1000 байт – чуть меньше 2 кластеров. Чтобы 24 байта (в каждом томе) не пропадали без пользы, разбиваем архив на тома размером 1024 байта. Их будет 1 МВ / 1 КВ = 1024 тома. Помещаем их в подкаталоги на дискетах, итого уже 2 экземпляра каждого тома. На каждой дискете осталось около 0,44 МВ свободного места (а может быть и меньше, если на дискетах уже есть сбойные кластеры). Этого места хватит на 0,44 МВ / 1024 = 440 томов. Используем это место так: 440 первых томов поместим на одну дискету, а 440 других томов – на другую. Итого, большинство томов присутствуют в трех экземплярах. Оценим теперь вероятность потери хотя бы части данных в предложенном методе и в случае хранения целых 1 МВ файлов:

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

При разбиении на тома размером 1024 байта данные потеряются лишь при потере всех экземпляров какого-нибудь тома:

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

 

Задача 4. “Бензовоз”.

Бензовоз должен доставить горючее из пункта X в пункт Y, расстояние между которыми равно S миль. Бензовоз расходует 1 литр на одну милю, а его бак вместе с цистерной вмещает 1000 литров. В пункте X стоит цистерна с запасом V литров. Бензовоз может сделать несколько рейсов, переливая бензин в цистерну в пункте Y и оставляя нужное количество бензина на возможный обратный путь.

Предложить алгоритм, который отвечает на вопрос, какое максимальное количество бензина можно перевезти из пункта X в пункт Y, если:

а) промежуточных пунктов для хранения бензина между X и Y нет;

б) в пункте C на расстоянии Z по пути от X до Y стоит пустая цистерна, куда предварительно можно завезти некоторый запас бензина, а затем его использовать.

 

а) Используем так называемый «жадный» алгоритм – будем перевозить их X в Y всякий раз максимально доступное количество бензина: 1000-2*S. Остановимся лишь если в X останется меньше либо равно 2*S литров, ради перевозки которых возвращаться невыгодно. Итак, в поездках полного бензовоза будет перевезено  литров, а за остатком бензина имеет смысл ехать лишь если в X осталось более 2*S литров. Полная формула:

 

б) Применим алгоритм пункта а) к перевозке бензина из X в C, а потом из C в Y.

Задача 5. “Лидеры”.

N спортсменов стартуют от одного места, но в разные моменты времени t1<t2<…<tN и движутся по дистанции (неограниченной) с постоянными скоростями v1<v2<…<vN. Предложить алгоритм, перечисляющий, кто из спортсменов побывает в роли лидеров.

 

Первый лидер – это тот, кто стартовал в момент t1. Найдем момент T1 смены лидера. Пусть это будет спортсмен x. Это произойдет на расстоянии (T1-t1)*v1, равном также (T1-tx)*vx. Выразим T1: пропуская расчеты, получим T1=v1*(tx-t1)/(vx-v1)+tx. Найдем номер нового лидера x: из всех возможных лидеров 2, 3,…, N выберем того, у кого момент T1 обгона прежнего лидера наступит раньше. После смены лидера прежний лидер отбрасывается и алгоритм применяется к оставшимся с коррекцией моментов времени стартов: t2+T1<t3+T1<…<tN+T1.

Задача 6. “Фестиваль”.

В клубе любителей кино состоят N членов. Ежегодно на Международный кинофестиваль в Канны посылаются K членов киноклуба. Одна делегация не должна ехать дважды, т.е. каждый год состав делегации не таков, как в предыдущие. Предложите алгоритм, порождающий списки всех возможных делегаций. Каково их количество?

 

Это выборки с повторениями (число сочетаний), их количество: . Генерировать варианты можно следующим рекурсивным алгоритмом: сначала получим все варианты, содержащие первого участника, а потом все, не содержащие его. То есть к претендентам (2, 3,…, N)  и вакансиям (K-1) применим этот же алгоритм рекурсивно, и в начало каждого полученного списка припишем первого участника. Потом к претендентам (2, 3,…, N)  и вакансиям (K) применим этот же алгоритм. Списки объединим.

Возможны и другие решения. Например, прибавлять двоично по единичке к битовому массиву размера N и подсчитывать число единичек в массиве.

 

Практический тур (4 задачи)

 

Задача 1. “Сумма квадратов”.

Вводятся целочисленные координаты трех точек на плоскости. Найти координаты точки плоскости такой, что сумма квадратов расстояний от нее до трех данных точек минимальна.

 

Даны точки (x1,y1), (x2,y2), (x3,y3). Ищем (x,y).

Сумма квадратов расстояний: S(x,y)=(x1-x)^2+(y1-y)^2+(x2-x)^2+(y2-y)^2+(x3-x)^2+(y3-y)^2. Найдем точки минимума по x и по y: Sx=-2*(x1-x)-2*(x2-x)-2*(x3-x)=0, -> x=(x1+x2+x3)/3. То же и для y: y=(y1+y2+y3)/3. Значит, искомая точка – среднее арифметическое соответствующих координат вершин треугольника. Программа простейшая.

Задача 2. “Сумма расстояний”.

То же, что и в первой задаче, только минимизировать сумму расстояний от искомой точки до трех заданных точек.

 

Даны точки (x1,y1), (x2,y2), (x3,y3). Ищем (x,y). Сумма расстояний:

Простейшее решение, без знания математики, такое: из любой исходной точки (например, первой вершины) начинаем движение. Пусть шаг равен для начала 1, выберем направление. Для этого посчитаем сумму расстояний S(x,y) в четырех точках с шагом 1 вверх, вниз, влево, вправо. Выберем ту, которая даст наилучшее уменьшение суммы. Когда зациклимся, т.е. будем перескакивать между 2-я точками, значит пора уменьшить шаг вдвое. Остановимся, когда достигнем необходимой точности – достаточно маленького шага.

Математическое решение такое: Берем производную:

 

. Это уравнение неразрешимо, поэтому придется искать точку численными методами. Например, методом градиентного спуска. Вспоминаем: вектор из производных  называется градиентом и направлен в сторону роста функции S(x,y). Значит, выбрав любую начальную точку, нужно двигаться в сторону, обратную градиенту. Алгоритм итерационный, начальная точка, например, x=x1, y=y1. Находим градиент в ней, пусть он равен (a,b). Сдвигаемся: x=x-k*a, y=y-k*b, где k – шаг, пусть в начале k=1. Посчитаем S в предыдущей и новой точках, и если S уменьшилось, значит идем правильно, продолжаем движение с тем же шагом. Если S увеличилось, значит мы перепрыгнули точку минимума из-за слишком большого k. Уменьшим k вдвое и продолжим спуск. Останавливаемся, когда достигнем требуемой точности, например k=0,001. Этот алгоритм аналогичен методу дихотомии (деления отрезка пополам).

Задача 3. “Умножение столбиком”.

Написать программу, которая выводит картинку, изображающую умножение «столбиком» двух введенных чисел (стандартного целочисленного типа).

 

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

Задача 4. “Целые точки”.

Вводятся целочисленные координаты вершин треугольника на плоскости. Определить количество целочисленных точек, попавших внутрь и на границу треугольника.

 

Попасть внутрь треугольника могут точки, принадлежащие прямоугольнику, описанному около исходного треугольника. Метод проверки принадлежности точки треугольнику таков: берем сторону треугольника, ее уравнение прямой делит плоскость надвое. Нужно убедиться, что целочисленная точка лежит в одной полуплоскости с третьей вершиной. Уравнение прямой имеет вид A*x+B*y+C=0 и если подставить точки в A*x+B*y+C, то результаты должны иметь просто одинаковый знак. Так же проверить для остальных сторон треугольника.