Người bạn của Henry

Xem PDF

Điểm: 300 Thời gian: 0.1s Bộ nhớ: 256M Input: bàn phím Output: màn hình

\(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
9
Note
  • Ứ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


  • 0
    longvu    2:42 p.m. 13 Tháng 2, 2021

    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?


    • 1
      jumptozero    2:45 p.m. 13 Tháng 2, 2021

      Là 2 cái khác nhau bạn một cái là ceil và một cái là floor !

    2 bình luận nữa