Консультация онлайн # 161012

Раздел: С / С++
Автор вопроса: Haji Kemal Erimez
Дата: 20.02.2009, 17:31 Консультация неактивна
Поступило ответов: 0
Здравствуйте!
Никак не могу решить задачи...
Помогите решить пожалуйста задачи по комбинаторики...

№1:
Нолики


Для заданных натуральных чисел N и K требуется вычислить количество чисел от 1 до N, имеющих в двоичной записи ровно K нулей.

Например, если N=8 и K=1, то мы можем записать все числа от 1 до 8 в двоичной системе счисления:

1, 10, 11, 100, 101, 110, 111 и 1000.

Откуда видно, что только числа 10, 101 и 110 имеют ровно один ноль в записи, т.е. правильный ответ – 3.

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

В единственной строке входного файла INPUT.TXT записано два натуральных числа через пробел N и K, не превышающих 1000000000.

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

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число — количество чисел от 1 до N с K нулями в двоичном представлении.

Примеры:
1. input.txt: 8 1
output.txt: 3
2. input.txt: 13 2
output.txt: 4
3. input.txt: 1000 5
output.txt: 210

Цифры могут быть очень большими. Программа должна работать до 1000000000.

№2:
Степень перестановки
(Время: 1 сек. Память: 16 Мб Сложность: 46%)

Требуется вычислить степень заданной перестановки.

Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N. Количество различных перестановок порядка N равно PN = N!

Пусть у нас есть упорядоченное множество из N элементов. Перестановка задает преобразование этого множества. А именно, она говорит, что на i место нужно поставить ai элемент множества, где ai - i-тый элемент перестановки.

Обратной перестановкой к перестановке π называется такая перестановка π-1, что ππ-1 = π-1π = ε, где ε – тождественная перестановка.

Степенью перестановки называется минимальное натуральное число k такое, что πk = ε

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

В первой строке входного файла INPUT.TXT записано число 0 < N <= 100 - порядок перестановки. Во второй строке записана сама перестановка.

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

В выходной файл OUTPUT.TXT выведите степень данной перестановки. Гарантируется, что ответ не превышает 1000000000.
Примеры:
input.txt:
3
2 3 1
output.txt: 3


№3:
Восстановление перестановки


Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N.

Пусть у нас есть упорядоченное множество из N элементов. Перестановка задает преобразование этого множества. А именно, она говорит, что на i место нужно поставить ai элемент множества, где ai - i-тый элемент перестановки.

Пусть дана перестановка π. Обозначим φ[i] - количество таких j, что π[j] > π[i], а j < i. φ называется таблицей инверсий перестановки π.

Требуется по данной таблице инверсий восстановить перестановку.

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

В первой строке входного файла INPUT.TXT записано число 0 < N <= 2000 - порядок перестановки. Во второй строке записана таблица инверсий.

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

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

Примеры:
1.
input.txt:
3
0 0 2
output.txt:
2 3 1


Спасибо большое за внимание !!! smile

Ответов еще не поступило.

Мини-форум консультации # 161012


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