Задача по олимпиаде?

Question

[KiberKachok]

Мальчик Петя решил приготовить маме подарок на день рождения — праздничный завтрак. Он решил сделать вкусный чай и испечь блинчики. К сожалению, не отличаясь выдающимися кулинарными способностями, Петя не смог уследить за блинчиками. Каждый из них получился подгорелым с одной стороны и недожаренным с другой. В результате у Пети получилось N черно-белых блинчиков. Все блинчики он выложил на большую тарелку друг на друга. Теперь Петя хочет перевернуть их так, чтобы все они лежали светлой стороной вверх — Петя думает, что так они маме понравятся больше. Для переворачивания блинчиков у него есть лопаточка, которой он может взять несколько верхних блинчиков (от одного до всей стопки) и перевернуть их все вместе (таким образом, что верхний блин окажется на месте нижнего из взятых блинов).

За какое минимальное число таких действий Петя может перевернуть все блины светлой стороной вверх?

Comments

[Сергей delphinpro]

Задача по олимпиаде?

Да, это задача по олимпиаде.
Накуя она здесь?

[Сергей delphinpro]

0

[Одиночка Айс]

По теории вероятности мама Пети пришла домой раньше и дала ему люлей за испорченную кухню и невыученные уроки. Это жизнь, а не эти ваши вышматы...

[KiberKachok]

Сергей delphinpro, Хочу разбор посмотреть, в инете нет

[Сергей delphinpro]

KiberKachok, какой разбор? Начальное положение блинчиков не уточняется. Значит из всех возможных вариантов блинчики уже могут лежать светлой стороной вверх и перекладывать их не требуется.

[Сергей delphinpro]

Вот максимальное кол-во действий было бы интереснее вычислить.

[Сергей П]

Сергей delphinpro, В таких случаях обычно подразумевается за какое минимальное количество действий гарантированно удастся перевернуть в худшем случае.
Ну, то есть, как бы блинчики ни лежали, есть некое число действий за которое гарантировано можно уложить блины как надо.
И вот это минимальное число как раз и нужно искать.

Answer 1

[jcmvbkbc]

Запишем последовательность блинов цифрами 0 (светлой стороной вверх) и 1 (тёмной стороной вверх). Назовём инверсией переход с 1 на 0 или с 0 на 1. Один переворот стопки может добавить или убавить максимум одну инверсию на границе между переворачиваемой и не переворачиваемой частями (все инверсии внутри переворачиваемой части сохраняются, только меняют знак). Следовательно минимальное число переворотов для устранения всех инверсий равно числу инверсий в исходной стопке блинов. Если первый блин лежит тёмной стороной вверх для решения задачи потребуется ещё один переворот всей стопки.

Answer 2

[Mercury13]

ОПРЕДЕЛЕНИЕ. Беспорядок — а) чёрный блин внизу; б) белый блин на чёрном, чёрный на белом.

ТЕОРЕМА. Переворот исправляет не более одного беспорядка.
ДОКАЗАТЕЛЬСТВО. Ни в переворачиваемой стопке, ни в оставшейся как был беспорядок, так и остаётся. У нас есть шанс исправить один беспорядок — тот, в который мы залезли лопатой.

СЛЕДСТВИЕ. Оценка снизу — количество беспорядков.

ТЕОРЕМА. Эта граница достижима.
БАЗА ИНДУКЦИИ. У нас 0 беспорядков. Все блины белые — реально нужно 0 ходов.
ШАГ ИНДУКЦИИ. Доказано, что граница достижима для 0…N−1 беспорядков. Пусть теперь беспорядков N.
Если количество беспорядков нечётно, вверху будет чёрный блин. Перевернём всю стопку, кроме нижних белых блинов. Теряем одним ходом один беспорядок, а для N−1 граница достижима.
Если количество беспорядков чётно, вверху белый блин. Поскольку беспорядков не 0, белые блины лежат на чёрных. Перевернём белую группу (теряем один беспорядок) и получаем вверху чёрный блин. Теряем одним ходом один беспорядок, а для N−1 граница достижима.

АЛГОРИТМ. Подсчитать количество беспорядков в стопке, вывести его. O(N).

Answer 3

[res2001]

Очевидно, что максимальное число переворотов будет, если блины лежат друг к другу одинаковыми сторонами (белая к белой, черная к черной). В этом случае для упорядочивания нужно сделать N-1 переворот.
Количество переворотов увеличивается на 1 (потому что в конце оказывается, что вся стопка лежит черной стороной вверх), если:
1. N не четное и в начале первый блин черный
2. N четное и первый блин белый
Итого, максимальное число переворотов: N