#93

Мирные ферзи

Темы: [Разные комбинаторные структуры] [Рекурсия] [Перебор]

Дано число N. Определите, сколькими способами можно расставить на доске N×N N ферзей, не бьющих друг друга.

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

Задано единственное число N. (N ≤ 10)

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

Необходимо вывести количество способов, которыми можно расставить на доске N×N N ферзей, не бьющих друг друга.

Примеры

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

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

#94

Мирные ферзи (без поворотов и отражений)

Темы: [Разные комбинаторные структуры] [Рекурсия]

Дано число N. Определите, сколькими способами можно расставить на доске N×N N ферзей, не бьющих друг друга. Расстановки ферзей, которые можно получить друг из друга поворотами и отражениями доски, нужно считать за одно.

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

Задано единственное число N. (N ≤ 10)

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

Необходимо вывести количество способов, которыми можно расставить на доске N×N N ферзей, не бьющих друг друга.

Примеры

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

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

#155

Генератор

Темы: [Размещения с повторениями] [Разные комбинаторные структуры]

Максимальное время работы на одном тесте:

2 секунды

Даны два натуральных числа N и K. Требуется вывести все цепочки x₁, x₂, ..., x_N такие, что x_i - натуральное и 1 ≤ x_i ≤ K.

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

Вводятся два натуральных числа N и K (N, K ≤ 6).

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

Выведите все требуемые цепочки в произвольном порядке – по одной на строке. Никакая цепочка не должна встречаться более одного раза.

Примеры

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

2 3

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

#193

Гладкие числа

Темы: [Разные комбинаторные структуры]

Максимальное время работы на одном тесте:

1 секунда

Назовем число гладким, если его цифры, начиная со старшего разряда, образуют неубывающую последовательность. Упорядочим все такие числа в возрастающем порядке и присвоим каждому номер. Вам требуется по номеру N вывести N-ое гладкое число.

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

На вход программы поступает номер N (1 <= N <= 2147483647).

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

Выведите соответствующее номеру N гладкое число.

Примеры

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

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

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

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

#517

Дробь

Темы: [Разные комбинаторные структуры] [Простые числа и разложение на множители]

Источники: [ Командные олимпиады, ВКОШП, 2003, Задача B ]

Дано выражение p1/p2/.../pn. Требуется определить, сколько различных значений и целых значений оно может принимать при всевозможных расстановках скобок.

Известно, что сложение и умножение являются ассоциативными операциями. Это значит, что значение выражений вида \(a_1\) + \(a_2\) +...+ \(a_n\) и \(a_1\) . \(a_2\) . ... . \(a_n\) не зависит от порядка выполнения в них действий и, следовательно, не меняется при произвольной расстановке в этих выражениях скобок.

В отличие от сложения и умножения, деление – операция не ассоциативная. Так, значение выражения вида \(a_1\)/\(a_2\)/ ... /\(a_n\) может меняться при расстановке в нем скобок.

Рассмотрим выражение вида

\(p_1\)/\(p_2\)/ ... /\(p_n\),

где все \(p_i\) – простые числа (не обязательно различные). Найдите количество возможных значений, которые может принять указанное выражение после расстановки в нем скобок, а также количество целых чисел среди этих значений. Например, выражение 3/2/2 после расстановки скобок может принять два значения: 3/4 = (3/2)/2 и 3 = 3/(2/2).

В первой строке вводится число \(n\) ( 1\( \le\)n\( \le\)200). Следующая строка содержат \(n\) натуральных чисел – \(p_1\), \(p_2\),..., \(p_n\). Все числа \(p_i\) простые и не превосходят \(10^4\).

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

В первой строке выведите количество возможных значений, которые может принять выражение \(p_1\)/\(p_2\)/ ... /\(p_n\) при заданных \(p_i\) после расстановки в нем скобок. Во второй строке выведите количество целых чисел среди этих значений.

Примеры

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

3
3 2 2

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

2
1