Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 17 задач <---
Источники --> Личные олимпиады --> COCI --> COCI 2015-2016
    Раунд 1(6 задач)
    Раунд 2(6 задач)
    Раунд 3(6 задач)
    Раунд 4(6 задач)
    Раунд 5(6 задач)
    Раунд 6(6 задач)
Страница: << 1 2 3 4 Отображать по:
#113587
Мистер Картошечка
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 6, Мистер Картошечка ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Одаренный предпринимательским талантом Мистер Картошечка открывает два новых магазина, где, как вы, вероятно, уже догадались, он будет продавать картошечку. Мистер Картошечка получает картошку от N фермеров. Каждый фермер предлагает ровно a i картофелин с мешке общей стоимостью c i . Мистер Картошечка собирается купить по мешку картошки у кадого из фермеров и распределить их в два своих магазина.

Обозначим среднюю цену картошки в магазинах за P 1 и P 2 . Средняя цена равняется отношению суммарной стоимости к количеству картошки в данном магазине. Мистер Картошечка хочет, чтобы значение P 1 · P 2 было минимальным.

Кроме того, хотя бы в одном магазине дожно быть ровно L мешков картошки.

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

В первой строке содержатся два целых числа N и L ( 1 ≤ L < N ≤ 100 ).

Вторая строка содержит N целых чисел a i ( 1 ≤ a i ≤ 100 ), разделенных пробелами.

Третья строка содержит N целых чисел c i ( 1 ≤ c i ≤ 10 6 ), разделенных пробелами.

.

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

Выведите одно вещественное число, округлённое до 3 знаков после запятой – минимальное возможное значение P 1 · P 2 .

Система оценки

30 баллов: N ≤ 20 .

Примеры
Входные данные
3 1
3 2 1
1 2 3
Выходные данные
0.556
Входные данные
3 2
2 2 2
3 3 3
Выходные данные
2.250
#113588
Специфический сон
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 6, Специфический сон ]
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
512 megabytes

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

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

Формально, если A ( i , j ) - значение в i -й строке и j -м столбце доски, то:

1. A ( i , 1) = i

2. A ( i , j ) = A ( i , j - 1) + rev ( A ( i , j - 1)) , если j > 1 .

rev ( x ) - операция разворота числа в его десятичном представлении. Например, rev (345) = 543 , а rev (1040) = 0401 = 401 .

Затем во сне Аника увидела дружелюбного призрака Бозо, появившегося из-за угла. Он сказал ей: "Аника! Если ты правильно ответишь на мои вопросы, я подарю тебе коробку вкусного печенья. А вопросы мои будут такие: я буду давать тебе по два числа A и B , а ты должна будешь сказать, сколько на доске чисел, лежащих в диапазоне [ A : B ] ".

Аника, хоть она и во сне, очень хочет поесть печенья, поэтому просит вас помочь ответить на вопросы Бозо.

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

Первая строка содержит одно целое число Q ( 1 ≤ Q ≤ 10 5 ) - количество вопросов.

Каждая из последующих Q строк содержит два целых числа A и B ( 1 ≤ A ≤ B ≤ 10 10 ) - вопросы Бозо.

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

Выведите Q строк, в каждой одно целое число - ответ на соответствующий вопрос Бозо.

Примечание

Решения, работающие при A , B ≤ 10 6 , будут оцениваться в 50 баллов.

Примеры
Входные данные
2
1 10
5 8
Выходные данные
18
8
Входные данные
3
17 144
121 121
89 98
Выходные данные
265
25
10
Входные данные
1
1 1000000000
Выходные данные
1863025563
Страница: << 1 2 3 4 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест