•PAN (Personal Area Network) — персональная сеть, предназначенная для взаимодействия различных устройств, принадлежащих одному владельцу. •LAN (Local Area Network) — локальные сети, имеющие замкнутую инфраструктуру до выхода на поставщиков услуг. Термин «LAN» может описывать и маленькую офисную сеть, и сеть уровня большого завода, занимающего несколько сотен гектаров. Зарубежные источники дают даже близкую оценку — около шести миль (10 км) в радиусе. Локальные сети являются сетями закрытого типа, доступ к ним разрешен только ограниченному кругу пользователей, для которых работа в такой сети непосредственно связана с их профессиональной деятельностью. •CAN (Campus Area Network — кампусная сеть) — объединяет локальные сети близко расположенных зданий. •MAN (Metropolitan Area Network) — городские сети между учреждениями в пределах одного или нескольких городов, связывающие много локальных вычислительных сетей. •WAN (Wide Area Network) — глобальная сеть, покрывающая большие географические регионы, включающие в себя как локальные сети, так и прочие телекоммуникационные сети и устройства. Пример WAN — сети с коммутацией пакетов (Frame relay), через которую могут «разговаривать» между собой различные компьютерные сети. Глобальные сети являются открытыми и ориентированы на обслуживание любых пользователей. •Термин «корпоративная сеть» также используется в литературе для обозначения объединения нескольких сетей, каждая из которых может быть построена на различных технических, программных и информационных принципах.
По типу функционального взаимодействия
•Клиент-сервер •Смешанная сеть •Одноранговая сеть •Многоранговые сети
По типу сетевой топологии
•Шина •Кольцо •Двойное кольцо •Звезда •Ячеистая •Решётка •Дерево •Fat Tree
По типу среды передачи
•Проводные (телефонный провод, коаксиальный кабель, витая пара, волоконно-оптический кабель) •Беспроводные (передачей информации по радиоволнам в определенном частотном диапазоне)
По функциональному назначению
•Сети хранения данных •Серверные фермы •Сети управления процессом •Сети SOHO, домовые сети
По скорости передач
•низкоскоростные (до 10 Мбит/с) , •среднескоростные (до 100 Мбит/с) , •высокоскоростные (свыше 100 Мбит/с) ;
По сетевым операционным системам
•На основе Windows •На основе UNIX •На основе NetWare •На основе Cisco
По необходимости поддержания постоянного соединения
•Пакетная сеть, например Фидонет и UUCP •Онлайновая сеть, например Интернет и GSM
Я буду думать, что сочетание - набор нулей и единиц, в котором на i-м месте стоит 0, если i-й буквы нет в сочетании, и 1, если она есть. Тогда, например, (0111) соответствует bcd. Общее число чисел по условию N, число единиц равно K. Этот список упорядочен по убыванию, и нам необходимо найти M-е число в этом списке. Всего число выбрать K элементов из N равно C_N^K ("цэ из N по K"). Поймем, например, надо ли брать 1-й элемент. Всего сочетаний, где первый элемент взят: C_(N-1)^(K-1) {в самом деле, в этом случае осталось выбрать K-1 из оставшихся N-1}; не взят: C_(N-1)^K. Учитывая, что те, в которые первый элемент входит, идут перед теми, в которые он не входит, решаем: если M > C_(N-1)^(K-1), 1-й элемент не берём, иначе берём. Дальше если 1-й взяли, M оставляем таким же, если нет - уменьшаем на C_(N-1)^(K-1). Процесс повторяем, пока не найдем все буквы. Осталось понять, как считать C_N^K. Исходя из рассуждений выше, C_N^K = C_(N-1)^(K-1) + C_(N-1)^K. Кроме того, C_N^0 = 1 для всех N, C_N^K = 0 при K < 0 или K > N. Пользуясь этим, можно найти все C_N^K. Не забываем про длинную арифметику: C_N^K может не влезать в обычные типы данных. Я буду писать на PascalABC.NET, там длинная арифметика есть - тип BigInteger, если нет - легко найти, как это писать. (Update: в данном случае всё влезет в longint - биномиальные коэффициенты не превысят 10 миллионов с небольшим). Итак, вот и искомый код: begin var N, K: integer; read(N, K); var M := ReadString().ToBigInteger(); var C: array[,] of BigInteger := new BigInteger[N, K]; for var j := 1 to K - 1 do C[0, j] := 0; for var i := 0 to N - 1 do C[i, 0] := 1; for var i := 1 to N - 1 do for var j := 1 to K - 1 do C[i, j] := C[i - 1, j] + C[i - 1, j - 1]; var possible := 'a'; while K > 0 do begin if M <= C[N - 1, K - 1] then begin write(possible); dec(K); end else M := M - C[N - 1, K - 1]; dec(N); inc(possible); end; end.
Без BigInteger: begin var N, K: integer; var M: longint; read(N, K, M); var C: array[,] of longint := new longint[N, K]; for var j := 1 to K - 1 do C[0, j] := 0; for var i := 0 to N - 1 do C[i, 0] := 1; for var i := 1 to N - 1 do for var j := 1 to K - 1 do C[i, j] := C[i - 1, j] + C[i - 1, j - 1]; var possible := 'a'; while K > 0 do begin if M <= C[N - 1, K - 1] then begin write(possible); dec(K); end else M := M - C[N - 1, K - 1]; dec(N); inc(possible); end; end.
•PAN (Personal Area Network) — персональная сеть, предназначенная для взаимодействия различных устройств, принадлежащих одному владельцу.
•LAN (Local Area Network) — локальные сети, имеющие замкнутую инфраструктуру до выхода на поставщиков услуг. Термин «LAN» может описывать и маленькую офисную сеть, и сеть уровня большого завода, занимающего несколько сотен гектаров. Зарубежные источники дают даже близкую оценку — около шести миль (10 км) в радиусе. Локальные сети являются сетями закрытого типа, доступ к ним разрешен только ограниченному кругу пользователей, для которых работа в такой сети непосредственно связана с их профессиональной деятельностью.
•CAN (Campus Area Network — кампусная сеть) — объединяет локальные сети близко расположенных зданий.
•MAN (Metropolitan Area Network) — городские сети между учреждениями в пределах одного или нескольких городов, связывающие много локальных вычислительных сетей.
•WAN (Wide Area Network) — глобальная сеть, покрывающая большие географические регионы, включающие в себя как локальные сети, так и прочие телекоммуникационные сети и устройства. Пример WAN — сети с коммутацией пакетов (Frame relay), через которую могут «разговаривать» между собой различные компьютерные сети. Глобальные сети являются открытыми и ориентированы на обслуживание любых пользователей.
•Термин «корпоративная сеть» также используется в литературе для обозначения объединения нескольких сетей, каждая из которых может быть построена на различных технических, программных и информационных принципах.
По типу функционального взаимодействия
•Клиент-сервер
•Смешанная сеть
•Одноранговая сеть
•Многоранговые сети
По типу сетевой топологии
•Шина
•Кольцо
•Двойное кольцо
•Звезда
•Ячеистая
•Решётка
•Дерево
•Fat Tree
По типу среды передачи
•Проводные (телефонный провод, коаксиальный кабель, витая пара, волоконно-оптический кабель)
•Беспроводные (передачей информации по радиоволнам в определенном частотном диапазоне)
По функциональному назначению
•Сети хранения данных
•Серверные фермы
•Сети управления процессом
•Сети SOHO, домовые сети
По скорости передач
•низкоскоростные (до 10 Мбит/с) ,
•среднескоростные (до 100 Мбит/с) ,
•высокоскоростные (свыше 100 Мбит/с) ;
По сетевым операционным системам
•На основе Windows
•На основе UNIX
•На основе NetWare
•На основе Cisco
По необходимости поддержания постоянного соединения
•Пакетная сеть, например Фидонет и UUCP
•Онлайновая сеть, например Интернет и GSM
Всего число выбрать K элементов из N равно C_N^K ("цэ из N по K").
Поймем, например, надо ли брать 1-й элемент. Всего сочетаний, где первый элемент взят: C_(N-1)^(K-1) {в самом деле, в этом случае осталось выбрать K-1 из оставшихся N-1}; не взят: C_(N-1)^K. Учитывая, что те, в которые первый элемент входит, идут перед теми, в которые он не входит, решаем: если M > C_(N-1)^(K-1), 1-й элемент не берём, иначе берём.
Дальше если 1-й взяли, M оставляем таким же, если нет - уменьшаем на C_(N-1)^(K-1).
Процесс повторяем, пока не найдем все буквы.
Осталось понять, как считать C_N^K. Исходя из рассуждений выше, C_N^K = C_(N-1)^(K-1) + C_(N-1)^K. Кроме того, C_N^0 = 1 для всех N, C_N^K = 0 при K < 0 или K > N. Пользуясь этим, можно найти все C_N^K. Не забываем про длинную арифметику: C_N^K может не влезать в обычные типы данных. Я буду писать на PascalABC.NET, там длинная арифметика есть - тип BigInteger, если нет - легко найти, как это писать. (Update: в данном случае всё влезет в longint - биномиальные коэффициенты не превысят 10 миллионов с небольшим).
Итак, вот и искомый код:
begin
var N, K: integer;
read(N, K);
var M := ReadString().ToBigInteger();
var C: array[,] of BigInteger := new BigInteger[N, K];
for var j := 1 to K - 1 do
C[0, j] := 0;
for var i := 0 to N - 1 do
C[i, 0] := 1;
for var i := 1 to N - 1 do
for var j := 1 to K - 1 do
C[i, j] := C[i - 1, j] + C[i - 1, j - 1];
var possible := 'a';
while K > 0 do
begin
if M <= C[N - 1, K - 1] then
begin
write(possible);
dec(K);
end
else
M := M - C[N - 1, K - 1];
dec(N);
inc(possible);
end;
end.
Без BigInteger:
begin
var N, K: integer;
var M: longint;
read(N, K, M);
var C: array[,] of longint := new longint[N, K];
for var j := 1 to K - 1 do
C[0, j] := 0;
for var i := 0 to N - 1 do
C[i, 0] := 1;
for var i := 1 to N - 1 do
for var j := 1 to K - 1 do
C[i, j] := C[i - 1, j] + C[i - 1, j - 1];
var possible := 'a';
while K > 0 do
begin
if M <= C[N - 1, K - 1] then
begin
write(possible);
dec(K);
end
else
M := M - C[N - 1, K - 1];
dec(N);
inc(possible);
end;
end.