Темы --> Информатика --> Алгоритмы --> Перебор --> Комбинаторные структуры
    Размещения с повторениями(11 задач)
    Перестановки(20 задач)
    Сочетания(5 задач)
    Разбиения(9 задач)
    Разные комбинаторные структуры(17 задач)
    Генерация по номеру(2 задач)
---> 59 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 6 7 8 9 10 11 12 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Дана скобочная последовательность. Необходимо определить количество циклических сдвигов, переводящих ее в правильную.

Встретились однажды три культорга ЛКШ...

  • Первый культорг написала мелом на доске скобочную последовательность.
  • Второму культоргу стало интересно, существует ли циклический сдвиг, превращающий эту последовательность в правильную.
  • Третий же культорг, немного подумав, сказал, сколько таких сдвигов существует.

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

Циклическим сдвигом строки называется перенос некоторого (возможно, нулевого) количества символов из конца строки в её начало без изменения их порядка.

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

В единственной строке дана скобочная последовательность, записанная первым культоргом. Длина последовательности не равна нулю и не превышает \(100\,000\) символов.

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

Выведите количество циклических сдвигов, превращающих записанную скобочную последовательность в правильную.

Примеры
Входные данные
)(()
Выходные данные
1
Входные данные
)()(
Выходные данные
2
Входные данные
()

Выходные данные
1
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

У мальчика Васи есть \(N\) шоколадок (возможно, разного веса). Вася пригласил к себе в гости \(K\) своих друзей и хочет подарить им шоколадки. Чтобы никому из друзей не было обидно, Вася решил раздать шоколадки так, чтобы каждому другу досталось одно и то же количество шоколада (т.е. суммарный вес шоколадок, доставшихся каждому другу, должен быть одинаковым). Вася может раздать все свои шоколадки, может раздать лишь часть, но, поскольку он — очень гостеприимный мальчик, он не хочет оставлять друзей совсем без шоколада (т.е. сумма весов шоколадок, доставшихся каждому другу, должна быть строго положительной). Все шоколадки красиво упакованы, т.е. делить их на части нельзя.

Определите, сколько у Васи есть способов раздать шоколад своим друзьям. Два способа считайте различными тогда и только тогда, когда существует шоколадка, которая в одном способе досталась некоторому другу, а в другом — другому другу или вовсе не была отдана друзьям.

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

В первой строке входного файла находятся два натуральных числа \(N\) и \(K\) (\(1 \leq N \leq 15\), \(1 \leq K \leq 15\)) — количество шоколадок у Васи и количество друзей, которых Вася пригласил в гости. Во второй строке содержатся \(N\) натуральных чисел — веса шоколадок. Ни один из весов не превосходит \(1000\).

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

Выведите в выходной файл одно число — количество способов раздать шоколадки друзьям.

Примечание

Во втором примере возможные распределения шоколадок следующие:

  1. Первому другу дать шоколадку номер 1, второму — номер 2;
  2. Первому другу дать шоколадку номер 2, второму — номер 1;
  3. Первому другу дать шоколадку номер 3, второму — шоколадки номер 1 и 2;
  4. Первому другу дать шоколадки номер 1 и 2, второму — номер 3.

Примеры
Входные данные
5 4
1 2 1 1 1

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

Входные данные
3 2
1 1 2

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

ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Маленький Вася очень любит поезда. На день рождения ему подарили игрушечную железную дорогу. В комплект к железной дороге входит поезд, состоящий из \(n\) вагонов, пронумерованных числами от 1 до \(n\).

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

Справа к тупику подъезжает поезд, составленный из всех \(n\) вагонов. Затем вагоны по одному загоняются в сортировочный тупик и выгоняются из него налево. Васе нравится, если ему удается отсортировать поезд с помощью сортировочного тупика — добиться того, чтобы слева от тупика вагоны были расположены по порядку от 1 до \(n\).

Например, пусть в исходном поезде 4 вагона, которые следуют в порядке 3, 1, 2, 4. Его можно отсортировать следующим образом. Загоняем вагон 3 в тупик. Загоняем вагон 1 в тупик. Выгоняем вагон 1 из тупика. Загоняем вагон 2 в тупик. Выгоняем вагон 2 из тупика. Выгоняем вагон 3 из тупика. Загоняем вагон 4 в тупик. Выгоняем вагон 4 из тупика.

Не все поезда можно отсортировать таким образом. Например, поезд из 3 вагонов, следующих в порядке 2, 3, 1, отсортировать нельзя.

Вася выписал на листке в лексикографическом порядке все поезда длины \(n\), которые можно отсортировать с помощью тупика. Поезд \((a_1, a_2, \ldots, a_n)\) идет раньше поезда \((b_1, b_2, \ldots, b_n)\) в лексикографическом порядке, если существует такое \(i\) (\(1 \le i \le n\)), что для всех \(j < i\) выполняется \(a_j = b_j\), а \(a_i < b_i\). Например, все поезда из трех вагонов, которые можно отсортировать с помощью тупика, в лексикографическом порядке выписываются следующим образом: \((1, 2, 3)\), \((1, 3, 2)\), \((2, 1, 3)\), \((3, 1, 2\)), \((3, 2, 1)\).

Вася потерял свой листок, и его интересует вопрос: какой поезд был выписан на его листке под номером \(k\). Помогите ему выяснить это.

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

Входной файл содержит два целых числа — \(n\) и \(k\) (\(1 \le n \le 30\), \(1 \le k \le 10^{18}\)).

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

Выведите в выходной файл \(n\) целых чисел: \(k\)-й в лексикографическом порядке поезд из \(n\) вагонов, который можно отсортировать с помощью тупика.

Если с помощью тупика можно отсортировать менее \(k\) поездов из \(n\) вагонов, выведите \(-1\).

Примеры тестов
Входные данные
4 1
Выходные данные
1 2 3 4
Входные данные
4 3
Выходные данные
1 3 2 4
Входные данные
4 15
Выходные данные
-1
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
8 megabytes

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

Напишите программу, которая найдет минимальную стоимость такой сортировки заданной последовательности.

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

Входной файл содержит две строки. Первая строка содержит положительное целое число n (1000 > n > 1) — количество чисел, которые требуется отсортировать. Вторая строка содержит n различных чисел (каждое положительное и не больше 1000), которые надо отсортировать.

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

Выведите одну строку, содержащую минимальную стоимость сортировки чисел как показано в примере.

Примеры
Входные данные
3
3 2 1
Выходные данные
4
Входные данные
4
8 1 2 4
Выходные данные
17
Входные данные
5
1 8 9 7 6
Выходные данные
41
Входные данные
6
8 4 5 3 2 7
Выходные данные
34

Страница: << 6 7 8 9 10 11 12 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест