Танец Для школьного праздника группа учащихся решила поставить танец, в котором иллюстрировалась бы работа алгоритма сортировки пузырьком. В этом танце учащиеся становятся в одну линию, после этого некоторые стоящие рядом танцоры могут меняться местами. Одновременные обмены запрещены, то есть пока одна пара танцоров меняется местами, другие остаются на своих местах.
В конце танца все девочки должны стоять в ряду слева, а все мальчики — справа. По данному первоначальному расположению мальчиков и девочек в ряду определите, какое минимальное число обменов им необходимо совершить, чтобы встать нужным образом.
Например, пусть первоначальная расстановка танцоров такая (буква «Д» обозначает девочку, буква «М» обозначает мальчика):
МДДМД
Тогда им необходимо выполнить 4 обмена. Запишем расстановку после каждого обмена, выделив жирным шрифтом пару, которая поменялась местами.
ДМДМД
ДМДДМ
ДДМДМ
ДДДММ
В этой задаче вам необходимо определить минимальное число обменов для следующих пяти первоначальных расстановок:
МДММДМД
Во второй расстановке сначала стоит 7 мальчиков, потом 8 девочек.
В третьей расстановке стоит 10 мальчиков, 10 девочек, 10 мальчиков, 10 девочек, 10 мальчиков, 10 девочек. Всего 60 танцоров.
В четвёртой расстановке 1 мальчик, 1 девочка, 2 мальчика, 2 девочки, 3 мальчика, 3 девочки, 4 мальчика, 4 девочки, 5 мальчиков, 5 девочек, 6 мальчиков, 6 девочек. Всего 42 танцора.
В пятой расстановке мальчики и девочки чередуются, всего 80 танцоров.
ответом на эту задачу является пять целых чисел, записанных в пяти отдельных строках, по одному числу в строке. ответы на расстановки должны быть записаны в том же порядке, в котором они приведены в условии. Если вы не можете найти ответ для какой-то расстановки, напишите в качестве ответа любое число.
Для выполнения вычислений вы можете пользоваться компьютером (калькулятором, электронной таблицей, средой программирования).
nn=100;
type
Abit=record
fio:string;
ball:array[1..3] of byte;
from:string;
midb:real
end;
var
t:Abit;
mAb:array[1..nn] of Abit;
i,j,n,m:integer;
midinst:real;
begin
{ ввод исходных данных }
Write('Количество абитуриентов (до 100): '); Readln(n);
Write('Средний по институту: '); Readln(midinst);
m:=0;
for i:=1 to n do
begin
Writeln('Абитуриент № ',i);
With mAb[i] do begin
Write('Фамилия, И.О.: '); Readln(fio);
Write(' по трем предметам через пробел: ');
Readln(ball[1],ball[2],ball[3]);
midb:=(ball[1]+ball[2]+ball[3])/3;
Write('Место жительства: '); Readln(from)
end;
if mAb[i].midb>midinst then m:=m+1;
end;
{ простейшая обменная сортировка по убыванию }
for i:=1 to n-1 do
for j:=i+1 to n do
if mAb[i].midb<mAb[j].midb then begin
t:=mAb[i];
mAb[i]:=mAb[j];
mAb[j]:=t
end;
{ вывод }
Writeln;
Writeln('Количество поступающих со средним выше среднеинститутского: ',m);
for i:=1 to n do
with mAb[i] do
Writeln(fio,' ',ball[1]:2,ball[2]:2,ball[3]:2,' ',from)
end.
Тестовое решение:
Количество абитуриентов (до 100): 4
Средний по институту: 5.94
Абитуриент № 1
Фамилия, И.О.: Иванов А.Г.
по трем предметам через пробел: 9 7 5
Место жительства: Вологда
Абитуриент № 2
Фамилия, И.О.: Петров Л.Л.
по трем предметам через пробел: 9 9 9
Место жительства: Грязевец
Абитуриент № 3
Фамилия, И.О.: Раковский Д.Г.
по трем предметам через пробел: 4 4 5
Место жительства: Сокол
Абитуриент № 4
Фамилия, И.О.: Акимова Я.С.
по трем предметам через пробел: 9 5 4
Место жительства: Харовск
Количество поступающих со средним выше среднеинститутского: 3
Петров Л.Л. 9 9 9 Грязевец
Иванов А.Г. 9 7 5 Вологда
Акимова Я.С. 9 5 4 Харовск
Раковский Д.Г. 4 4 5 Сокол
Можно развернуть куб, центром "развертки" делаем грань где сидит муха, если муха и варенье на одной грани достачно просто, путь прямая, Зелным цветом залита одна и таже грань отмечено 4 возможных пути один из которых, в зависимости от размеров куба и координат мухи и варенья будет кратчайшим. Кратчайший путь для ситуации на рисунке - зеленый пунктир.
Да если достроить до треугольника (черный пунктир катеты d и f), искомый путь гипотенуза. Её длина
Значит вся "хитрость" в том, чтобы правильно "собрать" длины катетов.
Если успею обобщить и облечь все в формулы (код) (логические выражения), добавлю. И уточню рисунки. Если нет, может кто-то догадается. Или в крайнем случае отошлют на доработку мне или Allangarsk.
Возможно, что в случае расположения на противоположных гранях, придется просчитывать все пути кандидаты и выбирать из них наименьший.
В случае на расположения на одной грани (X1=X2)OR(Y1=Y2)OR(Z1=Z2) кратчайший путь очевиден. Если, допустим Z1=Z2, то
d=(X1-X2), f=(Y1-Y2).