Задача 2: Танец Для школьного праздника группа учащихся решила поставить танец, в котором иллюстрировалась бы работа алгоритма сортировки пузырьком. В этом танце учащиеся становятся в одну линию, после этого некоторые стоящие рядом танцоры могут меняться местами. Одновременные обмены запрещены, то есть пока одна пара танцоров меняется местами, другие остаются на своих местах.
В конце танца все девочки должны стоять в ряду слева, а все мальчики — справа. По данному первоначальному расположению мальчиков и девочек в ряду определите, какое минимальное число обменов им необходимо совершить, чтобы встать нужным образом.
Например, пусть первоначальная расстановка танцоров такая (буква «Д» обозначает девочку, буква «М» обозначает мальчика):
МДДМД
Тогда им необходимо выполнить 4 обмена. Запишем расстановку после каждого обмена, выделив жирным шрифтом пару, которая поменялась местами.
ДМДМД
ДМДДМ
ДДМДМ
ДДДММ
В этой задаче вам необходимо определить минимальное число обменов для следующих пяти первоначальных расстановок:
МДММДМД
Во второй расстановке сначала стоит 7 мальчиков, потом 8 девочек.
В третьей расстановке стоит 10 мальчиков, 10 девочек, 10 мальчиков, 10 девочек, 10 мальчиков, 10 девочек. Всего 60 танцоров.
В четвёртой расстановке 1 мальчик, 1 девочка, 2 мальчика, 2 девочки, 3 мальчика, 3 девочки, 4 мальчика, 4 девочки, 5 мальчиков, 5 девочек, 6 мальчиков, 6 девочек. Всего 42 танцора.
В пятой расстановке мальчики и девочки чередуются, всего 80 танцоров.
ответом на эту задачу является пять целых чисел, записанных в пяти отдельных строках, по одному числу в строке. ответы на расстановки должны быть записаны в том же порядке, в котором они приведены в условии. Если вы не можете найти ответ для какой-то расстановки, напишите в качестве ответа любое число.
Для выполнения вычислений вы можете пользоваться компьютером (калькулятором, электронной таблицей, средой программирования).
// PascalABC.NET 3.6.3
uses School;
function Divizors(n: integer): List<integer>;
begin
var L := new List<integer>;
L.Add(1);
L.Add(n);
if n > 3 then
begin
var k := 2;
while (k * k <= n) and (k < 46341) do
begin
if n mod k = 0 then
begin
var t := n div k;
L.Add(k);
if k < t then L.Add(t)
else break
end;
Inc(k)
end;
L.Sort;
end;
Result := L
end;
begin
// 1
if ReadInteger.IsPrime then Println('YES')
else Println('NO');
// 2
ReadInteger.Factorize.First.Println;
// 3
var a := Divizors(ReadInteger);
Print(a.Count, a.Sum)
end.
// PascalABC.NET 3.3, сборка 1634 от 14.02.2018
// Внимание! Если программа не работает, обновите версию!
begin
var a:=ArrRandom(ReadInteger('n='),20,80); a.Println;
var k:=a.Where(t->t mod 10=6).Count;
if k>0 then Writeln(k)
else Writeln('Нет')
end.
Пример
n= 15
47 53 73 26 75 64 70 32 27 80 29 53 20 62 66
2
2. Достаточно много раз нужно запускать задачу, чтобы суметь получить случайную последовательность с парой одинаковых соседних элементов...
// PascalABC.NET 3.3, сборка 1634 от 14.02.2018
// Внимание! Если программа не работает, обновите версию!
begin
var a:=ArrRandom(10,0,100); a.Println;
var k:=a.Pairwise.Where(t->t[0]=t[1]).Count;
if k>0 then Writeln(k)
else Writeln('Нет')
end.
Пример
60 41 87 87 95 75 72 32 8 52
1