Задача взята с сайта 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 |
Реализация
|
1 2 3 4 5 6 7 8 9 10 11 |
#include <iostream> using namespace std; int main() { int n; // количество клеток int c; //количество способов поселения cin >> n; c = (n - 1) * (n - 2); cout << c; return 0; } |
Здесь находится код в 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 здесь.