Vậy là 1 kì Contest nữa lại trôi qua, có vẻ Contest lần này gặp khá nhiều vấn đề, đó là do Ami không tham gia viết đề, mong các bạn thông cảm. Sau Contest lần này, các bạn có muốn mình giữ nguyên mức độ ra đề này không ? Và việc Random độ khó mang đến cho các bạn cảm giác thế nào ? Hãy đóng góp ý kiến dưới phần comment. Dù sao mình cũng khá vui, vì các bạn không A/C quá nhanh 4 bài nữa.
Top 5 Contest 10
1) L9 malego
2) L9CaoThuNoSeo
3) L9QuangLD
4) cbl_huynhtiendung
5) a518xuanhieu2611
Bạn A/C từng bài nhanh nhất
A L9 malego
B cbl_huynhtiendung
C
F
G cbl_huynhtiendung
Xin chúc mừng bạn cbl_huynhtiendung là người duy nhất ac bài B, và bạn L6NhatQuangNguyenKhuyen là học sinh lớp 6 thuộc top 10 kì thi.
Sau đây là editorial của Contest.
A - GAME
Thuật toán bài này rất đơn giản. Sau khi vét cạn 1 vài test, các bạn sẽ nhận ra, Duy chỉ thắng khi số sỏi chia 8 dư 1. Để chứng minh điều này, chúng ta có thể quy nạp như sau : Rõ rằng nếu số viên sỏi từ 2 à 7 thì Tuấn là người thắng cuộc và số viên sỏi là 1 thì Duy là người thắng cuộc. Giả sử nếu rằng điều này là đúng với n viên sỏi. Vậy với n + 1 viên sỏi sẽ có 2 trường hợp xảy ra :
*Số viên sỏi chia 8 dư 1. Lúc này, Tuấn đi trước, bốc từ 1 à 7 viên sỏi thì số viên sỏi còn lại sẽ không thể chia 8 dư 1 nữa. Sau đó Duy bốc số viên sỏi còn lại và Duy thắng.
*Số viên sỏi chia 8 không dư 1. Lúc này, Tuấn đi trước và bốc số sỏi sao cho các viên sỏi còn lại chia 8 dư 1. Sau đó, Duy sẽ bốc trước trong đống sỏi chia 8 dư 1 và Tuấn thắng.
Vậy các bạn chỉ cần kiểm tra số sỏi chia 8 có dư 1 không và in kết quả.
B - Đếm số không
Lưu ý rằng, số chữ số không tận cùng của 1 số tự nhiên N sẽ là min(cnt2 , cnt5). Với cnt2 chính là số mũ thừa số 2 và cnt5 là số mũ thừa số 5 khi phân tích N thành thừa số nguyên tố.
Vậy, ta có thuật toán sau, với mỗi số Bi, ta kiểm tra xem số đó chia hết cho bao nhiêu số 2 và số 5. Với mỗi số mũ của 2 ta sẽ đánh dấu lại và cập nhật max của mũ 2 này bằng mũ 5. Vì tất nhiên nếu 2 số phân tích ra thừa số nguyên tố có cùng số mũ 2, ta sẽ ưu tiên số có số mũ 5 lớn hơn. Từ đây, ta có thể duyệt trâu tất cả mũ 2, với mỗi mũ 2, ta sẽ có mũ 5 lớn nhất tương ứng và hoàn toàn có thể tính được tổng số 0 tận cùng của dãy A.
Độ phức tạp O(N * log2(1015)).
C - Đếm cặp
Số cặp I,J mà abs(ai – aj) > 1 sẽ bằng tất cả các cặp I,J trừ khi các cặp I,J mà abs(ai – aj) <= 1.
Đầu tiên là thuật toán vét cạn, rõ ràng ta có thể dùng 2 vòng lặp, cố định cận trái và for cận phải. Mỗi lần duyệt cận phải, ta hoàn toàn có thể tính được số cặp I,J mà abs(ai – aj) <= 1 hiện tại. Và ta có thể tính được kết quả dễ dàng.
Để giải quyết bài toàn trong giới hạn thời gian cho phép, ta sẽ dùng thuật toán phân rã căn bậc 2 (Mo's Algorithm) – một loại hình chia để trị khá phổ biến trong lập trình thi đấu. Đầu tiên, các bạn chia dãy số này thành căn bậc 2 đoạn liên tiếp gọi là block. Vậy các số từ 1 à sqrt(n) sẽ thuộc block1, từ sqrt(n)+1 à 2*sqrt(n) thuộc block 2…… và sẽ có sqrt(n) block. Chúng ta sẽ sort lại các truy vấn theo block mà cận trái của truy vấn đó thuộc về. Nếu trùng block, ta sắp xếp tăng dần theo cận phải.
Sau khi sắp xếp như thế, ta sẽ duyệt hết tất cả block. Mỗi block ta sẽ duyệt tất cả phần tử thuộc block có thứ tự lớn hơn block ta đang duyệt. Giả sử ta đang duyệt block i và e là phần tử nhỏ nhất thuộc block i. Gọi các truy vấn có cận trái thuộc block i là truy vấn tốt. Trong lúc duyệt, nếu ta gặp 1 cận phải của 1 truy vấn tốt, ta sẽ tăng hoặc giảm e sao cho cận trái của truy vấn này trùng với e. Mỗi lần tăng, giảm như thế, ta hoàn toàn tính được số cặp I,J mà abs(ai – aj) <= 1 từ đó tính ra kết quả dễ dàng. Và mỗi lần giảm, tăng, ta sẽ không làm quá sqrt(n) phép tính.
Độ phức tạp O(N * sqrt(N)).
D - Xây Nhà
Đây là một bài tường minh, các bạn chỉ cần chú ý vào cài đặt thôi.
E - CaiWinDao và 3 em gái
Bài này có nhiều cách giải, nhưng mình sẽ trình bày cách làm quy hoạch động.
Gọi F[i][j] là số viên kẹo nhiều nhất mà chỉ xét i bao kẹo ban đầu và số viên kẹo đó chia 3 dư f (-1 < f < 3).
Vậy ta sẽ có cách chuyển đổi trạng thái như sau
F[i][j] = F[i-1][j]
F[i][j] = F[i-1][x] + a[i] (với (x + a[i]) mod 3 = j) ,-1 < x < 3)
Kết quả bài toán sẽ là F[n][0] / 3.
Đô phức tạp O(3 * N) hoặc O(9 * N).
F - INTERSECT
Xét hình chữ nhật thứ i ta có: tọa độ của góc trái dưới (x1, y1) và góc phải trên (x2, y2)
=> tọa độ của góc trái trên (x1, y2) và góc phải dưới (x2, y1)
Với mỗi hình ta quan tâm đến 2 cạnh L và R là 2 cạnh dọc của hình được giớ hạn bởi 2 cặp điểm lần lượt là [(x1, y1); (x1, y2)] và [(x2, y1); (x2, y2)].
Tiếp theo, ta sắp các cạnh hình chữ nhật lại theo x. Ta có a[y] thể hiện số đoạn thẳng đang có chưa điểm (x, y) tại thời điểm đang xét. Với mỗi hình chữ nhật i ta thực hiện lần lượt các thao tác:
+ Nếu cạnh đang xét là cạnh L thì ta thực hiện tăng giá trị của ô a[y2 – 1] và ô a[y1 + 1] lên 1 đơn vị
+ Nếu cạnh đang xét là cạnh R thì ta thực thiệt giảm giá trị của ô a[y2 – 1] và ô a[y1 + 1] xuống 1 đơn vị. Sau đó, ta kiểm tra xem trong đoạn [y1 + 1, y2 - 1] có chứa ô nào có giá trị >= 1 không nếu có thì chính là 2 hình chữ nhật cắt nhau. Ta có thể làm bằng cách tính tổng các ô ai trên đoạn [y1 + 1, y2 – 1].
để update nhanh trên các giá trị và tính tổng trên đoạn nhanh ta có thể sử dụng các cấu trúc dữ liệu như segment tree hoặc là BIT(fenwick tree)
Độ phức tạp O(N * log2(N)).
G - Số phú quý
Thuật toán bài này thì đã quá rõ ràng rồi ta chỉ cần đổi từ hệ tam phân sang hệ thập phân.
Độ phức tạp O(18).
