Какое минимальное количество ходов должна сделать Катя, чтобы покрасить все точки в жёлтый цвет

@Martin Yacovlev · Регистрация: 19.06.2021

Студворк — интернет-сервис помощи студентам

На окружности отмечены n точек. Изначально все они белые. Катя играет в игру,
закрашивая точки жёлтым. За один ход Катя может либо закрасить жёлтым любую
одну точку, либо одновременно закрасить жёлтым все белые точки, у которых есть
жёлтые соседи на окружности.
Какое минимальное количество ходов потребуется Кате, чтобы сделать все точки
жёлтыми?

Формат входных данных
В первой строке записано целое число n — количество точек на окружности
(1 <= n <= 2 · 10^9)

Формат выходных данных
В первой строке выведите одно число: какое минимальное количество ходов должна
сделать Катя, чтобы покрасить все точки в жёлтый цвет.
Примеры
8 - Ответ: 4
11 - ответ: 5

@Vigilant Mole · 08.12.2022, 23:40

Martin Yacovlev, один из оптимальных способов - сначала закрасить каждую 3-ю точку, пока между последней и первой закрашенной не останется <3 точек, а потом одним действием закрасить остальные. Получается такое соответствие:

Code
1
2
точек 1  2  3  4  5  6  7  8  9 10 11 12
ходов 1  2  2  3  3  3  4  4  4  5  5  5

Python
1
2
n = int(input())
print((n + 5) // 3 if n > 1 else 1)

Новые блоги и статьи Все статьи Все блоги /
Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI
Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .

@Martin Yacovlev 0 / 0 / 0 Регистрация: 19.06.2021 Сообщений: 11

	Какое минимальное количество ходов должна сделать Катя, чтобы покрасить все точки в жёлтый цвет 08.12.2022, 11:27. Показов 2281. Ответов 1 Метки нет (Все метки) На окружности отмечены n точек. Изначально все они белые. Катя играет в игру, закрашивая точки жёлтым. За один ход Катя может либо закрасить жёлтым любую одну точку, либо одновременно закрасить жёлтым все белые точки, у которых есть жёлтые соседи на окружности. Какое минимальное количество ходов потребуется Кате, чтобы сделать все точки жёлтыми? Формат входных данных В первой строке записано целое число n — количество точек на окружности (1 <= n <= 2 · 10^9) Формат выходных данных В первой строке выведите одно число: какое минимальное количество ходов должна сделать Катя, чтобы покрасить все точки в жёлтый цвет. Примеры 8 - Ответ: 4 11 - ответ: 5 0