Giả sử chúng ta có một chuỗi s chỉ có các chữ số và cũng có hai giá trị a và b. Chúng ta có thể áp dụng bất kỳ một trong hai thao tác sau vào bất kỳ số lần nào và theo bất kỳ thứ tự nào trên s -
-
Thêm 'a' vào tất cả các mục có vị trí lẻ của s (được lập chỉ mục 0). Nếu chữ số là 9, thì bằng cách thêm một cái gì đó với nó sẽ được chuyển về 0.
-
Xoay 's' sang phải theo b vị trí.
Vì vậy, chúng ta phải tìm chuỗi nhỏ nhất về mặt từ vựng mà chúng ta có thể nhận được bằng cách áp dụng các phép toán trên bất kỳ số lần nào trên s.
Vì vậy, nếu đầu vào là s ="5323" a =9 b =2, thì đầu ra sẽ là 2050 vì nếu chúng ta làm theo
- Xoay vòng:"5323"
- Thêm:"5222"
- Thêm:"5121"
- Xoay vòng:"2151"
- Thêm:"2050"
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- đã thấy:=một tập hợp mới
- deq:=một hàng đợi mới với một phần tử 's'
- trong khi deq không trống, hãy thực hiện
- curr:=phần tử bị xóa đầu tiên của deq
- chèn thanh cuộn vào bộ đã nhìn thấy
- ad:=thực hiện thao tác thêm đã cho trên curr
- nếu quảng cáo không được nhìn thấy, thì
- chèn quảng cáo vào cuối deq
- chèn quảng cáo vào tập hợp đã nhìn thấy
- ro:=thực hiện thao tác xoay trên curr
- nếu ro không được nhìn thấy, thì
- chèn ro vào cuối deq
- chèn ro vào tập hợp đã thấy
- trả lại số tiền tối thiểu đã thấy
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
from collections import deque def add_(s,a): res = '' for idx, i in enumerate(s): if idx % 2 == 1: num = (int(i) + a) % 10 res += str(num) else: res += i return res def rotate_(s, b): idx = len(s)-b res = s[idx:] + s[0:idx] return res 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