В сервисе починки роботов очень важно соблюдать порядок

@Клин · Регистрация: 26.10.2022

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

В сервисе починки роботов очень важно соблюдать порядок. Главный механик любит, чтобы все роботы стояли друг за другом — сначала только сломанные (если они есть), а потом исправные (если они есть).
По ночам роботы всё время гуляют по ангару, и к утру порядок, установленный главным механиком, нарушается. Механик решил наказывать роботов, которые нарушают порядок, и удалять из очереди. Но роботы взбунтовались и требуют равноправия — если уж удалять из очереди, то равное количество исправных и сломанных роботов.
Сломанные роботы обозначаются буквой B (broken), исправные — буквой W (working).
Есть строка из букв B и W. Надо удалить наименьшее и равное количество сломанных и исправных роботов так, чтобы в очереди сначала стояли только сломанные, а потом только исправные. Может оказаться, что одних или других нет. Общее количество роботов в очереди не превышает 10 000.
Выведи количество удалённых роботов и очередь, которая получилась после удаления нарушивших правило роботов.
Если в очереди никого не осталось, выведи «НИКОГО НЕ ОСТАЛОСЬ».
Ввод
BWBWWBW
BWWWWW
BBBBB
WWBB
Вывод
2
BBWWW
0
BWWWW
0
BBBBB
4
НИКОГО НЕ ОСТАЛОСЬ

@eaa · 07.03.2023, 06:05

Aleksander964, похоже на правду, только решение за O(n).

@Alexarh · 07.03.2023, 12:40

Даже и не подумал, что вот такой вариант будет настолько быстрее, чем со списком для удаления из другой темы.
Но все равно, который выше с count быстрее.

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
25
26
def foo(s):
    i = 0
    j = len(s) - 1
    a1 = a2 = ''
    count = 0
    while i <= j:
        while i <= j and s[i] != 'W':
            a1 += s[i]
            i += 1
        while i <= j and s[j] != 'B':
            a2 = s[j] + a2
            j -= 1
        if i < j:
            count += 2
        i += 1
        j -= 1
 
    return count, a1 + a2 or 'НИКОГО НЕ ОСТАЛОСЬ'
 
 
s = ''.join(choice('WB') for _ in range(100000))
s1 = time()
r1 = foo(s)
s2 = time()
print(r1)
print(s2 - s1)

Добавлено через 15 минут

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def foo(s):
    i = 0
    j = len(s) - 1
    count_w = count_b = 0
    while i <= j:
        while i <= j and s[i] != 'W':
            count_b += 1
            i += 1
        while i <= j and s[j] != 'B':
            count_w += 1
            j -= 1
        i += 1
        j -= 1
    a = 'B' * count_b + 'W' * count_w
    return len(s) - len(a), a or 'НИКОГО НЕ ОСТАЛОСЬ'

@eaa · 07.03.2023, 14:37

Alexarh, вроде стандартная задача на "два указателя"

@Aleksander964 · 09.03.2023, 18:17

да, первое решение быстрее моего, но я зато свое решение сам придумал за пол часа, оптимизировал, и оно вроде работает даже быстро, я проводил тесты по времени решения с большими строками, мой код работает в 4.5 раза дольше максимум
например строка 'B'+'W'*10000+'B'*9999+'W'
мой код выполнился за 20 секунд
а первый (не мой) за 5

Добавлено через 8 минут
eaa, и решение у меня 158/158 баллов за олимпиаду эту)

@eaa · 09.03.2023, 18:28

Aleksander964, если сам решал, то молодец!

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@Клин 0 / 0 / 0 Регистрация: 26.10.2022 Сообщений: 32

	В сервисе починки роботов очень важно соблюдать порядок 10.02.2023, 12:28. Показов 41197. Ответов 24 Метки информатика (Все метки) В сервисе починки роботов очень важно соблюдать порядок. Главный механик любит, чтобы все роботы стояли друг за другом — сначала только сломанные (если они есть), а потом исправные (если они есть). По ночам роботы всё время гуляют по ангару, и к утру порядок, установленный главным механиком, нарушается. Механик решил наказывать роботов, которые нарушают порядок, и удалять из очереди. Но роботы взбунтовались и требуют равноправия — если уж удалять из очереди, то равное количество исправных и сломанных роботов. Сломанные роботы обозначаются буквой B (broken), исправные — буквой W (working). Есть строка из букв B и W. Надо удалить наименьшее и равное количество сломанных и исправных роботов так, чтобы в очереди сначала стояли только сломанные, а потом только исправные. Может оказаться, что одних или других нет. Общее количество роботов в очереди не превышает 10 000. Выведи количество удалённых роботов и очередь, которая получилась после удаления нарушивших правило роботов. Если в очереди никого не осталось, выведи «НИКОГО НЕ ОСТАЛОСЬ». Ввод BWBWWBW BWWWWW BBBBB WWBB Вывод 2 BBWWW 0 BWWWW 0 BBBBB 4 НИКОГО НЕ ОСТАЛОСЬ 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	07.03.2023, 06:05
	Aleksander964, похоже на правду, только решение за O(n). 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	07.03.2023, 14:37
	Alexarh, вроде стандартная задача на "два указателя" 0

@Aleksander964 1 / 1 / 0 Регистрация: 05.10.2020 Сообщений: 2
	09.03.2023, 18:17
	да, первое решение быстрее моего, но я зато свое решение сам придумал за пол часа, оптимизировал, и оно вроде работает даже быстро, я проводил тесты по времени решения с большими строками, мой код работает в 4.5 раза дольше максимум например строка 'B'+'W'10000+'B'9999+'W' мой код выполнился за 20 секунд а первый (не мой) за 5 Добавлено через 8 минут eaa, и решение у меня 158/158 баллов за олимпиаду эту) 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	09.03.2023, 18:28
	Aleksander964, если сам решал, то молодец! 0