Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.96/91: Рейтинг темы: голосов - 91, средняя оценка - 4.96
-46 / 1 / 0
Регистрация: 26.09.2019
Сообщений: 67

Удалить наименьшее количество синих точек так, чтобы сначала шли только синие, а потом – только красные

14.11.2019, 16:17. Показов 18714. Ответов 29
Метки нет (Все метки)

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

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

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

Примеры
входные данные
BBBRBRBRR
выходные данные
BBBRRRR
2
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
14.11.2019, 16:17
Ответы с готовыми решениями:

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

Удалить ОДИНАКОВОЕ количество синих и красных, чтобы сначала шли только синие, а потом – только красные
Не могу понять... Дана цепочка, состоящая из синих (B) и красных (R) точек. Нужно удалить наименьшее одинаковое количество синих и...

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

29
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
14.11.2019, 17:34
Тот же вопрос: красные нельзя удалять?
0
-46 / 1 / 0
Регистрация: 26.09.2019
Сообщений: 67
14.11.2019, 17:41  [ТС]
Тот же ответ: нельзя)
0
0 / 0 / 1
Регистрация: 26.11.2016
Сообщений: 19
14.11.2019, 17:47
Как то так?

Python
1
2
n = 'BBBRBRBRR'
n = sorted(n)
хотя нет, тут надо перебирать с условием...
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
14.11.2019, 17:49
PsyPerception, перемещать тоже нельзя
0
-46 / 1 / 0
Регистрация: 26.09.2019
Сообщений: 67
14.11.2019, 17:54  [ТС]
Не, что-то не работает
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
14.11.2019, 18:02
Конечно не работает. Ведь ничего не удалили.
0
0 / 0 / 1
Регистрация: 26.11.2016
Сообщений: 19
14.11.2019, 18:31
Лучший ответ Сообщение было отмечено mik-a-el как решение

Решение

Немного извращенно, но это работает. Где вам задают такие садомазо-задания?
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n = 'BBBRBRBRR'
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)
0
1732 / 970 / 199
Регистрация: 22.02.2018
Сообщений: 2,693
Записей в блоге: 6
14.11.2019, 18:44
HogaLe, Я вижу только единственный алгоритм решения, удалить все синии точки расположенные после первой красной. То есть в цикле ищем первую красную точку и затем поставив флаг и продолжая цикл удаляем все последующие синии точки.
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
14.11.2019, 18:46
Лучший ответ Сообщение было отмечено mik-a-el как решение

Решение

Python
1
2
3
4
5
6
>>> s = 'BBBRBRBRR'
>>> l = s.lstrip('B')
>>> l
'RBRBRR'
>>> 'B' * (len(s) - len(l)) + 'R' * l.count('R')
'BBBRRRR'
0
0 / 0 / 1
Регистрация: 26.11.2016
Сообщений: 19
14.11.2019, 18:48
Viktorrus, пример предложенного вами алгоритма в моей реализации выше
0
1732 / 970 / 199
Регистрация: 22.02.2018
Сообщений: 2,693
Записей в блоге: 6
14.11.2019, 18:51
PsyPerception, При варианте 'BRBBRBRBRR' Ваш код выдает не правильный ответ.
BRBRRRRR
3
0
0 / 0 / 1
Регистрация: 26.11.2016
Сообщений: 19
14.11.2019, 18:52
Рыжий Лис, ваш пример гораздо более pythonic
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
14.11.2019, 18:56
Лучший ответ Сообщение было отмечено mik-a-el как решение

Решение

PsyPerception, если хочется перебирать строку, то проще делать в два цикла:
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
s = 'BBBRBRBRR'
result = ''
count = 0
i = 0
while s[i] == 'B':
    result += 'B'
    i += 1
 
while i < len(s):
    if s[i] == 'R':
        result += 'R'
    else:
        count += 1
    i += 1
print(result)
print(count)
0
0 / 0 / 1
Регистрация: 26.11.2016
Сообщений: 19
14.11.2019, 18:59
Viktorrus, спасибо, что указали, я пока тоже еще ученик в алгортимах
0
Эксперт Python
 Аватар для dondublon
4653 / 2073 / 366
Регистрация: 17.03.2012
Сообщений: 10,183
Записей в блоге: 6
14.11.2019, 19:55
Наивный алгоритм через рекурсию:
Python
1
2
3
4
5
6
7
8
def solve(a):
    а = наш список точек
    if a[0]=='B':
       # начинается с синей. Значит, для правильного ответа её удалять не нужно, а удалить надо ровно столько, сколько надо удалить в хвосте:
        return solve(a[1:])
    else:
        # начинается с красной. Раз красные удалять нельзя, значит, придётся удалить ВСЕ синие. 
        return sum(itm=='B' for itm in a)
Повторяю: это наивное решение. Для больших массивов оно может вылететь по производительности либо с recursion error, если не влезет. Так что желательно развернуть в массив, но это надо немного посидеть, подумать, оформить

Добавлено через 12 минут
Если долго-долго смотреть надо код, то сквозь строчки начинает просвечивать очевидное решение. Алгоритм в нерекурсивном виде довольно простой, оказывается. Находим первую красную и удаляем все синие далее
0
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
14.11.2019, 19:56
Цитата Сообщение от dondublon Посмотреть сообщение
Алгоритм в нерекурсивном виде довольно простой, оказывается. Находим первую красную и удаляем все синие далее
lol, да?
0
Эксперт Python
 Аватар для dondublon
4653 / 2073 / 366
Регистрация: 17.03.2012
Сообщений: 10,183
Записей в блоге: 6
15.11.2019, 09:41
Рыжий Лис, именно.
0
1 / 1 / 0
Регистрация: 12.03.2020
Сообщений: 13
20.03.2020, 13:49
Цитата Сообщение от Рыжий Лис Посмотреть сообщение
Алгоритм в нерекурсивном виде довольно простой, оказывается. Находим первую красную и удаляем все синие далее
lol, да?
Верно для этого примера, но неверно для условия
прример
Вход
BBBRBBRBRBRRRRRR
Выход
BBBBBRRRRRRR
4

Добавлено через 1 час 0 минут
Цитата Сообщение от lektrik Посмотреть сообщение
Верно для этого примера, но неверно для условия
прример
Вход
BBBRBBRBRBRRRRRR
Выход
BBBBBRRRRRRR
4
Сорян, там условие другое, удалять и красные и синие
0
5516 / 2869 / 571
Регистрация: 07.11.2019
Сообщений: 4,760
20.03.2020, 18:10
Лучший ответ Сообщение было отмечено mik-a-el как решение

Решение

Python
1
2
3
4
s='BBBRBRBRR'
s2=s[0:s.index('R')]+''.join(filter(lambda x: x=='R', s[i:]))
print(s2)
print(len(s)-len(s2))
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
20.03.2020, 18:10
Помогаю со студенческими работами здесь

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

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

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

Удалить наименьшее одинаковое количество синих и красных точек так, чтобы выполнялось условие
программа выдает s как пустую стироку вот условие Дана цепочка, состоящая из синих (B) и красных (R) точек. Нужно удалить наименьшее...

Переставить числа так, чтобы сначала шли только 0, затем только 1, затем только 2
Даны целые числа A,A,A,...,A, каждое из которых является либо 0, либо 1, либо 2. Переставить числа так, чтобы сначала шли только 0, затем...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Автоматическое создание документа при проведении другого документа
Maks 29.03.2026
Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .
Настройка движения справочника по регистру сведений
Maks 29.03.2026
Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .
Автозаполнение реквизита при выборе элемента справочника
Maks 27.03.2026
Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .
Сумматор с применением элементов трёх состояний.
Hrethgir 26.03.2026
Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа
Maks 26.03.2026
Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .
Команды формы и диалоговое окно
Maks 26.03.2026
1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT?
DevAlt 26.03.2026
Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .
Отправка уведомления на почту при создании или изменении элементов справочника
Maks 24.03.2026
Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru