Колода из 1200 карт, на каждой карте написано натуральное число от 1 до 1200. Каждое число встречается лишь один раз. Раскладывается пасьянс в виде прямоугольника из карт 3x400 (3 строки и 400 столбцов) так, что числа на картах в каждом столбце возрастают сверху вниз, а также любое число в нижней строке больше любого числа в верхней строке. Удачностью пасьянса называется сумма всех чисел на карточках в верхней и нижней строках. Какой максимальной удачности можно выложить пасьянс?
Рассмотрим колоду из 1200 карт с числами от 1 до 1200. Необходимо расположить их в 3 строки по 400 карт (то есть 400 столбцов) так, чтобы в каждом столбце числа шли по возрастанию сверху вниз, а любое число нижней строки было больше любого числа верхней строки. Удачность пасьянса определяется как сумма всех чисел на карточках верхней и нижней строк.
Чтобы максимизировать эту сумму, нужно максимизировать сумму чисел верхней и нижней строк. Заметим, что общая сумма всех чисел от 1 до 1200 фиксирована и равна
S = 1 + 2 + … + 1200 = 1200·1201/2 = 720600.
При этом...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
