Страница: << 18 19 20 21 22 23 24 >> Отображать по:

#3398

Велогонка

Темы: [Бинарный поиск по ответу] [Тернарный поиск]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2011, Задача F ]

Велосипедисты, участвующие в шоссейной гонке, в некоторый момент времени, который называется начальным, оказались в точках, удалённых от места старта на $x_1$, $x_2$, ..., $x_n$ метров ($n$ – общее количество велосипедистов). Каждый велосипедист двигается со своей постоянной скоростью $v_1$, $v_2$, ..., $v_n$ метров в секунду. Все велосипедисты двигаются в одну и ту же сторону.

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

Требуется написать программу, которая по заданному количеству велосипедистов $n$, заданным начальным положениям велосипедистов $x_1$, $x_2$, ..., $x_n$ и их скоростям $v_1$, $v_2$, ..., $v_n$, вычислит момент времени $t$, в который расстояние $l$ между лидирующим и замыкающим велосипедистом будет минимальным.

Входные данные

Первая строка входного файла содержит целое число $n$ – количество велосипедистов.

В последующих n строках указаны по два целых числа: $x_i$ – расстояние от старта до $i$-го велосипедиста в начальный момент времени ($0 \leq x_i \leq 10^7$) и $v_i$ – его скорость ($0 \leq v_i \leq 10^7$).

Выходные данные

В выходной файл необходимо вывести два вещественных числа: $t$ – время в секундах, прошедшее от начального момента времени до момента, когда расстояние в метрах между лидером и замыкающим будет минимальным, $l$ – искомое расстояние.

Числа t и l должны иметь абсолютную или относительную погрешность не более $10^{–6}$, что означает следующее. Пусть выведенное число равно $x$, а в правильном ответе оно равно $y$. Ответ будет считаться правильным, если значение выражения $|x – y| / max(1, |y|)$ не превышает $10^{–6}$.

Подзадачи и система оценки

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

Подзадача 1 (20 баллов)

$2 \leq n \leq 50$, $0 \leq x_i \leq 1000$, $0 \leq v_i \leq 1000$. Гарантируется, что существует ответ, в котором $t$ – целое число, не превышающее 1000.

Подзадача 2 (20 баллов)

$2 \leq n \leq 200$.

Подзадача 3 (30 баллов)

$2 \leq n \leq 2000$

Подзадача 4 (30 баллов)

$2 \leq n \leq 10^5$

Примеры

Входные данные

Выходные данные

1 30

Входные данные

Выходные данные

0.5 5.000000000000

#3400

Распил бревен

Темы: [Многоугольники. Выпуклые оболочки]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2011, Задача H ]

Лесопильный комбинат выполняет заказ на распил брусьев для строительства детского городка. Все готовые брусья должны иметь форму треугольных призм, основаниями которых являются равнобедренные треугольники. Для изготовления брусьев закуплены заготовки в виде половинок продольно распиленных бревен. Заготовки не являются идеальными половинками цилиндров, поэтому при изготовлении бруса необходимо учитывать форму заготовок. Комбинат заинтересован в изготовлении бруса с наибольшей возможной площадью поперечного сечения.

Для каждой заготовки измеряется несколько сечений. Каждое из них задано в виде ломаной, представленной координатами ее вершин ($x_0, y_0$), ($x_1, y_1$), ..., ($x_N, y_N$) в порядке их следования. Координаты вершин ломанной удовлетворяют следующим условиям:

$x_0 < x_1 < x_2 < \dots < x_N$;

$x_i = 0$ для некоторого $0 < i < N$;

$y_0 = y_N = 0$;

для всех $i$ от 1 до ($N – 1$) выполнено условие $y_i > 0$.

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

основание треугольника лежит на оси абсцисс;

основание симметрично относительно начала координат;

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

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

Входные данные

Первая строка входного файла содержит целое число $K$ – количество измеренных сечений.

Далее следуют описания каждого из $K$ сечений. В первой строке описания сечения содержится число $N_K$ – количество звеньев ломаной. За ней следуют ($N_K + 1$) строк, каждая из которых содержит пару целых чисел $x_i$ и $y_i$ – координаты вершин ломаной сечения в порядке их следования.

Выходные данные

Выходной файл должен содержать одно вещественное число – наибольшую возможную площадь треугольника. Эта площадь должна иметь абсолютную или относительную погрешность не более $10^{–6}$, что означает следующее. Пусть выведенное число равно $x$, а в правильном ответе оно равно $y$. Ответ будет считаться правильным, если значение выражения $|x – y| / max(1, |y|)$ не превышает $10^{–6}$.

Подзадачи и система оценки

Данная задача содержит пять подзадач.

Подзадача 1 (20 баллов)

$K = 1$, $N_1 \leq 15$, координаты вершин по модулю не превышают 20.

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

Подзадача 2 (10 баллов)

$1 \leq K \leq 20$, сумма $N_i \leq 2000$, координаты вершин по модулю не превышают $10^4$. Гарантируется, что полученный в качестве ответа треугольник является прямоугольным.

Подзадача 3 (20 баллов)

$1 \leq K \leq 20$, сумма $N_i \leq 2000$, координаты вершин по модулю не превышают $10^4$.

