Сложная задача на перестановки

@Суренчик · Регистрация: 12.02.2017

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

Перестановкой размера n называется массив ⟨a1, a2, . . . , an⟩ различных чисел от 1 до n.
Каждое число в перестановке встречается ровно один раз.
Сеня называет красотой перестановки ⟨a1, a2, . . . , an⟩ число
(a1a2 + a2a3 + . . . + an−1an). Он хочет посчитать количество перестановок, красота
которых делится на k.
Даны числа n и k, найдите количество перестановок размера n, красота которых делится
на k.
Например, для n = 3 существует 6 перестановок. Рассмотрим все эти перестановки и
их красоту.
Перестановка Красота
⟨1, 2, 3⟩ 1 · 2 + 2 · 3 = 8
⟨1, 3, 2⟩ 1 · 3 + 3 · 2 = 9
⟨2, 1, 3⟩ 2 · 1 + 1 · 3 = 5
⟨2, 3, 1⟩ 2 · 3 + 3 · 1 = 9
⟨3, 1, 2⟩ 3 · 1 + 1 · 2 = 5
⟨3, 2, 1⟩ 3 · 2 + 2 · 1 = 8

Добавлено через 4 минуты
Перестановка Красота
⟨1, 2, 3⟩ 1 · 2 + 2 · 3 = 8
⟨1, 3, 2⟩ 1 · 3 + 3 · 2 = 9
⟨2, 1, 3⟩ 2 · 1 + 1 · 3 = 5
⟨2, 3, 1⟩ 2 · 3 + 3 · 1 = 9
⟨3, 1, 2⟩ 3 · 1 + 1 · 2 = 5
⟨3, 2, 1⟩ 3 · 2 + 2 · 1 = 8

@Sun Serega · 23.10.2018, 21:10

Pascal

function ПолучитьПерестановки(c: integer; prev: array of integer; i: integer): sequence of array of integer;
begin
  if i=0 then
    prev := new integer[c] else
  if i=c then
  begin
    yield prev;
    exit;
  end;
  for var n := 1 to c do
    if not prev.Contains(n) then
    begin
      var temp := Copy(prev);
      temp[i] := n;
      yield sequence ПолучитьПерестановки(c, temp, i+1);
    end;
end;
 
function ПолучитьПерестановки(c: integer) :=
ПолучитьПерестановки(c,nil,0);
 
begin
  var (c,k) := ReadlnInteger2;
  ПолучитьПерестановки(c)
  .Where(a-> ( a.Pairwise.Sum(t->t[0]*t[1]) mod k )=0 )
  .Count
  .Print;
end.

@Суренчик · 23.10.2018, 21:31 **[ТС]**

Серега, она не работает

@Sun Serega · 23.10.2018, 21:42

Как именно не работает? Скрин + текст ошибки.

@Суренчик · 23.10.2018, 21:49 **[ТС]**

Вот так

@Sun Serega · 23.10.2018, 21:53

А, это была #486, уже давно исправлено. Обновитесь.

@Суренчик · 23.10.2018, 22:15 **[ТС]**

не можешь ли ты объяснить,что и для чего в этой программе? просто я щё учусь,хочу понять способ решения

@Sun Serega · 23.10.2018, 22:23

Ок, какие части непонятны?

@Суренчик · 23.10.2018, 22:28 **[ТС]**

Ну, вообще, как бы, я не проходил ещё таких функций, так что было бы неплохо, если бы ты объяснил всё. Спасибо большое!!!

@Sun Serega · 23.10.2018, 22:37

Каких таких? yield - есть презентация на PascalABC.Net

Что ещё?

@eaa · 24.10.2018, 18:00

А задача точна на "brute force" ?
Какие ограничения на массив a?

@Sun Serega · 24.10.2018, 18:19

Единственное ограничение - при вычислении суммы может возникнуть переполнение. Но для этого надо такое большое n - что программа никогда не досчитает (очень много перестановок будет).

@Суренчик · 24.10.2018, 21:22 **[ТС]**

Серёжа, ты можешь перевести на простой АВС с АВСnet?

Добавлено через 11 минут
Хотя нет, не надо. Спасибо большое!!!!

@Суренчик 1 / 1 / 1 Регистрация: 12.02.2017 Сообщений: 28
	24.10.2018, 21:22 [ТС]	13
	Серёжа, ты можешь перевести на простой АВС с АВСnet? Добавлено через 11 минут Хотя нет, не надо. Спасибо большое!!!! 0

