Для школьного праздника группа учащихся решила поставить танец, в котором иллюстрировалась бы работа алгоритма сортировки пузырьком. В этом танце учащиеся становятся в одну линию, после этого некоторые стоящие рядом танцоры могут меняться местами. Одновременные обмены запрещены, то есть пока одна пара танцоров меняется местами, другие остаются на своих местах. В конце танца все девочки должны стоять в ряду слева, а все мальчики — справа. По данному первоначальному расположению мальчиков и девочек в ряду определите, какое минимальное число обменов им необходимо совершить, чтобы встать нужным образом.
Например, пусть первоначальная расстановка танцоров такая (буква «Д» обозначает девочку, буква «М» обозначает мальчика):
МДДМД
Тогда им необходимо выполнить 4 обмена. Запишем расстановку после каждого обмена, выделив жирным шрифтом пару, которая поменялась местами.
ДМДМД
ДМДДМ
ДДМДМ
ДДДММ
В этой задаче вам необходимо определить минимальное число обменов для следующих пяти первоначальных расстановок:
МДММДМД
Во второй расстановке сначала стоит 7 мальчиков, потом 8 девочек.
В третьей расстановке стоит 10 мальчиков, 10 девочек, 10 мальчиков, 10 девочек, 10 мальчиков, 10 девочек. Всего 60 танцоров.
В четвёртой расстановке 1 мальчик, 1 девочка, 2 мальчика, 2 девочки, 3 мальчика, 3 девочки, 4 мальчика, 4 девочки, 5 мальчиков, 5 девочек, 6 мальчиков, 6 девочек. Всего 42 танцора.
В пятой расстановке мальчики и девочки чередуются, всего 80 танцоров.
ответом на эту задачу является пять целых чисел, записанных в пяти отдельных строках, по одному числу в строке. ответы на расстановки должны быть записаны в том же порядке, в котором они приведены в условии. Если вы не можете найти ответ для какой-то расстановки, напишите в качестве ответа любое число.
Объяснение:
В общем алгоритм такой.
Пусть мы имеем массив a[1..n, 1..n] из n*n элементов,
i - номер строки, j - номер столбца.
Спускаемся вниз по строкам до строки, номер которой отличается от того,
n - четное или нечетное.
В общем случае это номер i_ser, равный n делить на 2, и округленный до целого вниз.
Например, если n = 4, i_ser = 2, если n = 7, то i_ser = 3.
Для i от 1 до i_ser делать
начало
Для j от 1 до i делать
// здесь мы получаем нужные нам координаты i, j
конец
Если i_ser нечетно, то отдельно проходимся по строке с номером i_ser+1
Если i_ser нечетно то
начало
i_ser = i_ser + 1
Для j от 1 до i_ser делать
// здесь мы получаем нужные нам координаты i_ser, j
конец
i_ser = i_ser + 1
Для i от i_ser до n делать
начало
Для j от 1 до n - i + 1 делать
// здесь мы получаем нужные нам координаты i, j
конец