Đo nước
Xem PDF
Điểm:
1500 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Bờm đang nghiên cứu mực nước biển ở hành tinh Quạt Mo. Sau nhiều ngày theo dõi, Bờm nhận thấy rằng quy luật của mực nước biển là: mực nước biển của một ngày bất kì bằng trung bình cộng mực nước biển của ngày hôm trước và ngày hôm sau. Dựa vào ghi chép mực nước biển hai ngày đầu của Bờm, hãy tính toán mực nước biển ngày thứ \(N\).
Input
- Dòng 1: chứa 2 số nguyên \(b, a\) là mực nước biển 2 ngày đầu (\(-100 \le a, b \le 100\)). Số \(a\) là mực nước ngày thứ nhất, số \(b\) là mực nước ngày thứ 2.
- Dòng 2: chứa số nguyên dương \(N\) (\(3\le N\le 10^{12}\)).
Output
- Mực nước biển ngày thứ \(N\).
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(n\le 10^7\)
- Subtask \(2\) (\(50\%\) số điểm): \(10^7<n\le 10^{12}\)
Example
Test 1
Input
1 2
3Output
3Test 2
Input
3 1
3Output
-1
Bình luận
:))
kì vậy
sao test 2 bằng -1 v
bài này code thonny là gì vậy cho code đi
à nhầm nha
hình như không đúng đấy hungeazyITistrue
sử dụng cấp số cộng
Đơn giản thôi nha mn!
Chỉ cần a+(n-1)*(b-a) là xong nha! =)))
hình như test yếu hay sao mà O(n) mà vẫn acc
Mình xin chia sẻ lời giải cho bài này như sau:
Gọi \(u_n\) là mực nước biển ngày thứ \(n\). Khi đó, theo đề ta có công thức sau: \(u_n=\frac{u_{n-1}+u_{n+1}}{2}\iff u_{n+1}=2u_n-u_{n-1}\rightarrow (1)\) với \(u_1=a,u_2=b\)
Dưới đây mình sẽ trình bày 3 cách có thể tiếp cận bài này như sau:
Cách 1: Biến đổi thông thường:
Từ $(1)\implies u_{n+1}-u_{n}=u_n-u_{n-1}=...=u_2-u_1 $
\(\implies u_{n+1}-u_n=u_2-u_1\iff u_{n+1}=u_{n}+(b-a)=u_{n-1}+2*(b-a)=...=u_1+n*(b-a)=a+n*(b-a)\)
Từ đây ta suy ra được: \(u_{n}=a+(n-1)*(b-a)\). Đến đây ta chỉ cần thế số \(a,b,n\) là bài toán đã được giải quyết.
Độ phức tạp là \(O(1)\).
Cách 2: Sử dụng phương trình đặc trưng:
Ta xét phương trình đặc trưng sau: \(\lambda^2 = 2\lambda -1\iff \lambda^2-2\lambda+1=0\iff (\lambda-1)^2=0\iff \lambda=1\)
Do đó: Phương trình \((1)\) sẽ có dạng như sau: \(u_n = (P*n+Q)*1^{n}=P*n+Q\rightarrow (2)\) với \(P,Q\) là một số nào đó, và bây giờ ta cần phải đi tìm.
Đơn giản, ta chỉ lần lượt thay \(u_1=a,u_2=b\) để tìm \(P,Q\). Và ta làm như sau:
Từ \((2)\) ta suy ra được:
\(\left\{\begin{matrix} u_1 = P+Q\rightarrow (3) \\ u_2 = 2*P+Q\rightarrow (4) \end{matrix}\right.\)
Lấy \((4)-(3)\) vế theo vế ta được: \(P=u_2-u_1=b-a\). Và từ đây ta dễ dàng suy ra được: \(Q=u_1-P=a-(b-a)=b\)
Vậy \(u_n=(b-a)*n+b =a+ (n-1)*(b-a)\). Và đến đây công việc còn lại chỉ là thế số.
Cách 3: Sử dụng nhân ma trận.
Ý tưởng của nhân ma trận như sau:
Từ phương trình \((1)\) đã cho, ta đưa về một phương trình liên quan đến ma trận có dạng như sau:
\(\begin{pmatrix} a_{n-1} & a_{n} \end{pmatrix} . \begin{pmatrix} u_1 & u_2 \\ u_3 & u_4 \end{pmatrix} = \begin{pmatrix} a_{n} & a_{n+1} \end{pmatrix}\) , trong đó \(u_1,u_2,u_3,u_4\) là các số nào đó .
Vậy việc đưa về phương trình ma trận trên có ý nghĩa gì ? Để hiểu rõ hơn, các bạn cùng theo dõi nhé, vì kĩ thuật này rất hay được sử dụng đối với những dãy truy hồi tuyến tính như vầy !
Giả sử tồn tại \(u_1,u_2,u_3,u_4\) thoả mãn: \(\begin{pmatrix} a_{n-1} & a_{n} \end{pmatrix} . \begin{pmatrix} u_1 & u_2 \\ u_3 & u_4 \end{pmatrix} = \begin{pmatrix} a_{n} & a_{n+1} \end{pmatrix}\rightarrow (I)\)
Và nhiệm vụ của ta là đi tìm các số \(u_1,u_2,u_3,u_4\). Chúng được thực hiện như sau:
Gọi \(L(I),R(I)\) lần lượt là về trái và vế phải của phương trình \((I)\).
Ta có: \(L(I) = \begin{pmatrix} a_{n-1} & a_{n} \end{pmatrix} . \begin{pmatrix} u_1 & u_2 \\ u_3 & u_4 \end{pmatrix} = \begin{pmatrix} a_{n-1}u_1+a_nu_3 & a_{n-1}u_3+a_{n}u_4 \end{pmatrix}=R(I)=\begin{pmatrix} a_{n} & a_{n+1} \end{pmatrix}\)
Từ đây ta suy ra được:
\(\left\{\begin{matrix} a_{n-1}u_1+a_nu_3=a_n\rightarrow (5) \\ a_{n-1}u_2+a_{n}u_4=a_{n+1}\rightarrow (6) \end{matrix}\right.\)
Từ \((1),(5),(6)\), sử dụng đồng nhất thức ta suy ra được:\((u_1,u_2,u_3,u_4)=(0,-1,1,2)\)
hay \(\begin{pmatrix} u_1 & u_2 \\ u_3 & u_4 \end{pmatrix}=\begin{pmatrix} 0 & -1 \\ 1 & 2 \end{pmatrix} \rightarrow M\) (và ta gán ma trận này là ma trận \(M\))
Gọi \(p_n=\begin{pmatrix} a_{n} & a_{n+1} \end{pmatrix}\)
Khi đó \((I)\iff p_n=p_{n-1}*M = p_{n-2}*M^2=...=p_1*M^{n-1}\), trong đó \(p_1=\begin{pmatrix} a & b \end{pmatrix}\)
Và nhiệm vụ của ta đơn giản là nhân ma trận. Để tính được \(M^n\), ta tiếp tục sử dụng luỹ thừa nhị phân.
Độ phức tạp của bài này là : \(O(log(n))\)
Vì cách \(1\), cách \(2\) khá đơn giản nền mình chỉ trình bày code của bài \(3\) tại đây
Như vậy là mình đã trình bày xong 3 cách để giải quyết bài toán này !
Ps: Nếu có gì thắc mắc, các bạn cứ cmt nhé !