Подзадача 4 (10 баллов)

$1 \leq K \leq 1000$, сумма $N_i \leq 10^5$, координаты вершин по модулю не превышают $10^9$. Гарантируется, что полученный в качестве ответа треугольник является прямоугольным.

Подзадача 5 (40 баллов)

$1 \leq K \leq 1000$, сумма $N_i \leq 10^5$, координаты вершин по модулю не превышают $10^9$.

Каждый тест для данной подзадачи оценивается отдельно.

Примеры

Входные данные

Выходные данные

25.0

#3787

Кривая дракона

Темы: [Арифметические алгоритмы] [Цикл for]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2011, Задача B ]

Сегодня мальчик Саша на уроке математики узнал про фракталы. Учитель показывал так называемую «кривую дракона». Она представляет собой геометрическую фигуру, которая строится следующим образом: на первом шаге проводится отрезок из начала координатной плоскости в точку (0; 1). Далее на каждом шаге из конца фрактала повторяется уже нарисованная часть фигуры, повернутая на 90 градусов против часовой стрелки (см. рисунок).

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

$\text{[math]}$

Входные данные

Вводится одно целое число N (1 ≤ N ≤ 30).

Выходные данные

Выведите два числа через пробел — координаты конца фрактала.

Примеры

Входные данные

Выходные данные

1 1

Входные данные

Выходные данные

2 -2

#3789

Сохранить энергию

Темы: [Динамическое программирование: два параметра]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2011, Задача D ]

Одна Фруктовая Компания, производящая электронику, решила озаботиться длительностью работы своих смартфонов от аккумулятора.

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

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

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

Входные данные

Первая строка содержит три целых числа: число k (1 ≤ k ≤ 100) — количество операций в языке программирования, число m (1 ≤ m ≤ 100) — количество режимов работы, которое поддерживает процессор, и число n (1 ≤ n ≤ 10000) — количество операций в исследуемой программе.

Следующие k строчек содержат по m целых неотрицательных чисел, не превышающих 100. j-е число в i-ой строчке обозначает, сколько энергии тратится на выполнение i-ой операции в j-ом режиме команд.

Далее следует m строчек, содержащих по m целых неотрицательных чисел, не превышающих 100. j-ое число в i-ой строчке обозначает, сколько единиц энергии тратится на переключение процессора с режима i на режим j. Гарантируется, что в i-ой строке i-ое число равно 0.

Последняя строчка содержит исследуемую программу: n натуральных чисел, не превышающих k и соответствующих операциям языка программирования.

Выходные данные

Выведите одно число — минимальное количество единиц энергии, необходимое для выполнения программы.

Подзадачи и система оценки

Тесты к этой задаче состоят из трех групп.

Тесты из условия, оцениваются в ноль баллов.
В тестах этой группы $n$, $m$, $k$ не превосходят 10. Эта группа оценивается в 50 баллов, баллы ставятся только при прохождении всех тестов группы.
В тестах этой группы $m$ не превосходит 10. Эта группа оценивается в 30 баллов, баллы ставятся только при прохождении всех тестов группы и предыдущих групп.
В тестах этой группы дополнительные ограничения отсутствуют. Группа оценивается в 20 баллов, баллы ставятся только при прохождении всех тестов этой и предыдущих групп.

Примеры

Входные данные

Выходные данные

Входные данные

Выходные данные

#3865

Круглый стол

Темы: [Жадный алгоритм]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2012, 1 день, Задача B ]

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

Руководитель клуба Иван Петрович недавно заметил, что не все ребята активно участвуют в обсуждении. Понаблюдав за несколькими заседаниями клуба, он заметил, что активность члена клуба зависит от того, кто с кем сидит рядом.

В клуб приходят на занятия m мальчиков и n девочек. Иван Петрович заметил, что мальчик активно участвует в обсуждении только тогда, когда непосредственно рядом с ним с обеих сторон от него сидят девочки, а девочка активно участвует в обсуждении только тогда, когда непосредственно рядом с ней с одной стороны от нее сидит мальчик, а с другой — девочка.

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

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

Входные данные

Входной файл содержит два целых числа m и n, разделенных ровно одним пробелом (0 ≤ m ≤ 1000, 0 ≤ n ≤ 1000, m + n ≥ 3).

Выходные данные

Выходной файл должен содержать строку с расположенными в некотором порядке m символами «B» (заглавная латинская буква) и n символами «G» (заглавная латинская буква). Символ «B» означает мальчика, а символ «G» — девочку.

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

Примечание к примерам тестов

В первом примере все члены клуба примут активное участие в обсуждении.

Во втором примере мальчики примут активное участие в обсуждении, а девочки нет. В этом примере можно также разместить членов клуба следующим образом: «BBGG». В этом случае активное участие в обсуждении примут обе девочки, а мальчики — нет. Разместить всех так, чтобы три или четыре члена клуба приняли активное участие в обсуждении, нельзя.

Примеры

Входные данные

1 2

Выходные данные

BGG

Входные данные

2 2

Выходные данные

BGBG

Страница: << 18 19 20 21 22 23 24 >> Отображать по:

Выбрано

Отменить

Добавить в контест