Минимальное количество перемещений

@OlgaBoy · Регистрация: 19.11.2015

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

За один раз Вася может поменять местами два шампура. Помогите Васе подсчитать наименьшее количество перемещений шампуров.

Формат входных данных:

В первой строке задано одно натуральное число N (1 ≤ N ≤ 105). Во второй строке через пробел записаны N различных чисел — номера позиций, куда нужно переместить соответствующие шампура. Все номера являются натуральными числами, не превосходящими N.

Формат выходных данных:

Выведите минимальное количество перемещений.

Пример

4
1 4 3 2 => 1

5
4 2 1 3 5 => 2

@JuriiMW · 23.11.2015, 07:38

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
type
  aType = array [1..105] of Integer;
  
var
  v : array [1..10000] of record
    p, m1, m2 : Integer;
  end;
  n, count : Integer;
  a, r : aType;
 
procedure m(p : Integer);
begin
  if p = 0 then
    for var i := 1 to n do
      a[i] := i
  else
    begin
      count += 1;
      m(v[p].p);
      Swap(a[v[p].m1], a[v[p].m2]);
    end;
end;
 
function compare(a, r : aType);
begin
  Result := False;
  for var i := 1 to n do
    if a[i] <> r[i] then
      Exit;
  Result := True;
end;
 
begin
  reset(input, 'input.txt');
  n := readlninteger();
  for var i := 1 to n do
    r[i] := readinteger();
  
  var p := -1;
  var c := 0;
  repeat
    count := 0;
    p += 1;
    m(p);
    for var m1 := 1 to n-1 do
      for var m2 := m1+1 to n do
        begin
          c += 1;
          v[c].p := p;
          v[c].m1 := m1;
          v[c].m2 := m2;
        end;
  until compare(a, r);
  
  rewrite(output, 'output.txt');
  writeln(count);
end.

Может быть для больших n потребуется увеличить размер массива v на пару порядков…

Новые блоги и статьи Все статьи Все блоги /
И решил я переделать этот ноут в машину для распределенных вычислений Programma_Boinc 09.11.2025 И решил я переделать этот ноут в машину для распределенных вычислений Всем привет. А вот мой компьютер, переделанный из ноутбука. Был у меня ноут асус 2011 года. Со временем корпус превратился. . .	Мысли в слух kumehtar 07.11.2025 Заметил среди людей, что по-настоящему верная дружба бывает между теми, с кем нечего делить.	Новая зверюга volvo 07.11.2025 Подарок на Хеллоуин, и теперь у нас кроме Tuxedo Cat есть еще и щенок далматинца: Хочу еще Симбу взять, очень нравится. . .	Инференс ML моделей в Java: TensorFlow, DL4J и DJL Javaican 05.11.2025 Python захватил мир машинного обучения - это факт. Но когда дело доходит до продакшена, ситуация не так однозначна. Помню проект в крупном банке три года назад: команда data science натренировала. . .	Mapped types (отображённые типы) в TypeScript Reangularity 03.11.2025 Mapped types работают как конвейер - берут существующую структуру и производят новую по заданным правилам. Меняют модификаторы свойств, трансформируют значения, фильтруют ключи. Один раз описал. . .
Адаптивная случайность в Unity: динамические вероятности для улучшения игрового дизайна GameUnited 02.11.2025 Мой знакомый геймдизайнер потерял двадцать процентов активной аудитории за неделю. А виновником оказался обычный генератор псевдослучайных чисел. Казалось бы - добавил в карточную игру случайное. . .	Протоколы в Python py-thonny 31.10.2025 Традиционная утиная типизация работает просто: попробовал вызвать метод, получилось - отлично, не получилось - упал с ошибкой в рантайме. Протоколы добавляют сюда проверку на этапе статического. . .	C++26: Read-copy-update (RCU) bytestream 30.10.2025 Прошло почти двадцать лет с тех пор, как производители процессоров отказались от гонки мегагерц и перешли на многоядерность. И знаете что? Мы до сих пор спотыкаемся о те же грабли. Каждый раз, когда. . .	Изображения webp на старых x32 ОС Windows XP и Windows 7 Argus19 30.10.2025 Изображения webp на старых x32 ОС Windows XP и Windows 7 Чтобы решить задачу, использовал интернет: поисковики Google и Yandex, а также подсказки Deep Seek. Как оказалось, чтобы создать. . .	Passkey в ASP.NET Core identity stackOverflow 29.10.2025 Пароли мертвы. Нет, серьезно - я повторяю это уже лет пять, но теперь впервые за это время чувствую, что это не просто красивые слова. В . NET 10 команда Microsoft внедрила поддержку Passkey прямо в. . .

@OlgaBoy 0 / 0 / 0 Регистрация: 19.11.2015 Сообщений: 5

	Минимальное количество перемещений 20.11.2015, 12:19. Показов 1469. Ответов 1 Метки нет (Все метки) За один раз Вася может поменять местами два шампура. Помогите Васе подсчитать наименьшее количество перемещений шампуров. Формат входных данных: В первой строке задано одно натуральное число N (1 ≤ N ≤ 105). Во второй строке через пробел записаны N различных чисел — номера позиций, куда нужно переместить соответствующие шампура. Все номера являются натуральными числами, не превосходящими N. Формат выходных данных: Выведите минимальное количество перемещений. Пример 4 1 4 3 2 => 1 5 4 2 1 3 5 => 2 0

Опции темы

Минимальное количество перемещений

Решение