Tóm tắt đề:
Cho $2$ số nguyên $A, B$. Đếm số cặp $(a, b)$ thỏa $1 \leq a \leq A, 1 \leq b \leq B$ và $a*b + a + b = \overline{ab}$. Ở đây ta nhìn nhận $\overline{ab} = a*10^{\lceil\log_{10}(b+1)\rceil}+b$.
Ví dụ: với $A = 1, B = 11$, ta có cặp $a = 1, b = 9$ thỏa yêu cầu: $1\times 9 + 1 + 9 = 19$.
Nhận xét: Bài này rất dễ, nhưng người ra đề thách thức độ can đảm của người làm bằng cách giấu constraint đi mất!
Gợi ý:
Cứ tin rằng $A, B$ store được trong int_64t. Giả sử $b$ có lần lượt $2, 3, 4$ chữ số, xong chuyển vế biểu thức và suy luận từng trường hợp. Nếu vẫn chưa làm ra, kéo qua hình để xem hướng dẫn giải.
Hướng giải:
Giả sử $b$ có $1$ chữ số, khi đó $\overline{ab} = 10a + b$. Biến đổi biểu thức ta thu được $a(b+1) = 10a \Rightarrow \forall a \in [1, A], b = 9$ thì các cặp $(a, b)$ đều thỏa đẳng thức.
Ta lại suy luận, nếu $b$ có $2$ chữ số? Câu trả lời có thể suy ra ngay được: $a(b+1)=100a \Rightarrow \forall a \in [1, A], b = 99$ thì các cặp $(a, b)$ cũng thỏa đẳng thức.
Đến cuối cùng ta sẽ suy luận được: đáp án của đề bài là $A\times $ số lượng số $9, 99, 999, ..$ nhỏ hơn $B$.
Happy coding!
No comments:
Post a Comment