Для школьного праздника группа учащихся решила поставить танец, в котором иллюстрировалась бы работа алгоритма сортировки пузырьком. В этом танце учащиеся становятся в одну линию, после этого некоторые стоящие рядом танцоры могут меняться местами. Одновременные обмены запрещены, то есть пока одна пара танцоров меняется местами, другие остаются на своих местах. В конце танца все девочки должны стоять в ряду слева, а все мальчики — справа. По данному первоначальному расположению мальчиков и девочек в ряду определите, какое минимальное число обменов им необходимо совершить, чтобы встать нужным образом.
Например, пусть первоначальная расстановка танцоров такая (буква «Д» обозначает девочку, буква «М» обозначает мальчика):
МДДМД
Тогда им необходимо выполнить 4 обмена. Запишем расстановку после каждого обмена, выделив жирным шрифтом пару, которая поменялась местами.
ДМДМД
ДМДДМ
ДДМДМ
ДДДММ
В этой задаче вам необходимо определить минимальное число обменов для следующих пяти первоначальных расстановок:
МДММДМД
Во второй расстановке сначала стоит 7 мальчиков, потом 8 девочек.
В третьей расстановке стоит 10 мальчиков, 10 девочек, 10 мальчиков, 10 девочек, 10 мальчиков, 10 девочек. Всего 60 танцоров.
В четвёртой расстановке 1 мальчик, 1 девочка, 2 мальчика, 2 девочки, 3 мальчика, 3 девочки, 4 мальчика, 4 девочки, 5 мальчиков, 5 девочек, 6 мальчиков, 6 девочек. Всего 42 танцора.
В пятой расстановке мальчики и девочки чередуются, всего 80 танцоров.
ответом на эту задачу является пять целых чисел, записанных в пяти отдельных строках, по одному числу в строке. ответы на расстановки должны быть записаны в том же порядке, в котором они приведены в условии. Если вы не можете найти ответ для какой-то расстановки, напишите в качестве ответа любое число.
Для выполнения вычислений вы можете пользоваться компьютером (калькулятором, электронной таблицей, средой программирования).
var x : array[1..n] of real;
i : integer; min : real;
begin
Randomize;
writeln('Исходный массив:');
for i:=1 to n do
begin
x[i]:=20*random-10;
write(x[i]:6:2,' ');
end;
writeln;
min:=x[1];
for i:=2 to n do
if x[i] < min then min:=x[i];
writeln('min=',min:6:2);
for i:=1 to n do
if x[i]<0 then x[i]:=min;
writeln('Измененный массив:');
for i:=1 to n do write(x[i]:6:2,' ');
end.
Пример:
Исходный массив:
-7.84 -9.97 7.00 -8.26 -7.71 -3.88 7.59 -2.32
min= -9.97
Измененный массив:
-9.97 -9.97 7.00 -9.97 -9.97 -9.97 7.59 -9.97