Số chín ưa thích

Điểm: 4,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một số nguyên dương $a$ chỉ gồm các chữ số từ $1$ đến $9$ (không có chữ số $0$ ).

Trong một thao tác, bạn được chọn hai chữ số kề nhau trong số đó có tổng bằng $9$ , rồi thay cặp hai chữ số đó bằng một chữ số $9$ duy nhất. Bạn được thực hiện thao tác này nhiều lần tùy ý (kể cả không lần nào).

Hãy đếm số lượng các số khác nhau có thể nhận được sau quá trình thao tác, với điều kiện số chữ số $9$ trong kết quả là lớn nhất có thể.

Đề bài đảm bảo đáp án không vượt quá $2^{63} - 1$ .

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $a$ .

Dữ liệu ra

Một dòng duy nhất chứa đáp án.

Ràng buộc

$1 \leq a \leq 10^{100000}$
$a$ không chứa chữ số $0$ .

Ví dụ

Input	Output	Giải thích
369727	2	Có thể biến đổi $369727 \to 99727 \to 9997$ hoặc $369727 \to 99727 \to 9979$ . Cả hai đều có $3$ chữ số $9$ — đây là số chữ số $9$ tối đa, và có $2$ số phân biệt đạt được.
123456789987654321	1	Chỉ có duy nhất một cách biến đổi đạt số chữ số $9$ tối đa.
1	1	Không có thao tác nào thực hiện được; chính bản thân số $1$ là kết quả duy nhất.

Bình luận

Không có bình luận tại thời điểm này.