ЛАБОРАТОРНАЯ №2. Комбинаторика. Формат входного файла. Формат выходного файла. Примеры. Примеры. C. Задача о восьми ферзях

ЛАБОРАТОРНАЯ №2

Комбинаторика

Input file name:	input. txt
Output file name:	output. txt
Time limit (per test case):	1 sec
Memory limit (per test case):	64 MB
Score:	100 points

A. Суммарная полезность (тема: генерация всех подмножеств)

Дано n предметов, каждый из которых характеризуется весом w_i и полезностью p_i. Необходимо выбрать некоторый набор этих предметов так, чтобы суммарный вес этого набора не превышал W, а суммарная полезность была максимальна.

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

Формат входного файла

Первая строка входного файла содержит натуральные числа n (1≤ n≤ 20) и W (1≤ W≤ 10⁹). Каждая из последующих n строк содержит описание одного предмета. Каждое описание состоит из двух чисел: w_i — веса предмета и p_i — его полезности (1≤ w_i, p_i≤ 10⁹).

Формат выходного файла

В первой строке выходного файла выведите максимальную суммарную полезность.

Примеры

input. txt	output. txt
2 10 10 100 9 80
5 100 80 1000 50 550 50 550 50 550 50 550
6 100 80 1000 50 550 50 550 50 550 50 550 100 1100

B. Перестановки
Дана строка, состоящая из M попарно различных символов. Вывести все перестановки символов данной строки.

Ограничения: 2 ≤ M≤ 8, символы - буквы латинского алфавита и цифры.

Ввод: В первой строке файла находится исходная строка.

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

Примеры

INPUT. TXT	OUTPUT. TXT
AB	AB BA
IOX	XOI OIX IXO XIO OXI IOX

C. Задача о восьми ферзях

Расположения восьми ферзей, которые не бьют друг – друга пронумерованы в лексикографическом порядке (симметричные решения считать решением). Найти k -е расположение.

Ввод: В первой строке файла находится целое число k.

Вывод: В первой строке вывести ответ.