Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамика по подмножествам
    meet in the middle(4 задач)
---> 2 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: 1 Отображать по:
#1212
Перестановки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
K-перестановкой чисел называется такая перестановка, в которой НОД соседних чисел не меньше K. Заданы числа из которых необходимо построить N-ую перестановку в лексикографическом порядке.

Задано множество из n различных натуральных чисел. Перестановку элементов этого множества назовем k-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее k. Например, если задано множество элементов S = {6, 3, 9, 8}, то перестановка {8, 6, 3, 9} является 2-перестановкой, а перестановка {6, 8, 3, 9} – нет.

Перестановка {p1, p2, …, pn} будет лексикографически меньше перестановки {q1, q2, …, qn}, если существует такое натуральное число i (1 ≤ i ≤ n), для которого pj = qj при j < i и pi < qi.

В качестве примера упорядочим все k-перестановки заданного выше множества в лексикографическом порядке. Например, существует ровно четыре 2-перестановки множества S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} и {9, 3, 6, 8}. Соответственно, первой 2-перестановкой в лексикографическом порядке является множество {3, 9, 6, 8}, а четвертой – множество {9, 3, 6, 8}.

Требуется написать программу, позволяющую найти m-ую k-перестановку в этом порядке.

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

Входной файл в первой строке содержит три натуральных числа – n (1 ≤ n ≤ 16), m и k (1 ≤ m, k ≤ 109). Вторая строка содержит n различных натуральных чисел, не превосходящих 109. Все числа в строках разделены пробелом.

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

В выходной файл необходимо вывести m-ую k-перестановку заданного множества или –1, если такой нет.

Разбалловка для личной олимпиады

Тесты 1-3 — из условия. Оцениваются в 0 баллов.

Тесты 4-17 — \(n\le 4\). Группа тестов оценивается в 28 баллов.

Тесты 18-28 — \(n\le 10\). Группа тестов оценивается в 22 балла (вместе с предыдущей группой — 50 баллов).

Тесты 29-53 — дополнительных ограничений нет. Группа тестов оценивается в 50 баллов (вместе с предыдущими группами — 100 баллов).

Баллы начисляются за прохождение всех тестов группы и всех тестов предыдущих групп. При выставлении баллов за отдельные тесты каждый тест (кроме тестов из условия) оценивается в 2 балла.

Примеры
Входные данные
4 1 2
6 8 3 9
Выходные данные
3 9 6 8
Входные данные
4 4 2
6 8 3 9
Выходные данные
9 3 6 8
Входные данные
4 5 2
6 8 3 9
Выходные данные
-1
#113570
День рождения Мирко
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 3, День рождения Мирко ]
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
512 megabytes

Мирко получил в подарок на свой день рождения квадратный стол N x N , где в каждой клетке записано неотрицательное целое число. К сожалению, некоторые числа кажутся Мирко слишком большими, поэтому он собирается положить на стол K фишек домино, которые закроют некоторые слишком большие числа. Точнее, он собирается положить фишки домино в соответствии со следующими правилами:

1. Каждая фишка домино покрывает две клетки, соседних по строчке или столбцу..

2. Фишки домино не накладываются друг на друга (но могут соприкасаться).

3. Сумма чисел на всех видимых (непокрытых) клетках минимальна.

Ваша задача - определить минимально возможную сумму чисел на видимых клетках. Тесты к задаче таковы, что на поле всегда можно положить K не накладывающихся друг на друга фишек домино.

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

Первая строка содержит два целых числа: N ( 1 ≤ N ≤ 2000 ) - размер стола, и K ( 1 ≤ K ≤ 8 ) - количество фишек домино. Каждая из следующих N строк содержит N целых чисел (в диапазоне [0, 1000]) - числа в соответствующих клетках поля.

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

Выведите единственное целое число - минимально возможную сумму чисел в клетках после установки фишек домино.

Примечание

Решения, работающие при K ≤ 5 , будут оцениваться в 70 баллов.

Примеры
Входные данные
3 1
2 7 6
9 5 1
4 3 8
Выходные данные
31
Входные данные
4 2
1 2 4 0
4 0 5 4
0 3 5 1
1 0 4 1
Выходные данные
17
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест