Темы
Информатика(2656 задач)
--->
173 задач
<---
Во время лыжных соревнований \(N\) спортсменов стартуют с интервалом в 1 минуту. Скорость каждого лыжника на дистанции постоянна: \(i\)-й лыжник преодолевает 1 км за \(w_i\) минут. Длина трассы равна \(L\) км. Считается, что \(i\)-й лыжник обогнал \(j\)-го (совершил обгон), если он стартовал позже \(j\)-го, а пришёл к финишу раньше него. Подсчитайте суммарное число совершённых во время гонки обгонов.
Первая строка входного файла содержит два целых числа \(N\) и \(L\). Во второй строке через пробел расположены \(N\) целых чисел \(w_i\).
Выведите единственное число - суммарное количество обгонов.
Во всех тестах \(1 \le L \le 10^9\), \(1 \le w_i \le 10^9\) при \(i = 1, 2, \dots, N\). Тесты состоят из трёх групп.
2 1 20 19
0
5 3 3 6 2 4 1
7
В одной Очень Известной Летней Школе наиболее популярным видом спорта является волейбол. Для каждого из \(N\) школьников известно его умение играть в волейбол. Перед началом занятий школьников необходимо распределить между двумя тренерами.
Тренеры сочли справедливым следующий алгоритм разделения на две группы. Сначала они выбирают два целых числа \(p\), \(q\) (\(0 < p \le q \le N\)). Затем первый берет себе \(p\) лучших школьников, после чего оба тренера, начиная со второго, берут по очереди по \(q\) лучших школьников из оставшихся, пока их количество не меньше \(q\). В конце очередной тренер просто берет всех оставшихся.
Оба тренера заинтересованы в наиболее справедливом распределении школьников между группами. Поэтому они стремятся найти такие \(p\) и \(q\), чтобы разница суммарных умений между двумя группами школьников оказалась минимальной. При этом, вообще говоря, не обязательно, чтобы количество школьников в каждой из групп было одинаковым.
Помогите тренерам подобрать такие "справедливые" значения \(p\) и \(q\) (\(0 < p \le q \le N\)), при которых разница в суммарных умениях образованных групп школьников по абсолютной величине будет минимальна.
В первой строке входного файла записано единственное целое число \(N\). Во второй строке содержатся \(N\) неотрицательных целых чисел, не превосходящих \(10^9\) - умения школьников играть в волейбол.
Выведите искомые целые значения \(p\) и \(q\) (\(0 < p \le q \le N\)). Если искомых пар несколько, то выведите любую из них.
Тесты состоят из четырёх групп.
8 5 3 3 3 3 3 7 1
1 2
На одну Очень Известную Планету упал метеорит. Метеорит в атмосфере распался на \(N\) кусков, каждый из которых упал в свою точку.
Чтобы куски метеорита не были испорчены любопытными туристами, для проведения научных исследований решили построить один забор, которым огородить не менее \(K\) кусков метеорита. Естественно, что забор должен быть минимально возможной длины, и внутри него должны оказаться любые \(K\) (или больше) кусков метеорита (кусок считается лежащим внутри забора как когда он лежит строго внутри, так и когда забор проходит непосредственно через него).
Конечно, ученые хотят огородить как можно больше кусков, но как всегда, все упирается в деньги. Главный бухгалтер решил составить такую таблицу: для каждого \(K\) от 1 до \(N\) определить, какой минимальной длины нужно построить забор, чтобы внутри него оказалось не менее \(K\) кусков метеорита. Помогите ему.
В первой строке входного файла записано единственное целое число \(N\). В каждой из следующих \(N\) строк записано по паре целых чисел, по модулю не превосходящих \(1\,000\) - координаты точек, куда упали куски метеорита. Никакие два куска не упали в одну и ту же точку.
Выведите \(N\) чисел, \(i\)-е (\(1 \le i \le N\)) должно быть равно минимальной длине забора, внутри которого окажется не менее \(K\) кусков метеорита. Выведенный ответ будет сравниваться с правильным с точностью до \(10^{-6}\).
Тесты состоят из четырёх групп.
4 0 0 0 1 1 0 1 1
0.000000000 2.000000000 3.414213562 4.000000000
3 1 1 0 0 2 0
0.000000000 2.828427125 4.828427125
Футбольный клуб «Инжир» не имеет проблем с финансированием, поэтому приобрел N полевых игроков. После долгих месяцев тренировок и тестов тренерский коллектив подробно изучил каждого игрока и собирается выбрать оптимальный стартовый состав.
Каждый игрок характеризуется тремя целыми неотрицательными числами: di — умение играть в защите, mi — умение играть в полузащите и ai — умение играть в нападении. Играть было решено по схеме 5-3-2. Это означает, что в основном составе будет 5 игроков защиты, 3 полузащитника и 2 нападающих. Цель тренерского штаба — выбрать 10 игроков так, чтобы сумма соответствующих умений была максимальна (для игрока обороны значение имеет только его умение играть в защите, аналогично для других позиций). Разумеется, каждый игрок может играть не более чем на одной позиции. Ваша задача — помочь тренерскому штабу подобрать оптимальный состав.
В первой строке входного файла находится одно целое число N — количество игроков в клубе. Следующие N строк файла содержат по три целых числа каждая di, mi и ai — умения футболиста с номером i играть в обороне, полузащите и нападении соответственно.
Выходной файл должен содержать ровно три строки. Первая строка должна содержать пять чисел — номера игроков обороны. Вторая строка должна содержать ровно три числа — номера игроков полузащиты. Третья строка должна содержать ровно два числа — номера игроков нападения. Если оптимальных ответов несколько, можно вывести любой.
10
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
7 8 9
8 9 10
9 10 1
10 1 2
10 9 8 7 6
3 4 5
1 2
10
1 5 1
3 2 2
3 3 5
2 1 3
4 4 5
2 0 2
1 1 1
4 5 1
1 3 3
4 5 4
10 5 2 6 7
1 8 9
3 4
Тесты состоят из пяти групп. Во всех группах 0 ≤ di, mi, ai ≤ 107.
После почти повсеместного закрытия казино у нас в стране, предприимчивые дельцы стали создавать клубы по игре в различные азартные, но пока еще не запрещенные игры. Одной из таких игр стала игра «Уголки».
Игроку выдается карточка, на которой нарисована таблица, состоящая из M строк и N столбцов, каждым элементом которой является целое число. Строки и столбцы пронумерованы, начиная с единицы, клетка с номером (1, 1) находится в левом верхнем углу.
Игрок может сделать несколько ходов по следующим правилам. Первым ходом он может указать на любой элемент таблицы (r1, c1), и все числа в прямоугольнике (1, 1)–(r1, c1) меняют свой знак на противоположный. Здесь первое число обозначает номер строки, а второе — номер столбца. Следующие ходы игрока аналогичны, то есть выбирается прямоугольник (1, 1)–(ri, ci) и все числа опять меняют знак, однако каждый следующий прямоугольник должен полностью содержать предыдущий выбранный, но не совпадать с ним. Количество ходов при этом естественным образом ограничено размерами таблицы. При желании ходы можно и не выполнять совсем.
Например, если таблица состоит из 10 строк и 9 столбцов, то возможна в том числе такая последовательность ходов: (2, 2)–(4, 4)–(4, 6)–(5, 6).
После того как все желаемые ходы выполнены, подсчитывается результат игры — сумма значений элементов преобразованной таблицы. Если сумма положительная, то игрок получает от заведения соответствующую сумму денег, а если отрицательная — платит ее.
Помогите игроку добиться наилучшего результата: выиграть как можно больше или хотя бы проиграть как можно меньше.
В первой строке входного файла заданы два натуральных числа M и N (M ≤ 1 000, N ≤ 1 000). Каждая из следующих M строк содержит N целых чисел, по модулю не превышающих 1 000, — элементы таблицы.
В первой строке выходного файла выведите максимальную сумму, которую можно получить с помощью оптимальной стратегии игры по описанным правилам. Во второй строке выведите целое число K — количество действий в алгоритме, дающем наилучший результат. В следующих K строках выведите последовательность из K пар чисел (ri, ci), описывающих сам алгоритм.
Если дающих наилучший результат алгоритмов несколько, выведите любой.
2 3
3 6 4
1 -2 -7
21
2
1 3
2 3
4 4
2 -1 -5 -1
1 -3 -3 -1
0 -5 1 1
-1 -1 0 2
22
2
2 1
4 3
Тесты состоят из четырех групп.