Задача про роботов

Рейтинг: -5Ответов: 1Опубликовано: 04.03.2023

есть задача и я не совсем понимаю как ее решить, понял основной принцип но не до конца.

Задача: В сервисе починки роботов очень важно соблюдать порядок. Главный механик любит, чтобы все роботы стояли друг за другом — сначала только сломанные (если они есть), а потом исправные (если они есть). По ночам роботы всё время гуляют по ангару, и к утру порядок, установленный главным механиком, нарушается. Механик решил наказывать роботов, которые нарушают порядок, и удалять из очереди. Но роботы взбунтовались и требуют равноправия — если уж удалять из очереди, то равное количество исправных и сломанных роботов. Сломанные роботы обозначаются буквой B (broken), исправные — буквой W (working). Есть строка из букв B и W. Надо удалить наименьшее и равное количество сломанных и исправных роботов так, чтобы в очереди сначала стояли только сломанные, а потом только исправные. Может оказаться, что одних или других нет. Общее количество роботов в очереди не превышает 10 000. Выведи количество удалённых роботов и очередь, которая получилась после удаления нарушивших правило роботов. Если в очереди никого не осталось, выведи "НИКОГО НЕ ОСТАЛОСЬ".

Поначалу показалось что понял как ее решить, но когда увидел ввод/вывод то немного сломался.

Ввод:BWBWWBW Вывод: 2 BBWWW

Ввод: WBBWWBBW Вывод: 4 BBWW

Не могу понять как определить какое количество роботов надо исключить, вроде бы если 'перед ночью' (на примере 2 ввода) было BBBBWWWW, то после вывода идет BBWW. Надеюсь кто нибудь объяснит мне как это сделать)

python python-3.x
Источник: Stack Overflow на русском

Ответы

▲ 1Принят

Количество роботов для удаления d(s) обладает следующими свойствами:

  1. d() = 0 - нет роботов - нечего удалять,
  2. d(B...) = d(...) - сломанный робот слева на результат не влияет,
  3. d(...W) = d(...) - рабочий робот справа на результат не влияет,
  4. d(W...B) = 2 + d(...) - рабочий слева, сломанный справа составляют одну пару.

d(BWBWWBW) =2 d(WBWWBW) =3 d(WBWWB) =4 2 + d(BWW) =2

=2 2 + d(WW) =3 2 + d(W) =3 2 + d() =1 2

d(WBBWWBBW) =3 d(WBBWWBB) =4 2 + d(BBWWB) =2 2 + d(BWWB) =2

=2 2 + d(WWB) =4 4 + d(W) =3 4 + d() =1 4

Эта функция вычисляется за линейное время. Из неё же можно сделать функцию, которая вернёт правильный строй после удаления. Но это будет в другом ответе.