Программирование+ + настольные игры с ИКИТом. Выпуск №8

Минимальная стоимость проезда (332)
Ссылка
сложность

Минимальная стоимость проезда (332)
Будем определять минимальную стоимость проезда до [i] станции, где [i] меняется от 1 до n.
Очевидно, что для [0] станции стоимость проезда до неё равна 0.
Для первой станции есть только один вариант доехать до неё, с нулевой станции.
Для второй станции уже два варианта, либо мы едем с нулевой станции, либо сначала оптимально до первой, а от неё уже на вторую.

Минимальная стоимость проезда (332)
Пример:
4
7 10 20 38
4 8 10
2 12
10
Станции [i]: 0 1 2 3 4
Минимальная стоимость проезда: 0 7 10 12 17

Чунга-Чанга (1181А)
Ссылка
сложность

Чунга-Чанга (1181А)
Саша и Маша точно могут купить n = [x/z] + [y/z] кокосов.
Если на оставшиеся деньги (то есть r = x mod z + y mod z) нельзя купить кокос (r
Если можно, то нужно узнать, сколько нужно денег передать, то есть q = min(n- (x mod z), n-(y mod z)) и ответ cout<

Разделение числа (1181B)
Ссылка
сложность

Разделение числа (1181B)
Найдем место разреза линии. Будем начинать делить строку от середины, и бежать указателем в разные стороны, пока символ строки равен ‘0’ (так как число при разделении не имеет ведущих нулей).
Найдем первое корректное разделение в левую и первое корректное разделение в правую сторону. Может быть и такая ситуация, что корректных разделений в одну из сторон нет, это тоже нужно учесть (пример: 1000010 не имеет корректных разделений в левую сторону).

Разделение числа (1181B)
После этого, делим строку на две (можно воспользоваться функцией substr) и складываем их как числа (на python это удобнее, так как там реализована длинная арифметика).
Проверяем, какое число меньше, при делении в левую или при делении в правую сторону. Меньшее и будет ответом.
Пример:

Флаг (1181C)
Ссылка
сложность

Флаг (1181C)
Динамическое программирование:
Будем хранить в каждой позиции матрицы помимо символа также информацию о начальной позиции, когда полоска в высоту одного и того же цвета заканчивается, а также, сколько флагов можно составить, если они имеют правый нижний угол в данной позиции.
Пример: Полученная матрица:
4 3
aaa (a 0 0) (a 0 0) (a 0 0)
bbb (b 1 0) (b 1 0) (b 1 0)
ccb (c 2 1) (c 2 2) (b 1 0)
ddd (d 3 1) (d 3 2) (d 3 0)

Флаг (1181C)
Пример: Полученная матрица:
4 3
aaa (a 0 0) (a 0 0) (a 0 0)
bbb (b 1 0) (b 1 0) (b 1 0)
ccb (c 2 1) (c 2 2) (b 1 0)
ddd (d 3 1) (d 3 2) (d 3 0)
Итоговый ответ будет сумма всех ответов в каждой ячейки.
Как быстро находить частичные ответы? Нужно проверить, можно ли получить флаг, рассматривая только текущий столбец. Если можно, то смотрим, чтобы слева от текущей позиции были бы такие же цвета, и с такой же высотой полоски. Если это так, суммируем текущий ответ в ответом в ячейке левее.

4 3 Полученная матрица: Ответ:12
aaa (a 0 0) (a 0 0) (a 0 0)
bbb (b 1 0) (b 1 0) (b 1 0)
aaa (a 2 1) (a 2 2) (a 2 3)
ddd (d 3 1) (d 3 2) (d 3 3)
7 3 Полученная матрица: Ответ:7
cdq (c 0 0) (d 0 0) (q 0 0)
cec (c 0 0) (e 1 0) (c 1 0)
bcc (b 2 0) (c 2 1) (c 1 0)
abb (a 3 1) (b 3 1) (b 3 0)
aaa (a 3 0) (a 4 1) (a 4 2)
afa (a 3 0) (f 5 1) (a 4 0)
afa (a 3 0) (f 5 0) (a 4 0)
Флаг (1181C)

Нажатия на кнопки (102168G)
Ссылка
сложность

Нажатия на кнопки (102168G)
Для случая, когда одна или две кнопки, решим задачу отдельно. Будем рассматривать случай, когда n≥3.
Пусть s1 – сумма всех чисел до нажатий, а s2 – после нажатий.
Введем обозначения. Для [i] кнопки: a[i] – число на кнопке до нажатий, b[i] – число на кнопке после нажатий, x[i] – количество нажатий на [i] кнопку.

Нажатия на кнопки (102168G)