(Если невозможно, вывести -1)
Даны массивы x[] и y[] из n <= 1000 элементов каждый.
Можно в каждом из массивов элементы перемешать.
Нужно максмизировать скалярное произведение
(x[0] * y[0] + x[1] * y[1] + ... + x[n-1] * y[n-1])
Easy-Version : x[i], y[i] >= 0
Есть белоснежка и n <= 100 000 гномов.
Укладывать i-го гнома спать нужно a[i] минут. Если хоть какие-то
гномы не спят, в комнате, где живут гномики, очень шумно, поэтому уже
уложенные не могут проспать больше, чем b[i] минут, после чего просыпаются.
В каком порядке белоснежке укладывать гномов так, чтобы все заснули?
Easy-Version : a[i] = 1
Дана N-звенная замкнутая ломаная (3 <= N <= 105).
Нужно по очереди удалить все звенья ломаной, получив при этом макс бонус.
Удаляя ребро, мы получаем бонус = произведению углов с соседними звеньями.
Угол выбирается <= 180. Если одно из соседних звеньев уже удалено, бонус = 0.
Easy-Version : N <= 100
Даны N доминошек (1 <= N <= 105). На каждой написано 2 числа - a[i] и b[i].
Доминошки можно переворачивать (менять a[i] и b[i] местами). Нужно расположить
их подряд (получится прямоугольник 2×N, состоящий из 2-х строк) так, чтобы
В первой строке числа неубывали, а во второй не возрастали.
Easy-Version : все числа различные от 1 до 2N
Даны N <= 10
5 чисел - a[i], все a[i] > 0.
За один ход можно взять 2 числа a[i], a[j] > 0 (i != j) и уменьшить их на 1.
- Какое максимальное число ходов можно сделать?
- Какое минимальное число ходов нужно сделать так, чтобы потом походить было уже нельзя?
Нужно построить матрицу NxN с заданными суммами в строках и столбцах.
Все элементы должны быть целые, от 0 до 100 (1 <= N <= 100).
Hard-Version : Элементы от 0 до 10^9, 1 <= N <= 1000.
Easy-Version1 : Нет ограничения про от 0 до 100.
Easy-Version2 : Нет ограничения про до 100 (но уже от 0)
Дан неориентированный граф.
Нужно каждое ребро покрасить в один из 2-х цветов так, чтобы
у каждой вершины было хотя бы одно смежное ребро каждого из 2-х цветов.