Byte >> Runes

Hóng sol bài C, D, K, L của anh rr

Đội mình sẽ train lại với đề này sau khi có full đề + test trên mạng. Hi vọng có bạn khác vào nói solution :3

Hôm qua trong lúc các team thi thì em phải ngồi nhà hóng scoreboard, chán quá :(

Anw, sol bài C của em:

Phát biểu lại bài toán: cho số \(N\), tìm cách phân tích \(N\) thành tổng các số nguyên dương \(a_1, a_2, ..., a_k\) sao cho \(LCM(a_1, a_2, ..., a_k)\)là lớn nhất.

Giả sử bộ \(a_1, a_2, ..., a_k\)là tối ưu, ta có một vài nhận xét nho nhỏ:

i) \(GCD(a_i, a_j) = 1\) với \(\forall i \neq j\). Chứng minh: giả sử tồn tại \(i, j\) sao cho \(GCD(a_i, a_j) > 1\), ta sẽ thay 2 số \(a_i, a_j\) thành \((a_i / d, a_j / d, 1, 1, ..., 1)\)với \(d = GCD(a_i, a_j)\) mà không làm thay đổi kết quả.

ii) \(a_i = 1\) hoặc \(a_i = {p_i} ^ {q_i}\) với mọi i. Chứng minh: giả sử \(a_i = {p_1} ^ {q_1} + {p_2} ^ {q_2} + ... + {p_k} ^ {q_k}, k > 1\)thì ta có thể thay \(a_i\) thành các số \({p_i} ^ {q_i}\) và các số 1.

Túm lại, ta sẽ phân tích N thành tổng các số \({p_i} ^ {q_i}\) và các số 1.

Đến đây, ta có hàm QHĐ \(f(i, j)\) là cách phân tích số i như trên, chỉ sử dụng j số nguyên tố đầu tiên. Công thức:

\(f(i, 0) = 1\) với \(i \ge 0\)

\(f(i, j) = max(f(i, j-1), max \{f(i-{p_j}^q, j-1) * {p_j}^q\})\)với \(i \geq {p_j} ^ q\)

