--->
13 задач
<---
Источники
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
После затянувшегося совещания директор фирмы решил заказать такси,чтобы развезти сотрудников по домам. Он заказал N машин —ровно столько, сколь у него сотрудников.Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.
Директор знает, какому сотруднику сколько километров от работы до дома (к сожалению, все сотрудники живут в разных направлениях, поэтому нельзя отправить двух сотрудников на одной машине). Теперь директор хочет определить, сколько придется заплатить за перевозку всех сотрудников. Естественно, директор хочет заплатить как можно меньшую сумму.
Входные данные
В первой строке записаны \(N\) чисел через пробел, задающих расстояния в километрах от работы до домов сотрудников компании. Во второй строке записаны \(N\) чисел — тарифы за проезд одного километра в такси.
Выходные данные
Выведите одно целое число — наименьшую сумму, которую придется заплатить за доставку всех сотрудников.
Примеры
Входные данные
10 20 30 50 20 30
Выходные данные
1700
#112125
ограничение по времени на тест
0.25 second;
ограничение по памяти на тест
256 megabytes
Для хранения двух агрессивных жидкостей \(A\) и \(B\) используется емкость с многослойной перегородкой, которая изготавливается из имеющихся \(N\) листов. Для каждого листа \(i\) (\(i\) = 1, ..., \(N\)) известно время его растворения жидкостью \(A\) - \(a_i\) и жидкостью \(B\) - \(b_i\). Растворение перегородки каждой из жидкостей происходит последовательно лист за листом, с постоянной скоростью по толщине листа. Требуется спроектировать такую перегородку, время растворения которой было бы максимальным.
В первой строке входного файла записано число \(N\) (1 ≤ \(N\) ≤ 256). В каждой из последующих N строк содержатся два положительных вещественных числа \(a_i\) и \(b_i\), разделенные пробелом.
Выходные данные
В первую строку выходного файла записать время растворения перегородки с точностью до 3 цифр после десятичной точки. В следующую строку файла записать номера листов в порядке их расположения от жидкости A к жидкости B, разделяя числа пробелами.
Примеры
Входные данные
4 1 2 1 2 0.5 1.5 7 3.5
Выходные данные
6.00000000 4 2 1 3
#113894
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
256 megabytes
Петя увлёкся алгоритмами сжатия данных. Он уже изучил форматы gz , bz , zip и несколько других. Воодушевившись новыми знаниями, Петя собрался разработать свой формат сжатия и назвать его dis .
Петя решил сжимать таблицы. У него есть таблица, состоящая из n строк и m столбцов, заполненная целыми положительными числами. Он хочет заменить значения элементов таблицы на целые положительные числа так, чтобы отношение элементов в каждой строке и каждом столбце не изменилось. То есть, если в некоторой строке исходной таблицы a i , j < a i , k , то и в сжатой таблице a ' i , j < a ' i , k , и если a i , j = a i , k , то a ' i , j = a ' i , k . Аналогично, если в некотором столбце исходной таблицы a i , j < a p , j , то и в сжатой таблице a ' i , j < a ' p , j , и если a i , j = a p , j , то a ' i , j = a ' p , j .
Поскольку б'{о}льшие значения требуют больше места для хранения, максимальное значение элемента получившейся матрицы должно быть как можно меньше.
В теории Петя мастер, но вот писать код он не любит. Помогите ему реализовать формат сжатия dis .
Входные данные
В первой строке входных данных содержатся два числа
n
и
m
(
— количество строк и столбцов таблицы соответственно.
В следующих n строках содержится по m целых чисел a i , j (1 ≤ a i , j ≤ 10 9 ) — значения элементов таблицы.
Выходные данные
Выведите сжатую таблицу: n строк, содержащих по m чисел.
Если существует несколько ответов, минимизирующих максимальное число, то разрешается вывести любой из них.
Система оценки
Тесты к этой задаче состоят из восьми групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых предыдущих групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
Примечание
В первом примере a 1, 2 ≠ a 2, 1 , но, поскольку они не располагаются в одной строке или в одном столбце, при сжатии их можно сделать равными.
Примеры
Входные данные
2 2 1 2 3 4
Выходные данные
1 2 2 3
Входные данные
4 3 20 10 30 50 40 30 50 60 70 90 80 70
Выходные данные
2 1 3 5 4 3 5 6 7 9 8 7
Выбрано
:
|