Задача. Перестановки

@Dennis Ritchie · Регистрация: 27.07.2014

Студворк — интернет-сервис помощи студентам

Перестановки

Вам дана перестановка p чисел 1, 2, ..., n. Давайте обозначим через f(p) следующую сумму:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?f(p)=\sum_{i=1}^{n}\sum_{j=i}^{n}min({p}_{i},{p}_{i+1},...{p}_{j})$

Найдите лексикографически m-ю перестановку длины n, обладающую максимальным возможным значением f(p).

Входные данные
Единственная строка входных данных содержит два целых числа n и m (1 ≤ n ≤ 8, 1 ≤ m ≤ cnt_n), где cnt_n — количество перестановок длины n, обладающих максимальным возможным значением f(p).

Выходные данные
Выведите n чисел — искомую перестановку.

Примеры тестов

Входные данные	Выходные данные
2 2	2 1
3 2	1 3 2
3 4	3 2 1
4 8	4 3 2 1

Примечание
В первом примере из условия обе перестановки чисел {1, 2} приводят к максимальному возможному значению f(p), равному 4. Из них (2, 1) идет второй в лексикографическом порядке.

Не могу до конца понять смысл задачи. Что обозначено переменными p_i, p_i+1? И чего-то я не понимаю, как получают цифру 4 в первом примере. Как вообще считается значение f(p)?

@salam · 13.02.2015, 16:59

при таких ограничениях нужно просто тупо все перебрать и посчитать.

@Dennis Ritchie · 13.02.2015, 17:03 **[ТС]**

Сообщение от salam

при таких ограничениях нужно просто тупо все перебрать и посчитать.

Так объясните, пожалуйста, что считать? Объясните первый пример хотя бы. Откуда взялась эта цифра "4"?

@salam · 13.02.2015, 17:17

у вас формула записана, что считать.

@Dennis Ritchie · 13.02.2015, 17:20 **[ТС]**

Сообщение от salam

у вас формула записана, что считать.

p_i - это перестановка или одна цифра из перестановки?

@salam · 13.02.2015, 17:42

i-ое число

@Dennis Ritchie · 14.02.2015, 11:03 **[ТС]**

salam, но ведь такой цикл для первого примера печатает не перестановки:

C++
1
2
3
4
5
6
7
8
9
/* Dlang */
import std.stdio;
 
void main ()
{
    for (int i = 1; i <= 2;++i)
        for (int j = i; j <= 2; ++j)
            writeln(i, "\t", j);
}

А такую ерунду:

Output1 1
1 2
2 2

Под p в этой задаче понимают одномерный массив? А под p_i - элементы массива?

@Dimension · 14.02.2015, 11:44

Сообщение от Dennis Ritchie

обозначим через f(p) следующую сумму

написано же

@Dennis Ritchie · 14.02.2015, 11:56 **[ТС]**

Сообщение от Dimension

написано же

Я вижу, что написано. Запишите эту формулу на каком-нибудь языке программирования, чтобы я понял, что значит p_i.

@Dimension · 14.02.2015, 12:03

C++
1
2
3
f[0]=1;
for(int i=1;i<n;i++)
  f[i]=f[i-1]*2;

@Dennis Ritchie · 14.02.2015, 12:16 **[ТС]**

Dimension, теперь я вообще ничего не понимаю. Зачем вы написали цикл, который добавляет в массив степени двойки?

@iliya785 · 19.02.2015, 03:58

min(p[i],p[i+1],..,p[j]) - это минимум с iого по jый элемента заданной перестановки p. f(p) - сумма минимумов по всем подотрезкам(без учёта повторений) по заданной перестановке p.

P.S. задача вроде с cf :-)

@Dennis Ritchie · 19.02.2015, 17:25 **[ТС]**

Сообщение от iliya785

по всем подотрезкам(без учёта повторений)

Я раньше даже и не думал про подотрезки. Т. е. для первого примера будет так?
min(1, 1) + min(1, 2) + min(2, 2) = 4
min(2, 2) + min(2, 1) + min(1, 1) = 4
Или я опять переборщил?

@iliya785 · 19.02.2015, 17:35

f([1,3,2]) = 1 + min(1,3) + min(1,3,2) + 3 + min(3,2) + 2

Добавлено через 1 минуту
[1,3,2] - это p

@Dennis Ritchie · 19.02.2015, 17:58 **[ТС]**

iliya785, спасибо. А почему в третьем примере перестановка 3 2 1 является лексикографически четвёртой?

@iliya785 · 19.02.2015, 18:51

f(p) для всех p в лексикографическом порядке:
10
10
9
10
9
10
так что всё правильно

Добавлено через 23 минуты
если вопросы остались - пиши, всё работает, на cf зашло

@Dennis Ritchie · 19.02.2015, 20:49 **[ТС]**

