Фокус с тенями

@Ksenija_22 · Регистрация: 29.05.2024

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

Привет, помогите пожалуйста оптимизировать задачу:
Фокус с тенями

Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт

Валера увлекается фокусами с тенями и сегодня придумал новый трюк. Он установил перед собой n фонарей, каждый из которых может светить вверх или вниз. Затем он повторяет один и тот же трюк. В начале он считает количество фонарей, которые светят вверх, пусть это число будет k. Если k = 0, то фокус заканчивается. В противном случае Валера переключает направление света k-го фонаря. Результатом фокуса является число повторений данного трюка.

Однако, поскольку Валера — фокусник, он удивлял вас своим мастерством, но вы решили удивить его и узнать результат фокуса до его завершения.

Формат входных данных
В первой строке вводится число n — количество фонарей (1 ≤ n ≤ 10^5).
Во второй строке вводится строка длины n, состоящая из "0" и "1" — положение фонарей. Символ "0" обозначает фонарь, светящий вниз, а "1" — фонарь, светящий вверх.

Формат выходных данных
Выведите количество повторений трюка или "-1", если фокусы будут повторяться бесконечно.

Примеры

стандартный ввод
10
1010110101

стандартный вывод
30

моё решение не оптимальное на больших тестах поэтому прошу помощи:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def shadow_trick(n, lanterns):
    visited_states = {}
    iterations = 0
    configuration = [int(lantern) for lantern in lanterns]
    
    while True:
        k = sum(configuration)
        
        if k == 0:
            return iterations
        
        state_key = tuple(configuration)
        if state_key in visited_states: 
            return -1
        
        visited_states[state_key] = iterations
        iterations += 1
        
        if k <= n:
            configuration[k - 1] = 1 - configuration[k - 1]
 
n = int(input())
lanterns = input()
print(shadow_trick(n, lanterns))

@contrlc · 06.09.2024, 14:51

Международная математическая олимпиада, задача C3.

Python
1
2
n, b = int(input()), list(map(int, input()))
print(2 * sum(i * bit for i, bit in enumerate(b, 1)) - sum(b)**2)

@Ksenija_22 · 06.09.2024, 15:00 **[ТС]**

Огромное спасибо!

@anton78spb · 06.09.2024, 15:13

contrlc, Судя по решению, случая когда алгоритм фокусника уходит в "вечный цикл" нет, т.е. вариант в возвратом -1 не предусмотрен?
Правильно понимаю, что задача всегда имеет решение?

@contrlc · 06.09.2024, 15:25

anton78spb, Да, доказательство тут https://www.imo-official.org/p... 2019SL.pdf

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Ksenija_22 0 / 0 / 0 Регистрация: 29.05.2024 Сообщений: 30
	06.09.2024, 15:00 [ТС]
	Огромное спасибо! 0

@anton78spb 1956 / 874 / 352 Регистрация: 05.09.2021 Сообщений: 1,387
	06.09.2024, 15:13
	contrlc, Судя по решению, случая когда алгоритм фокусника уходит в "вечный цикл" нет, т.е. вариант в возвратом -1 не предусмотрен? Правильно понимаю, что задача всегда имеет решение? 0

@contrlc 55 / 39 / 23 Регистрация: 07.05.2024 Сообщений: 58
	06.09.2024, 15:25
	anton78spb, Да, доказательство тут https://www.imo-official.org/p... 2019SL.pdf 1

Фокус с тенями

Решение