Вывести строку из символов В и G,

Question

Вывести строку из символов В и G,

Рейтинг: 0Ответов: 1Опубликовано: 22.01.2023

задача такая, вводятся два числа условно x и y, x =B, а y = G, строка длины x+y , надо вывести (любую) строку, в которой рядом с B стоит G и наоборот с G стоит B. Если так расставить символы не удаётся, вывести строку NO SOLUTION Например: Входные данные

5 5

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

BGBGBGBGBG

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

5 3

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

BGBGBBGB

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

100 1

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

NO SOLUTION

from itertools import product
x,y = map (int,input().split())
c = x+y
if x/y > 2:
    print('NO SOLUTION')
    
for i in product('BG',repeat = c):
    s = ''.join(i)
    if (s[0]!=s[1] and s[-1]!=s[-2]) and (not 'BBB' in s and not 'GGG' in s):
        print(s)
        break

Проблема в том, что при вводе x и y >10, программа выполняется слишком долго, максимальное значение x и y может быть равно 100 ,проблема в том, как ускорить процесс перебора в itertools для большого количества символов x и y ?

python

Источник: Stack Overflow на русском

Answer 1

▲ 2

Такая функция должна подойти:

def create_string(x, y):
    swapped = False
    if x < y:
        x, y, swapped = y, x, True
    
    # варианты, когда нельзя собрать строку    
    if x==0 or y==0 or x>y*2: 
        return 'NO SOLUTION'
    if x==y: # если x и y равны, то ответ - просто чередуем буквы
        return 'BG'*x
    # общий вид строки : b gbb gbb gbb ... gb        
    string  = ('b' + 'gbb'*(y-1) + 'gb')
    # здесь мы убираем лишние буквы 'b' из "общего вида" строки
    string = string.replace('gbb', 'gb', string.count('b')-x)
    
    # если мы меняли x и y местами, то буквы g и b тоже надо поменять в ответе
    if swapped:
        return string.replace('g', 'B').replace('b', 'G')    
    return string.replace('g', 'G').replace('b', 'B')

Спасибо @MBo за идею перейти от генерации+замены к чистой генерации.

def create_string(x, y):
    swapped = False
    if x < y:
        x, y, swapped = y, x, True
    
    # варианты, когда нельзя собрать строку    
    if x==0 or y==0 or x>y*2: 
        return 'NO SOLUTION'
    if x==y: # если x и y равны, то ответ - просто чередуем буквы
        return 'BG'*x
    string  = 'b' + 'gbb'*(x-y-1) + 'gb'*(2*y-x+1)
    # если мы меняли x и y местами, то буквы g и b тоже надо поменять в ответе
    if swapped:
        return string.replace('g', 'B').replace('b', 'G')    
    return string.replace('g', 'G').replace('b', 'B')

Вывести строку из символов В и G,

Ответы