Friday 15 October 2021

P201PROJ - Just a math

Đọc đề trên SPOJ PTIT

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$.

Code mẫu (C++).

Happy coding!

No comments:

Post a Comment

Popular posts