Задачи муниципального этапа олимпиады школьников по информатике 2013

Вышел Илья Муромец из леса на дорогу, ведущую из Киева в Чернигов, и увидел камень, на котором было написано "До села Калиновки – 120 верст, до реки Смородины – 50 верст, до Киева…". Остальная часть надписи на камне была неразборчива, но Илья вспомнил расстояние от Киева до села и до реки и легко определил, что от камня с надписью до Киева 200 верст.

В первой строке содержатся четыре целых числа, разделенные пробелами — расстояние от села Калиновки до Киева `A`, расстояние от реки Смородины до Киeва `B` (`1\ ≤\ \ A\ <\ B\ ≤\ 1000`), расстояние от камня до села Калиновки `X` и расстояние от камня до реки Смородины `Y` (`1\ ≤\ \ X,\ Y\ ≤\ 1000`). Гарантируется, что числа `A,\ B,\ X,\ Y` соответствуют какому-то возможному расположению камня на дороге.

Вывести одно целое число — расстояние от камня с надписью до Киева.

80 150 120 50

200

Реализуйте на одном из языков программирования алгоритм, представленный на схеме.

В первой строке ввода содержатся два целых числа `A` и `B` (`1\ ≤\ A\ ≤\ B\ ≤\ 10^9`).

Вывести одно целое число – значение `K` после завершения работы алгоритма.

10 100

2

Сотовый телефон всегда выбирает ближайшую базовую станцию, а при равенстве расстояний — базовую станцию с меньшим номером.

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

Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 10`) – количество базовых станций. Далее следует `N` строк, содержащих по два целых чисел в диапазоне от 0 до 1000 — координаты базовых станций. Следующая строка ввода содержит одно целое число `M` (`1\ ≤\ M\ ≤\ 1000`) – количество абонентов. Далее следует `M` строк, содержащих по два целых чисел в диапазоне от 0 до 1000 — координаты абонентов.

Вывести `N` строк, содержащих по одному целому числу. `i`-я строка содержит количество абонентов, выбравших `i`-ю базовую станцию для связи.

2
1 1
100 200
3
0 0
1000 1000
150 250

1
2

К 2020 году многие автокомпании планируют создать автомобили, которые могут самостоятельно доставить пассажиров из точки А в точку Б.

Чтобы понять трудности, стоящие перед разработчиками программного обеспечения для автомобиля-робота, напишите программу для управления роботом в следующей задаче. Роботу нужно проехать по двухполосной дороге с односторонним движением длиной 10 единиц, на которой припаркованы несколько машин (см. рис.). Машины могут стоять на любой полосе, но путь по дороге всегда существует. Первоначально робот находится в начале дороги на левой полосе. Робот может выполнять следующие команды: ^ – ехать вперед, < – сдвинуться в полосу, расположенную левее текущей полосы движения, > – сдвинуться в полосу, расположенную правее. После команды можно указать число – количество повторений этой команды. Например, ^5 – ехать вперед 5 единиц. Несколько команд можно соединить в группу с помощью круглых скобок, тогда число после закрывающейся скобки будет показывать количество повторений этой группы, например, (^>^<)3. Для проверки возможности движения в каком-то направлении используется команда ?, после которой указывается команда движения ^, <, >. Если движение в этом направлении возможно, то команда выполняется. Иначе в программе ищется символ | (вертикальная черта) и выполняется команда после него. Например, ?^|< – пытаемся ехать вперед, если нельзя, то сдвигаемся влево. Можно соединить несколько проверок в последовательность, например, ?^|?<|>.

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

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

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

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

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

Напишите программу, которая определяет суммарное количество итераций для некоторой комбинации циклов.

В первой строке ввода содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 10`) — количество циклов в программе. Далее следует `2*N` строк, содержащих информацию о циклах в анализируемой программе. Каждая строка содержит либо строку вида "for `x`", где `x` – целое число в диапазоне от 2 до 1000, количество итераций, либо строку "end", обозначающую конец цикла. Гарантируется, что каждый for будет иметь соответствующий ему end и наоборот.

Вывести в первой строке одно целое число — суммарное количество итераций для анализируемой программы. Гарантируется, что результат не будет превышать `10^{18}`.

2
for 100
for 20
end
end

2000

2
for 100
end
for 20
end

120

Рассмотрим две последовательности `A` и `B`, содержащих по `N` элементов. Сумму абсолютных значений разностей соответствующих элементов двух последовательностей (т.е. ) будем называть степенью различия этих последовательностей. Добавляя ко всем элементам первой последовательности некоторое значение `C`, можно уменьшить степень различия.

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

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

Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 100`) – количество элементов в последовательностях. Вторая строка содержит `N` целых чисел в диапазоне от 0 до 1000 — элементы первой последовательности. Третья строка содержит `N` целых чисел в диапазоне от 0 до 1000 — элементы второй последовательности. При указанных ограничениях на диапазон значений элементов в качестве возможных значений C, минимизирующих степень различия, можно рассматривать только числа в диапазоне от `-1000` до `1000`. Вывести одно целое число — степень похожести двух последовательностей.

4
10 20 21 9
0 10 10 0

2

Петя решил сделать небольшой забор из нескольких имеющихся у него досок разной длины. Из эстетических соображений разница в длине планок забора не должна превышать некоторой величины `D`. Петя может разрезать доску на любое количество планок, имеющих любую длину. Необязательно, чтобы их длина была целым числом или планки из одной доски имели одинаковую длину. Но после разрезания нельзя выбрасывать ничего – все отрезанные от доски части становятся планками забора. Так как Пете приходится пилить доски ножовкой (вручную), то он хочет минимизировать количество распилов.

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

Первая строка ввода содержит два целых числа — количество досок `N` (`2\ ≤\ N\ ≤\ 1000`) и ограничение по разнице длин планок `D` (`100\ ≤\ D\ ≤\ 1000`). Во второй строке содержится `N` целых чисел в диапазоне от 1000 до 100000 — длины досок.

Вывести одно целое число — минимальное количество распилов.

2 100
1600 1100

3

Пояснение к примеру: Петя может первую доску распилить на планки длиной 500, 500 и 600 с помощью двух распилов, а вторую доску – на две планки длиной 500 и 600. Это не единственный вариант. Можно распилить вторую доску на части длиной 501 и 599 или 502.36 и 597.64.

Характеристика тестов к задаче:

Для 10-11 классов в 20% тестов `N=2`, в 30% тестов `N=10`, в 50% тестов `N=1000`.

Для 7-9 классов `N≤10` и использовалась половина всех тестов, в 40% тестов `N=2`, в 60% тестов `N=10`.