Выбрана 1 задача 
Убрать все задачи
Из заданных n предметов выбрать такие , чтобы их суммарный вес был менее 30 кг, а стоимость - наибольшей. Напечатать суммарную стоимость выбранных предметов. Точнее- заданы два массива положительных чисел А[1:n] и В[1:n]. Выбрать такие попарно различные числа i1, i2,... ik, чтобы сумма
А[i1] + A[i2] +...+ A[ik] < 30, а сумма
B[i1] + B[i2] +...+ B[ik] = max была максимальной. Напечатать только величину max
Замечание. Можно предполагать , что предметы уже расположены в порядке возрастания или убывания веса А[i], стоимости В[i], цены В[i] / A[i] или какого-либо иного признака.
Решение
|
|
 |
Условие
Все клетки квадратной таблицы n×n пронумерованы в некотором порядке числами от 1 до n². Петя делает ходы по следующим правилам. Первым ходом он ставит фишку в любую клетку. Каждым последующим ходом Петя может либо поставить новую фишку на какую-то клетку, либо переставить фишку из клетки с номером a ходом по горизонтали или по вертикали в клетку с номером большим, чем a. Каждый раз, когда фишка попадает в клетку, эта клетка немедленно закрашивается; ставить фишку на закрашенную клетку запрещено. Какое наименьшее количество фишек потребуется Пете, чтобы независимо от исходной нумерации он смог за несколько ходов закрасить все клетки таблицы?
Решение
n фишек достаточно. Действительно, на каждую строку хватит одной фишки: можно поставить её в клетку строки с минимальным номером, а затем обойти все клетки строки в порядке возрастания номеров.
Покажем, что меньшего числа фишек может и не хватить. Для этого пронумеруем клетки одной диагонали числами 1, 2, ..., n, а остальные клетки нумеруем произвольно. Тогда одна фишка не сможет побывать на двух клетках этой диагонали: если фишка встала на одну её клеток, то следующим ходом она обязана будет пойти на клетку с номером, большим n, и значит, после этого не сможет вернуться на диагональ. Поскольку на каждой клетке диагонали должна побывать фишка, Пете придётся использовать не менее n фишек.
Ответ
n фишек.