Độ phức tạp của thuật toán là \(O(N * \pi(N))\) với \(\pi(N)\) là số các số nguyên tố \(\le N\), bộ nhớ là \(O(N)\) do ta chỉ tính \(f(i,j)\) theo \(f(i',j-1)\)

Tuy nhiên, vì kết quả có thể rất lớn nên ngoài hàm \(f\) ta sẽ tính thêm hàm \(g(i, j) = log_{10}(f(i,j))\). Bộ nhớ vẫn là \(O(N)\)

Thuật toán này chạy rất lâu do số phép tính lớn + xử lý số thực. Tuy nhiên qua khảo sát, mình nhận thấy khi \(j \ge 195\) (\(p_j \ge 1187\)) thì \(f(i,j) = f(i,j-1)\) với mọi i. Do đó, ta chỉ cần for 195 số nguyên tố đầu tiên nên độ phức tạp sẽ tầm \(O(N*195)\). Code chạy hết 1s trên máy ideone: https://ideone.com/NsWmMI

Hôm qua trong lúc các team thi thì em phải ngồi nhà hóng scoreboard, chán quá :(

Anw, sol bài C của em:

Phát biểu lại bài toán: cho số \(N\), tìm cách phân tích \(N\) thành tổng các số nguyên dương \(a_1, a_2, ..., a_k\) sao cho \(LCM(a_1, a_2, ..., a_k)\)là lớn nhất.

Giả sử bộ \(a_1, a_2, ..., a_k\)là tối ưu, ta có một vài nhận xét nho nhỏ:

i) \(GCD(a_i, a_j) = 1\) với \(\forall i \neq j\). Chứng minh: giả sử tồn tại \(i, j\) sao cho \(GCD(a_i, a_j) > 1\), ta sẽ thay 2 số \(a_i, a_j\) thành \((a_i / d, a_j / d, 1, 1, ..., 1)\)với \(d = GCD(a_i, a_j)\) mà không làm thay đổi kết quả.

ii) \(a_i = 1\) hoặc \(a_i = {p_i} ^ {q_i}\) với mọi i. Chứng minh: giả sử \(a_i = {p_1} ^ {q_1} + {p_2} ^ {q_2} + ... + {p_k} ^ {q_k}, k > 1\)thì ta có thể thay \(a_i\) thành các số \({p_i} ^ {q_i}\) và các số 1.

Túm lại, ta sẽ phân tích N thành tổng các số \({p_i} ^ {q_i}\) và các số 1.

Đến đây, ta có hàm QHĐ \(f(i, j)\) là cách phân tích số i như trên, chỉ sử dụng j số nguyên tố đầu tiên. Công thức:

\(f(i, 0) = 1\) với \(i \ge 0\)

\(f(i, j) = max(f(i, j-1), max \{f(i-{p_j}^q, j-1) * {p_j}^q\})\)với \(i \geq {p_j} ^ q\)

Độ phức tạp của thuật toán là \(O(N * \pi(N))\) với \(\pi(N)\) là số các số nguyên tố \(\le N\), bộ nhớ là \(O(N)\) do ta chỉ tính \(f(i,j)\) theo \(f(i',j-1)\)

Tuy nhiên, vì kết quả có thể rất lớn nên ngoài hàm \(f\) ta sẽ tính thêm hàm \(g(i, j) = log_{10}(f(i,j))\). Bộ nhớ vẫn là \(O(N)\)

Thuật toán này chạy rất lâu do số phép tính lớn + xử lý số thực. Tuy nhiên qua khảo sát, mình nhận thấy khi \(j \ge 195\) (\(p_j \ge 1187\)) thì \(f(i,j) = f(i,j-1)\) với mọi i. Do đó, ta chỉ cần for 195 số nguyên tố đầu tiên nên độ phức tạp sẽ tầm \(O(N*195)\). Code chạy hết 1s trên máy ideone: https://ideone.com/NsWmMI

Bài CTNOWN trên spoj mà ??

http://vn.spoj.com/problems/CTNOWN/

Nốt bài L:

Bài này ta cần xét 2 trường hợp:

TH1: \(R \ge D\)

Giả sử góc tạo bởi cái que và đường ngang được cố định là \(\alpha\) (\(0 \le \alpha \le \pi\)) thì xác suất để que chạm vào đường ngang là \(\frac {D} {R} sin \alpha\). Do vậy, xác suất để cái que chạm vào một đường ngang là:

\(\frac {1} {\pi} \int _{\alpha=0} ^ \pi \frac{D}{R}\sin \alpha d \alpha\)

\(= \frac{D}{\pi R} \int _{ \alpha = 0}^{\pi} \sin \alpha d\alpha\)

\(= \frac{2D}{\pi R}\)

Vì \(R \ge D\) nên cái que chỉ có thể chạm được nhiều nhất 1 đường thẳng, do đó giá trị kì vọng cũng là \(\frac {2D} {\pi R}\).

TH2: \(R < D\)

Lúc này, công thức ở trên sẽ rất phức tạp do phải lấy \(\min(\frac{D}{R}sin\alpha, 1)\). Do đó, thay vì fix góc ta sẽ fix tọa độ rơi trước.

Giả sử đầu mút nằm bên trái của cái que cách một khoảng bằng \(x\)so với đường thẳng nằm ngay dưới (\(R-x\) so với đường thẳng nằm ngay trên), thì để chạm vào một trong 2 đường thẳng, góc \(\alpha\) tạo bởi que và đường dọc phải thỏa mãn \(0 \le \alpha \le \cos^{-1}\frac{x}{D}\) hoặc \(\cos^{-1}\frac{R-x}{D} \le \alpha \le \pi\). Do đó, xác suất sẽ là:

\(P = \int_{x=0}^{R} \frac{\cos^{-1}\frac{x}{D}+\cos^{-1}\frac{R-x}{D}}{\pi R}dx\)

\(= \frac{2D}{\pi R} \int_{x=0}^{\frac{R}{D}} {\cos^{-1}x} dx\)

Đặt \(t = \frac{R}{D}\) ta có:

\(P = \frac{2}{\pi t} \int_{x=0}^{t}\cos^{-1}xdx\)

\(= \frac{2}{\pi t} (t\cos^{-1}t - \sqrt{1-t^2}+1)\)

Phần tính GTKV, em khá chắc nó vẫn là \(\frac{2D}{\pi R}\), nhưng chưa chứng minh được :(