Người bạn của Henry
Xem PDF\(Kaninho\) là hậu duệ đời thứ 15 của 2 đại dòng dõi Kante và Mourinho, đồng thời cũng là bạn chung lớp với \(Henry\). Vì biết \(Henry\) là người học giỏi về lập trình, nên một hôm sang nhà \(Henry\) chơi, \(Kaninho\) đã đố cậu ấy một bài toán như sau:
Cho xâu \(S\) được biểu diễn dưới dạng sau: \(a_0a_1a_2 \cdots a_n\) trong đó \(a_i\) là kí tự số (tức là \(a_i \in\){0 \(\ldots\) 9}). \(Kaninho\) đã xây dựng xâu \(T\) từ xâu \(S\) và được biểu diễn dưới dạng: \(b_0b_1b_2 \cdots b_n\) trong đó \(b_i\) là kí tự số (tức là \(b_i \in\){0 \(\ldots\) 9}) theo quy tắc sau:
\(b_0\) là một kí tự số bất kì thuộc tập {0 \(\ldots\) 9}
\(b_i\)=\(\frac{b_{i - 1}+a_i}{2}\) hoặc \(b_i=\frac{b_{i-1} + a_i}{2}\) với mọi \(1 \leq i \leq n\).
Hỏi có bao nhiêu xâu \(T\) khác nhau được sinh ra từ \(S\) theo quy tắc trên và \(T \neq S\)
Là người bạn tốt của \(Henry\), hãy giúp anh ấy một tay nhé !
Input
- Một dòng duy nhất chứa xâu \(S\) \((1 \leq |S| \leq 50)\)
Output
- Số lượng xâu \(T\) khác nhau được sinh ra từ \(S\)
Example
Test 1
Input
1 Output
9Note
- Ứng với \(S=1\). Ta có thể sinh ra \(9\) xâu \(T\) khác nhau và tất cả chúng đều khác \(S=1\). Đó là \(T \in\){\(′0′,′2′,′3′,′4′,′5′,′6′,′7′,′8′,′9′\)}
Bình luận
jumptozero cho em hỏi:
bi=⌈(bi−1+ai)/2⌉ hoặc bi=⌊(bi−1+ai)/2⌋ viết trên đề là 1 hay là 2 cái khác nhau vậy?
hhoangcpascal, mình đã edit lại đề ! Cảm ơn bạn đã báo cáo !
tác giả giải thích ví dụ giúp với ạ, có lẽ hiểu đề nhưng chưa rõ ví dụ lắm!