Question

ИНФОРМАТИКА (100 БАЛЛОВ) Для школьного праздника группа учащихся решила поставить танец, в котором иллюстрировалась бы работа алгоритма сортировки пузырьком. В этом танце учащиеся становятся в одну линию, после этого некоторые стоящие рядом танцоры могут меняться местами. Одновременные обмены запрещены, то есть пока одна пара танцоров меняется местами, другие остаются на своих местах. В конце танца все девочки должны стоять в ряду слева, а все мальчики — справа. По данному первоначальному расположению мальчиков и девочек в ряду определите, какое минимальное число обменов им необходимо совершить, чтобы встать нужным образом. Например, пусть первоначальная расстановка танцоров такая (буква «Д» обозначает девочку, буква «М» обозначает мальчика): МДДМД Тогда им необходимо выполнить 4 обмена. Запишем расстановку после каждого обмена, выделив жирным шрифтом пару, которая поменялась местами. ДМДМД ДМДДМ ДДМДМ ДДДММ В этой задаче вам необходимо определить минимальное число обменов для следующих пяти первоначальных расстановок: МДММДМД МММММММДДДДДДДД ММММММММММДДДДДДДДДДММММММММММДДДДДДДДДДММММММММММДДДДДДДДДД МДММДДМММДДДММММДДДДМММММДДДДДММММММДДДДДД МДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМД Во второй расстановке сначала стоит 7 мальчиков, потом 8 девочек. В третьей расстановке стоит 10 мальчиков, 10 девочек, 10 мальчиков, 10 девочек, 10 мальчиков, 10 девочек. Всего 60 танцоров. В четвёртой расстановке 1 мальчик, 1 девочка, 2 мальчика, 2 девочки, 3 мальчика, 3 девочки, 4 мальчика, 4 девочки, 5 мальчиков, 5 девочек, 6 мальчиков, 6 девочек. Всего 42 танцора. В пятой расстановке мальчики и девочки чередуются, всего 80 танцоров. Ответом на эту задачу является пять целых чисел, записанных в пяти отдельных строках, по одному числу в строке. Ответы на расстановки должны быть записаны в том же порядке, в котором они приведены в условии. Если вы не можете найти ответ для какой-то расстановки, напишите в качестве ответа любое число. Для выполнения вычислений вы можете пользоваться компьютером (калькулятором, электронной таблицей, средой программирования).

Answer 1

Ответ:

8

56

1000

720

1600

Объяснение:

Answer 2

Данная задача связана с симуляцией алгоритма сортировки пузырьком через танец учащихся. Основная идея состоит в том, чтобы понять, сколько обменов необходимо для того, чтобы девочки и мальчики выстроились в нужном порядке (девочки слева, мальчики справа).

Первоначальные расстановки представлены строками, где "М" обозначает мальчика, а "Д" - девочку. Нужно определить минимальное количество обменов для каждой расстановки. Вот решения для каждой из представленных расстановок:

1. МДММДМД - Для данной расстановки требуется выполнить 6 обменов: - ДМММДМД - ДММДММД - ДМДМММД - ДДММММД - ДДМММДМ - ДДДММММ

2. МММММММДДДДДДДД - Здесь не требуется никаких обменов, так как уже удовлетворяет условию задачи.

3. МММММММММММДДДДДДДДДДММММММММММДДДДДДДДДД - Снова не нужно никаких обменов, так как все уже в нужном порядке.

4. МДММДДМММДДДМММДДДДММММДДДДДММММММДДДДДД - Для этой расстановки необходимо выполнить 38 обменов.

5. МДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМДМД - В этом случае не требуется никаких обменов.

Таким образом, ответы для каждой из пяти представленных расстановок:

1. 6 2. 0 3. 0 4. 38 5. 0