e-olymp 157. Зоопарк

Задача взята с сайта  e-olymp.com.

Постановка задачи

В зоопарке [latex] N [/latex] клеток выстроены в ряд. В зоопарке, кроме прочих обитателей, живут две мартышки, Слава и Юра. Слава и Юра всегда были большими друзьями и сидели в соседних клетках, но теперь они поссорились и больше не хотят видеть друг друга. Смотритель уже собрался переселить их в соответствии с их желанием, однако возникла проблема. Слава и Юра — очень образованные мартышки (каждый из них закончил аж по восемь классов!), и они непременно хотят знать, сколько всего существует способов расселить их так, чтобы их клетки не были соседними, и уж конечно их клетки должны быть различными. Можно считать, что все  [latex] N [/latex] клеток доступны, остальные обитатели зоопарка готовы переехать куда угодно.

Входные данные:

В первой строке входных данных находится число [latex] N [/latex]  [latex](2\leq N\leq 100)[/latex] — количество клеток в зоопарке.

Выходные данные:

Выведите одно число — количество способов поселить Славу и Юру в разные клетки так, чтобы эти клетки не были соседними.

Тесты

4 6
15 182
30 812
48 2162
60 3422

Реализация

Здесь находится код в ideone.com

Решение

Рассмотрим  возможные расположения клеток при условии, что  одна из обезьян занимает первую клетку. Очевидно, что другая обезьяна не может занимать первую и вторую клетки, т к клетки должны быть разными и не соседними. Следовательно, существует [latex] (n — 2) [/latex] вариантов расположения второй обезьяны. Далее предположим, что первая обезьяна занимает вторую клетку. Тогда  количество вариантов расположения второй обезьяны равно [latex] (n-2-1) = (n-3) [/latex] . И так далее, до тех пор пока не останется один вариант расположения второй обезьяны. Таким образом, ключ к решению задачи лежит в рассмотрении количества вариаций расположения клеток обезьян как  арифметической  прогрессии. Исходя из условия задачи, нам необходимо найти сумму первых [latex] n [/latex]  членов прогрессии. Формула для вычислений: [latex] S=\frac{(a_1 + a_k}{2}*k [/latex], где  [latex] a_1=n-2 [/latex] и [latex] a_k=1 [/latex], и [latex] k=n-2 [/latex].  Применяя математические преобразования, получаем что [latex] S=\frac{(n-1) * (n-2)}{2} [/latex]. Однако,  имеет значение не только, непосредственно,  какие две клетки заняты, но и какая именно из обезьян занимает определенную клетку. То есть при [latex] n=3 [/latex] мы имеем лишь пару клеток, которые можем использовать, но два способа поселения. Следовательно, полученное выражение необходимо умножить на два. Таким образом, мы вывели необходимую нам формулу.

Выполненное задание на сайте  e-olimp.com здесь.

Related Images: