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

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

14.11.2019, 16:17. Показов 18462. Ответов 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
 Аватар для Рыжий Лис
5972 / 3734 / 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
 Аватар для Рыжий Лис
5972 / 3734 / 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
 Аватар для Рыжий Лис
5972 / 3734 / 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
 Аватар для Рыжий Лис
5972 / 3734 / 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
 Аватар для Рыжий Лис
5972 / 3734 / 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
4652 / 2072 / 366
Регистрация: 17.03.2012
Сообщений: 10,182
Записей в блоге: 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
 Аватар для Рыжий Лис
5972 / 3734 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
14.11.2019, 19:56
Цитата Сообщение от dondublon Посмотреть сообщение
Алгоритм в нерекурсивном виде довольно простой, оказывается. Находим первую красную и удаляем все синие далее
lol, да?
0
Эксперт Python
 Аватар для dondublon
4652 / 2072 / 366
Регистрация: 17.03.2012
Сообщений: 10,182
Записей в блоге: 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
5515 / 2868 / 571
Регистрация: 07.11.2019
Сообщений: 4,758
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
Ответ Создать тему
Новые блоги и статьи
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image
8Observer8 27.01.2026
Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
влияние грибов на сукцессию
anaschu 26.01.2026
Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru