Разбор задачи про шахматную доску из тестового в интернет-серв | No Data No Growth | Pavel Bukhtik

Разбор задачи про шахматную доску из тестового в интернет-сервис объявлений.

Чтобы добраться до нижнего правого угла, независимо от выбранного пути, шашке нужно совершить N-1 шагов вправо и N-1 шагов вниз. Итого, 2*(N-1) шагов.

Пусть 0 и 1 – шаги вниз и вправо соответственно.

Рассмотрим ленту из 2*(N-1) ячеек, содержащие 0.

(0 0 0 0 0 0 для N=4)

Теперь задача сводится к количеству вариантов замены 0 для N-1 ячеек на 1.

(0 0 1 0 0 1 1 для N=4 )

Т. е., условно, есть 2*(N-1) ячеек, сколько есть вариантов выбрать N-1 из них?

Получаем через количество сочетаний – C(2*(N-1), N-1).

Если N было бы задано в виде конкретного числа, то задачу можно было бы также решить с помощью треугольника паскаля. Центральное значение из нижней строки треугольника с глубиной 2*(N-1) и было бы искомым значением.

Быстрее всех ответ на задачу дал @art290790. Спасибо @maxlukyanenko за самое развернутое решение. @AlexeyMalafeev – отдельное спасибо за альтернативное решение. Молодцы

Остались вопросы или что-то непонятно? Спрашивайте в комментариях или л. с.)

#задачиссобеседований