Delivery Truck Emoji

Олимпиадные сообщества Бейонда объединяются в едином форуме Спроси! (ask.bc-pf.org)

Перейти к содержимому
  • Объявления

    • arman

      Если вы скачали .djvu файл   04.07.2020

      Не забудьте скачать специальную программу для этих файлов.  Для Windows и macOS: https://windjview.sourceforge.io/ru Программы для чтения djvu файлов для мобильных устройств можно найти в appstore и play market соответствующим поиском. Также вы можете перевести формат djvu в pdf через онлайн конверторы: https://djvu2pdf.com/  
    • arman

      Контесты Symmetrix   12.11.2020

      Контесты пока отложены на неопределенный срок
  • 0
Amir

Область 2011

Вопрос

Здравствуйте, можете помочь с решением следующей задачей:

У кассирши в одной пачке 200 денежных купюр. Она должна все купюры в пачке перевернуть лицевой стороной вверх; причем порядок купюр в пачке не имеет значения. На каждом шагу она выбирает некоторое количество купюр, лежащих в пачке подряд, и переворачивает всю выбранную часть пачки. Найдите наименьшее возможное число шагов, которого достаточно при любом изначальном положении купюр, чтобы перевернуть все имеющиеся в пачке купюры лицевой стороной вверх.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

1 ответ на этот вопрос

Рекомендованные сообщения

  • 1

@Amir Обозначим купюру лежащую лицом вверх как 1, лицом вниз как 0. Тогда пачка будет выглядеть как комбинация нулей и единиц. Например, \(11111...1\) -- это пачка в которой все купюры лежат лицом вверх, \(1000...0\) -- пачка в которой только верхняя лежит лицом вверх.

Оценка: Назовем блоком комбинацию в пачке, состоящую из последовательных единиц и ограниченную нулями. Например, в пачке \(110010011\) три блока. Ну и назовем сложностью пачки количество блоков которые в ней содержатся. Что тогда получается, кассирша имеет пачку сложностью \(n\), и она стремится привести эту пачку в вид \(11111...1\), т. е. уменьшить сложность до единицы. Заметим, что как бы ни старалась кассирша, за одно переворачивание она может уменьшить сложность пачки максимум на 1 (почему?). Так как наибольшая возможная сложность для пачки это 100 (когда пачка выглядит как \(1010101...0\)), то, чтобы привести эту пачку в правильный вид, ей нужно сделать как минимум 99 переворачиваний.

А почему 99 переворачиваний хватает при любом изначальном положении купюр попробуй доказать сам.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Пожалуйста, войдите для комментирования

Вы сможете оставить комментарий после входа



Войти сейчас

×