Cho một số chứa nhiều chữ số lặp lại dưới dạng chuỗi. Mục tiêu: tìm số cách đọc (spell) số đó. Ví dụ 112233 có thể đọc là "double one, double two, double three" hoặc "one one two two three three".
Cách làm: kiểm tra các chữ số liên tiếp. Nếu số là "13" chỉ có 1 cách đọc "one three" (2^0). Nếu "113" có 2 cách: "double one three", "one one three" (2^1). Do đó, đếm số lần lặp liên tiếp của mỗi chữ số, nhân kết quả với 2^(count-1).
Hãy hiểu qua ví dụ.
Đầu vào
num="11211"
Đầu ra
Count of ways to spell a number with repeated digits are: 4
Giải thích
cách đọc: 1. One one two one one 2. Double one two one one 3. One one two double one 4. Double one two double one
Đầu vào
num="2212"
Đầu ra
Count of ways to spell a number with repeated digits are: 2
Giải thích
cách đọc: 1. Two two one two 2. Double two one two
Phương pháp
- Nhận chuỗi str biểu diễn số.
- Hàm word_spell(string str) trả về số cách đọc.
- Khởi tạo count = 1.
- Duyệt str, đếm temp = số lần lặp liên tiếp của chữ số hiện tại.
- count = count * 2^(temp-1).
- Trả về count.
Ví dụ
#include<bits/stdc++.h> using namespace std; long long int word_spell(string str){ long long int count = 1; int len = str.length(); for (int i=0; i<len; i++){ int temp = 1; while(i < len-1 && str[i+1] == str[i]){ temp++; i++; } count = count * pow(2, temp-1); } return count; } int main(){ string str = "222211"; cout<<"Count of ways to spell a number with repeated digits are: "<<word_spell(str); return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Count of ways to spell a number with repeated digits are: 16