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

152

224

Посмотреть ответы 3

Ответы на вопрос:

Cektumcempra

Информатика

4,8(69 оценок)

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

Викка23

Информатика

4,5(46 оценок)

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.

ира1031

Информатика

4,4(64 оценок)

218.112

Объяснение:

213×1024=218.112

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

Реши свою проблему, спроси otvet5GPT

Быстро
Мгновенный ответ на твой вопрос
Точно
Бот обладает знаниями во всех сферах
Бесплатно
Задай вопрос и получи ответ бесплатно

Задай свой вопрос

Популярно: Информатика

Есть вопросы?

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.