@Quantorianech-SiriusER

Синие и красные?

Здравствуйте!
Есть задача с
условием:
Дана цепочка, состоящая из синих (B) и красных (R) точек. Нужно удалить наименьшее одинаковое количество синих и красных точек так, чтобы сначала шли только синие, а потом – только красные.

Входные данные

Входная строка содержит только символы 'B' и 'R' без пробелов.

Выходные данные

Нужно вывести полученную цепочку, в которой сначала идут только синие точки, а потом – только красные. Во второй строке нужно вывести количество удалённых (синих и красных) точек.

и примерами:
Примеры
Ввод
BBBRBBRBRBRRRRRR
Вывод
BBBBBRRRRRRR
4
Пытаюсь пол часа решить, использую разные варианты, но всё равно не получается.
Вот последний вариант кода:
n = input()
s = ''
count = 0
for g in range(0, len(n)):
    if g == len(n) - 1:
        break
    if n[g] == 'B' and n[g + 1] == 'B':
        s += 'B'
        continue
    elif n[g] == 'B' and n[g + 1] == 'R':
        if count == 0:
            s += 'B'
        else:
            s += 'R'
        continue
    elif n[g] == 'R' and n[g + 1] == 'B':
        s += 'R'
        count += 1
        continue
    elif n[g] == 'R' and n[g + 1] == 'R':
        continue
print(s)
print(count)
Что я делаю не так? В чём и где ошибки? Подскажите, пожалуйста, как правильно решить задачу и что использовать?!
  • Вопрос задан
  • 214 просмотров
Пригласить эксперта
Ответы на вопрос 2
Мне кажется что здесь надо для начала понять задачу, а не перебирать в лоб
А так мне кажется что это решение имеет место:

spoiler
s = 'BBBRBBRBRBRRRRRR'
end_b = s.find('R')
start_r = s.rfind('B')+1
new_s = s[end_b:start_r]
len_r = new_s.replace("B","").__len__()
len_b = new_s.replace("R","").__len__()
if(len_r >= len_b):
    print(s[:end_b] + new_s.replace("B","") + s[start_r:])
    print(len_b)
else:
    print(s[:end_b] + new_s.replace("R", "") + s[start_r:])
    print(len_r)


Исправленный вариант:
s = str(input())

def subst_ba(s):
    end_b = s.find('R')
    start_r = s.rfind('B')+1
    new_s = s[end_b:start_r]
    if new_s.__len__() > 2:
        recurce_s = subst_ba(new_s[1:-1])
    else:
        recurce_s = (new_s[1:-1],0)
    return (s[:end_b] + recurce_s[0] + s[start_r:] , recurce_s[1]+2)

res_s = subst_ba(s)
print(res_s[0])
print(res_s[1])
Ответ написан
yuzoru
@yuzoru
Полагаю, как-то так. Относительно алгоритма - в начале всего действия нахожу начало и конец новой строки, после чего автоматически подсчитываю кличество ошибок перед первыми "нужными" буквами, после найдя границы правой строки, подсчитываю, сколько ошибок будет если я нынешнее тело строки отдам под красный цвет, после прохожусь по строке, аперируя локальными ошибками по цветам, находя минимальную сумму ошибок, и сравнивая то, эквивалентны ли суммы локальных ошибок по буквам с их глобальными ошибками.

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

samp = str(input())

calc = 0 # result sum of mistakes
b_mistakes = 0 # global B mistakes
r_mistakes = 0 # global R mistakes

begin = 0
end = len(samp)

for i in range(0, len(samp), +1):
    if samp[i] == "R":
        r_mistakes += 1
        begin += 1
        calc += 1
    else:
        break

for j in range(len(samp) - 1, begin, -1):
    if samp[j] == "B":
        b_mistakes += 1
        end -= 1
        calc += 1
    else:
        break

b_local = 0 # mistakes of right side (as B)
r_local = 0 # mistakes of left side (as R)
local_min = 1000000 # sum of minimum mistakes
pos_x = begin

for i in range(begin + 1, end):
    if samp[i] == "B": b_local += 1

for i in range(begin + 1, end):
    if samp[i] == "R":
        r_local += 1
    else:
        b_local -= 1

    if (local_min > b_local + r_local and b_mistakes + b_local == r_mistakes + r_local):
        local_min = b_local + r_local
        pos_x = i

for i in range(len(samp)):
    if i <= pos_x:
        print("B" if samp[i] == "B" else "", end = "")
    else:
        print("R" if samp[i] == "R" else "", end = "")
print()

print(calc + local_min)
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы