|
Нам нужно определить, сколько чисел можно получить 20-ю командами, а не количество наборов программ, как в 22.
При этом от изменения порядок команд роли не играет, главное - не получить отрицательное число.
Допустим, наборы "+2 +2 +2 -4", "+2 +2 -4 +2", "+2 -4 +2 +2" и "-4 +2 +2 +2" в результате дадут одно и то же число. Правда два последних набора дадут отрицательный результат в процессе вычислений, но на это начихать, так как первые два набора дают положительный результат.
Теперь определим, сколько всего чисел мы можем получить, даже если в результате будет получаться отрицательное число.
Даны две команды +2 и -4
Всего программа состоит из 20 команд.
Для наглядности можно расписать
+2 +2 +2 +2 ... +2 +2 +2 - программа, состоящая только из 1-х команд
-4 +2 +2 +2 ... +2 +2 +2 - программа, в которой есть одна 2-я команда
-4 -4 +2 +2 ... +2 +2 +2 - программа, в которой есть две 2-е команды
...
-4 -4 -4 -4 ... -4 -4 -4 -4 - программа, состоящая только из команд -4
Не сложно посчитать, что всего существует 21 такая программа (всего 20 команд, от +2+2+2...+2 до +4+4+4...+4, 21 набор)
Однако отрицательные числа нам не нужны. Таким образом, мы можем найти количество программ, которые дают во всех вариантах расстановки команд отрицательное число. Проще говоря, если рассматривать программы в порядке увеличения количества команд -4, то в один прекрасный момент такие программы будут давать отрицательные числа. То есть нужно найти минимальное количество команд -4, которые дадут отрицательное число.
Для этого можно решить систему
5 + x*2 - y*4 < 0
x + y = 20
y >= 8
То есть если программа будет содержать 8 или больше команд 2, то результат будет отрицательный. Можно проверить:
5 + 12*2 - 8*4 = 5 + 24 - 32 = -3 - 8 команд -4
5 + 13*2 - 7*4 = 5 + 26 - 28 = 3 - 7 команд -4
Всего программ, в которых 8 или больше команд -4 - [8..20], то есть 13
Всего программ 21
Программ, из которых получаются положительные числа - 21-13 = 8
Ответ: 8
P.S. Как-то слишком объемно расписал, увлёкся, второе решение:
5 + 2x - 4y >= 0
x = 20-y
5 + 2(20-y) - 4y >=0
45 - 6y >= 0
6y <= 45
y <= 7,5, y - целое число, значит
y <= 7 - столько команд -4 может быть для получения положительного числа.
Так как команд -4 в программе может вообще не быть, то количество команд -4 в программах можно записать как [0..7]. Выходит, что всего таких программ 8.
| 