@Суренчик 1 / 1 / 1 Регистрация: 12.02.2017 Сообщений: 28
		1
	Сложная задача на перестановки 23.10.2018, 20:57. Показов 9993. Ответов 12 Метки олимпиадная задача pascal (Все метки) Перестановкой размера n называется массив ⟨a1, a2, . . . , an⟩ различных чисел от 1 до n. Каждое число в перестановке встречается ровно один раз. Сеня называет красотой перестановки ⟨a1, a2, . . . , an⟩ число (a1a2 + a2a3 + . . . + an−1an). Он хочет посчитать количество перестановок, красота которых делится на k. Даны числа n и k, найдите количество перестановок размера n, красота которых делится на k. Например, для n = 3 существует 6 перестановок. Рассмотрим все эти перестановки и их красоту. Перестановка Красота ⟨1, 2, 3⟩ 1 · 2 + 2 · 3 = 8 ⟨1, 3, 2⟩ 1 · 3 + 3 · 2 = 9 ⟨2, 1, 3⟩ 2 · 1 + 1 · 3 = 5 ⟨2, 3, 1⟩ 2 · 3 + 3 · 1 = 9 ⟨3, 1, 2⟩ 3 · 1 + 1 · 2 = 5 ⟨3, 2, 1⟩ 3 · 2 + 2 · 1 = 8 Добавлено через 4 минуты Перестановка Красота ⟨1, 2, 3⟩ 1 · 2 + 2 · 3 = 8 ⟨1, 3, 2⟩ 1 · 3 + 3 · 2 = 9 ⟨2, 1, 3⟩ 2 · 1 + 1 · 3 = 5 ⟨2, 3, 1⟩ 2 · 3 + 3 · 1 = 9 ⟨3, 1, 2⟩ 3 · 1 + 1 · 2 = 5 ⟨3, 2, 1⟩ 3 · 2 + 2 · 1 = 8 0

@Суренчик 1 / 1 / 1 Регистрация: 12.02.2017 Сообщений: 28
	23.10.2018, 21:31 [ТС]	3
	Серега, она не работает 0

@Sun Serega 2177 / 1306 / 497 Регистрация: 07.04.2017 Сообщений: 4,564
	23.10.2018, 21:42	4
	Как именно не работает? Скрин + текст ошибки. 0

@Суренчик 1 / 1 / 1 Регистрация: 12.02.2017 Сообщений: 28
	23.10.2018, 21:49 [ТС]	5
	Вот так Миниатюры 0

@Sun Serega 2177 / 1306 / 497 Регистрация: 07.04.2017 Сообщений: 4,564
	23.10.2018, 21:53	6
	А, это была #486, уже давно исправлено. Обновитесь. 0

@Суренчик 1 / 1 / 1 Регистрация: 12.02.2017 Сообщений: 28
	23.10.2018, 22:15 [ТС]	7
	не можешь ли ты объяснить,что и для чего в этой программе? просто я щё учусь,хочу понять способ решения 0

@Sun Serega 2177 / 1306 / 497 Регистрация: 07.04.2017 Сообщений: 4,564
	23.10.2018, 22:23	8
	Ок, какие части непонятны? 0

@Суренчик 1 / 1 / 1 Регистрация: 12.02.2017 Сообщений: 28
	23.10.2018, 22:28 [ТС]	9
	Ну, вообще, как бы, я не проходил ещё таких функций, так что было бы неплохо, если бы ты объяснил всё. Спасибо большое!!! 0

@Sun Serega 2177 / 1306 / 497 Регистрация: 07.04.2017 Сообщений: 4,564
	23.10.2018, 22:37	10
	Каких таких? yield - есть презентация на PascalABC.Net Что ещё? 0

@eaa Status 418 3873 / 2151 / 573 Регистрация: 26.11.2017 Сообщений: 5,021 Записей в блоге: 2
	24.10.2018, 18:00	11
	А задача точна на "brute force" ? Какие ограничения на массив a? 0

Опции темы

@Sun Serega 2177 / 1306 / 497 Регистрация: 07.04.2017 Сообщений: 4,564
	24.10.2018, 18:19	12
	Единственное ограничение - при вычислении суммы может возникнуть переполнение. Но для этого надо такое большое n - что программа никогда не досчитает (очень много перестановок будет). 0

Сложная задача на перестановки

Решение