Решить олимпиадную (9кл). олимиада уже прошла, но хочется знать решение. программа на паскале. заранее . петя выписал все сочетания из n первых латинских букв по k букв. в каждом сочетании он выписывал буквы в лексикографическом (словарном) порядке. сочетания он выписывал в лексикографическом порядке по одному в строке. надо узнать какое слово записано в m-ой строке. входные данные: целые числа n, k, m (1< =n< =26, 1< =k< =n, а м не превосходит количества всех выписанных сочетаний). выходные данные: вывести м-ое выписанное сочетание. пример: вх: 4 2 3 вых: ad пояснение: все сочетания в порядке их записи: ab ac ad bc bd cd (третьим по счету сочетанием является ad).

Ябуду думать, что сочетание - набор нулей и единиц, в котором на 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 : = ();   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.

Var n,k,i,d,m: longint;       b: array[1..26] of boolean; procedure writesymbol(j: longint); begin write(chr(ord('a')+j-1)); end; procedure print(x: longint); var z,h,p: longint; begin z : = 0; p : = 0; while true do begin p : = p + 1; if b[p] = false then z : = z + 1; if z = x then break; end; x : = p; b[x] : = true; writesymbol(x); end; function fa_l(a,b: longint): longint; var s,h: longint; begin s : = 1; for h : = a to b do s : = s * h; fa_l : = s; end; begin read(n,k,m); d : = fa_l(n-k+1,n-1); for i : = k downto 1 do begin print((m - 1) div d + 1); if m mod d = 0 then m : = d else m : = m mod d; d : = d div (n - (k - i + 1)); end; end.

218.112

Объяснение:

213×1024=218.112

Т.к. 1 кБайт=1024 байт