Сообщение от iliya785

если вопросы остались - пиши

Пока что вопросов больше нет.

Благодаря этому:

Сообщение от iliya785

10
10
9
10
9
10

Я понял всё, что до этого не понимал.
Вопросы есть по другой задаче:
Как разложить число на произведение факториалов?

Добавлено через 1 час 33 минуты

Сообщение от iliya785

на cf зашло

Какое-то длинное у тебя решение. Так лучше:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import std.stdio, std.string, std.container, std.conv, std.numeric, std.range;
import std.array, std.bigint, std.algorithm, std.math, std.typecons, std.random;
 
void main() {
 
    byte n;
    long k;
 
    readf(" %s %s", &n, &k);
    --k;
 
    k <<= 1;
    int[] a, b;
 
    foreach_reverse (i; 0 .. n)
        if ((k >> i) & 1L)
            b ~= n - i;
        else
            a ~= n - i;
 
    writefln("%(%s %)", a ~ b.reverse);
}

@Dennis Ritchie · 20.02.2015, 21:44 **[ТС]**

iliya785, а перестановки будут вести себя одинаково независимо от количества цифр?
Я заметил, что первые две перестановки обладают максимальным значением f(p), а потом просто чередуются через один. Например, для четырёх цифр 1234:
20
20
19
20
19
20
...
Если это выполняется для всех перестановок, то искать каждую перестановку, собственно, и не нужно.

@iliya785 · 20.02.2015, 22:20

если ты по поводу полного решения, то я и не думал(вопрос как раз был пояснить условие), заслал для проверки, значит подумаю, есди придумаю - напишу

@Dennis Ritchie · 20.02.2015, 22:46 **[ТС]**

Сообщение от iliya785

вопрос как раз был пояснить условие

Условие теперь понятно. Лучший ответ выбран. Теперь хочу обсудить полное решение.

Сообщение от iliya785

если ты по поводу полного решения

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

Хотелось бы понять: в чём смысл более сложного решения.

Добавлено через 14 минут
Похоже, что моё предположение неверное. Например, для перестановки 12345 моя "теорема" не выполнятся (если я правильно посчитал):
35
35
34
35
34
35
33
33
32
35
34
35
...

Новые блоги и статьи Все статьи Все блоги /
1С: Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .	Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	1С: Программный отбор элементов справочника по значению перечисления Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит предопределенное значение перечислений. Процедура. . .
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	13.02.2015, 16:59
	при таких ограничениях нужно просто тупо все перебрать и посчитать. 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	13.02.2015, 17:17
	у вас формула записана, что считать. 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	13.02.2015, 17:42
	i-ое число 0

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	14.02.2015, 12:16 [ТС]
	Dimension, теперь я вообще ничего не понимаю. Зачем вы написали цикл, который добавляет в массив степени двойки? 0

@iliya785 24 / 24 / 12 Регистрация: 04.06.2014 Сообщений: 80
	19.02.2015, 03:58
	Сообщение было отмечено Dennis Ritchie как решение Решение min(p[i],p[i+1],..,p[j]) - это минимум с iого по jый элемента заданной перестановки p. f(p) - сумма минимумов по всем подотрезкам(без учёта повторений) по заданной перестановке p. P.S. задача вроде с cf :-) 1

@iliya785 24 / 24 / 12 Регистрация: 04.06.2014 Сообщений: 80
	19.02.2015, 17:35
	f([1,3,2]) = 1 + min(1,3) + min(1,3,2) + 3 + min(3,2) + 2 Добавлено через 1 минуту [1,3,2] - это p 1

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	19.02.2015, 17:58 [ТС]
	iliya785, спасибо. А почему в третьем примере перестановка 3 2 1 является лексикографически четвёртой? 0

@iliya785 24 / 24 / 12 Регистрация: 04.06.2014 Сообщений: 80
	19.02.2015, 18:51
	f(p) для всех p в лексикографическом порядке: 10 10 9 10 9 10 так что всё правильно Добавлено через 23 минуты если вопросы остались - пиши, всё работает, на cf зашло 1

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	20.02.2015, 21:44 [ТС]
	iliya785, а перестановки будут вести себя одинаково независимо от количества цифр? Я заметил, что первые две перестановки обладают максимальным значением f(p), а потом просто чередуются через один. Например, для четырёх цифр 1234: 20 20 19 20 19 20 ... Если это выполняется для всех перестановок, то искать каждую перестановку, собственно, и не нужно. 0

@iliya785 24 / 24 / 12 Регистрация: 04.06.2014 Сообщений: 80
	20.02.2015, 22:20
	если ты по поводу полного решения, то я и не думал(вопрос как раз был пояснить условие), заслал для проверки, значит подумаю, есди придумаю - напишу 0

Задача. Перестановки

Решение