A1029

Іванов Вячеслав Володимирович
Іванов Вячеслав Володимирович

Latest posts by Іванов Вячеслав Володимирович (see all)

Задача о восьми мирных ладьях

Задача о восьми мирных ладьях

Условие

Получить все расстановки   [latex]8[/latex]   ладей на шахматной доске, при которых ни одна ладья не угрожает другой.


Решение

Для начала, выясним, а сколько существует таких расстановок, при условии, что рассматривается стандартная шахматная доска   [latex]8 \times 8[/latex].

Ладья находится под боем, если другая ладья находится с ней на одной строке или в одном столбце. Следовательно, фиксируя, скажем, столбцы, можно разместить ладьи по строкам таким образом, чтобы ни одна пара не находилась под боем.

Заведем массив на восемь элементов и занумеруем его таким образом, чтобы значение   [latex]j[/latex]   по индексу   [latex]i[/latex]   соответствовало строке [  [latex]j[/latex],   в которой находится ладья в   [latex]i[/latex]-м столбце.

Теперь легко видеть, что положение на доске определяется перестановкой чисел   [latex]1,..,8[/latex].   Как известно, число различных перестановок длины [latex]n[/latex]   —   [latex]P_{n}=n![/latex]. Следовательно, всего существует   [latex]8!=40320[/latex]   различных расстановок ладей.

Реализация
ideone: http://ideone.com/tBySY4
Легенда: R — Rook — ладья


Детали реализации

Для получения перестановок использована функция стандартной библиотеки [latex]next\_permutation()[/latex]

В силу большого объёма выходного файла (5.5 мб) он доступен отдельно, по ссылке: https://www.dropbox.com/s/yyaz7vq08jczsnl/out?dl=0

А1033

Марченко Філіп Олександрович
Марченко Філіп Олександрович

Latest posts by Марченко Філіп Олександрович (see all)

Условие

Получить все размещения из [latex]9[/latex] элементов [latex]\left\{1,2, \ldots, 9\right\}[/latex] по [latex]5[/latex] элементов в каждом.

Код на С++

 

Код на Java:

 

Решение

При решении этой задачи мне понадобились 2 источника информации:

Там были приведены алгоритмы генерирования перестановок («Комбинаторные алгоритмы», стр. 27-29) и генерирования сочетаний («Комбинаторика для программистов», стр. 39-41).
Размещения я получал следующим образом:

  • Посчитал кол-во всевозможных размещений по формуле [latex]A^{k}_{n}=\frac{n!}{(n-k)!}=\frac{9!}{4!}=15120[/latex];
  • Заметил, что размещения — это перестановки всех уникальных комбинаций из 5 чисел (т.е сочетаний);
  • Поскольку кол-во перестановок [latex]P_{k}=k![/latex], а кол-во сочетаний — [latex]C_{n}^{k}=\frac{n!}{k!(n-k)!}[/latex], то кол-во размещений [latex]A_{n}^{k}=P_{k}\times{C_{n}^{k}}=\frac{n!k!}{k!(n-k)!}=\frac{n!}{(n-k)!}=15120[/latex];

Таким образом, генерируя вначале сочетание, я генерировал перестановки этого сочетания. В результате вышло 15120 размещений.

e-olimp 4475. Часы

Іванов Вячеслав Володимирович
Іванов Вячеслав Володимирович

Latest posts by Іванов Вячеслав Володимирович (see all)

4475. Часы

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

Ученые разработали часы, которые могут налаживаться для отсчета времени на любой планете. Они состоят из шариков, лотка (очереди) и трех чаш: секундной, минутной и часовой. В каждый момент времени количество шариков в чашах показывает время (секунды, минуты и часы соответственно). Каждую секунду первый шарик из очереди попадает в секундную чашу. Если секундная чаша наполнилась (количество шариков равно количеству секунд в минуте на этой планете), то этот шарик переходит в минутную чашу, а остальные шарики переходят из секундной чаши в конец очереди в порядке, обратном к их попаданию в секундную чашу. Аналогично, при наполнении минутной чаши последний шарик переходит в часовую чашу, а остальные шарики из минутной чаши переходят в конец очереди в порядке, обратном к их попаданию в минутную чашу. Если заполняется часовая чаша, то все шарики из нее переходят в конец очереди в порядке, обратном к их попаданию в часовую чашу. Все шарики пронумерованы и в начальный момент времени находятся в очереди.

Написать программу, вычисляющую минимальное количество суток, необходимых для того, чтобы начальное положение шариков в очереди повторилось.

Во входном потоке содержится количество секунд в минуте [latex]S[/latex], минут в часе [latex]M[/latex], часов в сутках [latex]H[/latex] и число шариков [latex]K[/latex].

Алгоритм решения

  1. Интуитивно понятно, что положение шариков в очереди ежесуточно изменяется по одному и тому же закону, в силу однообразия процесса. Отыскать конкретный вид перестановки можно прямым моделированием часов, используя дек для описания лотка и стеки — каждой из чаш (у очереди задействованы оба конца, у чаш — только один).
  2. Определить порядок суточной перестановки можно и возведением её в степень, но это нерациональный способ. Используя теорему о разложении перестановки в композицию циклов (к слову, непересекающихся), можно заметить, что порядок каждого из циклов равен его длине. Если мысленно представить перестановку в виде ориентированного графа, то процесс поиска циклов сведётся к поиску в глубину: обойти каждую компоненту связности, зафиксировать число входящих в неё вершин (на илл.)
  3. Зная длины всех циклов, нетрудно заметить, что задача сводится к поиску НОК полученной последовательности длин. Обосновать такой переход можно индуктивно: порядок перестановки, представимой в виде композиции двух циклов, равен НОК их длин, а случай большего количества циклов в разложении сводится к рассмотренному последовательным рассмотрением пар циклов (результат не зависит от порядка рассмотрения в силу ассоциативности композиции).

Реализация:

ideone: http://ideone.com/nz2JlG
Засчитанное решение: http://www.e-olimp.com/solutions/1937971

Примечания

  • Экспериментально выяснено, что только тип long double является достаточно вместительным для избежания переполнения.
  • Операция взятия остатка для чисел с плавающей точкой не определена аппаратно, так что алгоритм Евклида вычисления НОД реализован в соответствии с его математическим описанием.
  • Модификатор fixed используется для предотвращения вывода чисел в научном формате (с использованием степеней десятки).

А36

Гусак Дмитро Євгенович
Гусак Дмитро Євгенович

Latest posts by Гусак Дмитро Євгенович (see all)

Задача: Даны действительные числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex]Проверить, выполняются ли неравенства  [latex]a<b<c[/latex].

Тесты:

Ввод Вывод Результат
a b c неравенство                     не выполнено
2 1 3 b<=a<c: нер-во a<b<c                 не выполняется неравенство                     не выполнено
1 3 2 a<=c<=b: нер-во a<b<c                 не выполняется неравенство                     не выполнено
3 1 2 b<=c<=a: нер-во a<b<c                 не выполняется неравенство                     не выполнено
3 2 1 c<=b<=a: нер-во a<b<c                 не выполняется неравенство                     не выполнено
2 3 1 c<=a<b: нер-во a<b<c                 не выполняется неравенство                     не выполнено
1 2 3 нер-во a<b<c справедливо неравенство выполнено

Код программы:

Отчет:

После ввода чисел a, b, c программа проверит их соотношения. Ввиду наличия трех сравниваемых чисел имеем 3! = 6 возможных комбинаций чисел, и только одна из них соответствует требованию. Если неравенство [latex]a<b<c[/latex] имеет место быть, то программа сообщит о его выполнении. В противном же случае консоль выдаст ответ о не выполненном неравенстве, предварительно сообщив причину.

Копия кода на сайте Ideone: ideone.com/aYmMJ2