Chương trình tìm chuỗi nhỏ nhất theo từ điển sau khi áp dụng phép toán trong Python

Cho chuỗi số s, giá trị a, b. 2 phép toán: (1) cộng a vào các vị trí lẻ (0-indexed), modulo 10; (2) xoay phải b vị trí. Áp dụng tùy ý lần, tìm chuỗi nhỏ nhất theo từ điển.

Ví dụ: s="5323", a=9, → "2050". Các bước: xoay → "5323", +a → "5222", +a → "5121", xoay → "2151", +a → "2050".

Giải thuật (BFS trạng thái)

1. Set seen lưu chuỗi đã gặp.
2. Queue deq bắt đầu từ s.
3. BFS: pop curr, sinh add_(curr, a) và rotate_(curr, b), nếu chưa thấy thì push vào queue và seen.
4. Trả về min(seen) (nhỏ nhất theo từ điển).

Ví dụ minh họa

from collections import deque

def add_(s, a):
    res = ''
    for idx, ch in enumerate(s):
        if idx % 2 == 1:
            num = (int(ch) + a) % 10
            res += str(num)
        else:
            res += ch
    return res

def rotate_(s, b):
    idx = len(s) - b
    return s[idx:] + s[:idx]

def solve(s, a, b):
    seen = set()
    deq = deque([s])
    while deq:
        curr = deq.popleft()
        seen.add(curr)
        ad = add_(curr, a)
        if ad not in seen:
            deq.append(ad)
            seen.add(ad)
        ro = rotate_(curr, b)
        if ro not in seen:
            deq.append(ro)
            seen.add(ro)
    return min(seen)

s = "5323"
a = 9
b = 2
print(solve(s, a, b))

Đầu vào

"5323", 9, 2

Đầu ra

2050