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 здесь.

9 thoughts on “e-olymp 157. Зоопарк

  1. Считает правильно, но…
    — Даже один символ N это уже формула. Нужен latex. Оформите везде по тексту формулы в latex.
    — Вы пишите «Объявим переменную n». Не нужно пересказывать на обычном языке код программы. Это бессмысленная работа. Нужно описать ход решения, вывод формулы и т.п. Назначение переменных можно указать в комментариях прямо в коде программы.
    — «Зоопарк» это не ключевое слово, а название задачи. Перечитайте свой текст и выделите важные слова.
    — «щелкните здесь» звучит как-то не очень. Гиперссылка нужна, но «щелкать» на ней пользователь должен догадаться сам.
    — (n-2)+(n-3)+(n-4)+…+1 это не прогрессия.
    — Пояснение ни куда не годится. Нужно логически вывести формулу. Нужно объяснить как Вы считаете варианты, как получаете арифметическую прогрессию. И формула арифметической прогрессии существенно проще того, что Вы накодировали.
    — «Для вопроса на выполнение…» это я вообще не понял.

  2. Очень хорошо. Почти великолепно.
    Ещё одну-две фразы уточним и будет зачтено.
    0. Что Вы имеете в виду под «алгебраическая прогрессия»?
    1. Не могу разобраться со стилистической и смысловой мотивацией употребления слова «оный» в данном контексте. Возможно здесь далеко не полный анализ и вы уточните свои мотивы? Нет, я догадываюсь, что это обычная референция к объекту «клетка», упоминаемому ранее в предложении. Но там не одна клетка, а две.
    2. «Исходя из вышесказанного» — это снова стилистическая ошибка. Такой оборот не используют в математических текстах. Он больше характерен для официальной переписки юридической или дипломатической направленности. Математики пишут «следовательно», «тогда получаем» и т.п. Да и то, только в том случае, когда действительно имеет место логическое следование.
    3. «Условие задачи смотреть здесь» — стилистически неуместное употребление императивного наклонения. Не стоит пугать читателя приказным тоном у него может не быть склонности к подчинению. Тем более условие полностью приводится тут же. Нам важно только указать на источник откуда взята задача, чтобы не нарушать авторские права. А смотреть или не смотреть этот источник дело читателя.

    P.S. Понимаю, что запрещая использовать приёмы стилистического диссонанса я снижаю литературную ценность публикации, но ведь всегда остаётся proza.ru, где можно было бы опубликовать авторский вариант. Думаю, это было бы интересным новаторством — творческое литературное описание решения задачи. Но всё новое — хорошо забытое старое. Когда-то любили описывать алгоритмы в стихах.

    • Спасибо,очень хороший сайт. Я исправила указанные стилистические ошибки. Под алгебраической прогрессией я подразумеваю последовательность чисел, в которой каждое число, начиная со второго, получается из предыдущего добавлением к нему постоянного числа d. Надеюсь, уместно то, что я оставила эту ссылку в описании решения задачи.

Добавить комментарий