EDITORIAL CONTEST 8

a516ami_crush_tuyetni - 21/02/2019

BÀI A :

Bài này có thuật toán khá tường minh. Các bạn có thể kiểm tra xem, nếu 3 bạn ra cùng một số hoặc ra 3 số khác nhau thì in ra 0, ngược lại in ra 1.

BÀI B :

            Thực chất kết quả của bài toán này chính là max của dãy số, do đó có thể làm được với n <= 106. Vì sao là max của dãy số ? Vì rõ rang trung bình cộng của dãy số dù có làm tròn hay không thì luôn <= max của dãy số đó.

            Thuật toán O(n2) : Các bạn có thể for tất cả các đoạn con của dãy số, với mỗi đoạn như thế các bạn có thể tính tổng và số lượng số hạng trong đoạn. Từ đó dễ dàng tính được trung bình cộng tất cả các đoạn con.

 

BÀI C :

            Đây là một bài toán khá kinh điển và cơ bản. Nếu một dãy số mà số sau trừ số trước bằng k thì số phần tử của sẽ bằng (số cuối – số đầu) / k + 1.

            Áp dụng vào bài toán này, ta sẽ có công thức (n – k) / k + 1. Chỉ cần để ý trường hợp nếu n < k thì in ra 0.

 

BÀI D :

            Bài này bọn mình ra hi vọng giết được những thuật toán O(n * logn) nhưng nghĩ lại vì mục đích kì thi là để luyện code nhứ không phải để các bạn tạch hết nên những thuật O(n * logn) vẫn qua được thời gian.

            Bài này có nhiều cách giải, nhưng mình sẽ trình bày cách giải đơn giản nhất (không phải ngắn nhất). Đó là chặt nhị phân. Vì dãy đã được sắp xếp, với một phần tử ai, các bạn tính ra số x = k – ai. Sau đó tìm vị trí j lớn nhất < i mà aj = x và vị trí k nhỏ nhất < i mà ak = x. Và thêm j - k + 1 vào kết quả cuối cùng.

            Để làm được thuật O(n) cho bài này các bạn có thể dùng thuật truy đuổi (2-pointer).

 

BÀI E :

            Bài này mình nghĩ không phải bài dễ nhưng nếu tinh ý các bạn vẫn có thể giải ra dễ dàng, nên được xếp là bài E.

            Trước hết, hãy nhìn vào thuật toán vét cạn :

                        A := a mod b;

                        For i := 1 to k-1 do a = a * 10 mod b;

                        Writeln(A *10 div b);

            Thuật toán vét cạn trên tương đương với biểu thức

a mod b * 10 mod b * 10 mod b *….. = a mod b * 10k-1 mod b * 10 div b;

            Để tính 10k-1 mod b với số mũ lớn như thế, các bạn cần thuật toán chia để trị sau :

                        int bigmod(int mu , int co_so , int mod)

                        {

                                    If (mu == 0) return 1;

                                    Int k = bigmod(mu / 2 , co_so , mod);

                                    If (mu % 2 == 0) return k * k % mod;

                                    Return k * k % mod * co_so % mod;

                        }

            Nếu bị WA, các bạn hãy chú ý số k có thể lên đến 1016, vi vậy việc nhân 2 số k lại với nhau sẽ gây tràn số, để khắc phục chuyện này, các bạn có thể viết hàm nhân 2 số tương tự như hàm tính mũ trên :

                        Int multiply(int a , int b , int mod)

                        {

                                    If (b == 0) return 0;

                                    Int k = multiply(a , b / 2 , mod);

                                    If (b % 2 == 0) return k * 2 % mod;

                                    Return (k * 2 % mod + a) % mod;

                        }

            Đây là kĩ thuật cực kì thông dụng trong lập trình thi đấu.

 

BÀI F :

            Bài này là một bài rất hay và khéo léo do Thánh Ngốc biên soạn. Đầu tiên, biểu thức để tính số vỏ kẹo và cây kẹo mà Tuấn có sau khi mua a cây kẹo :

            T = a/30 + a/31 + a/32 + …. + a/3log3(n).

            Nếu gọi x là số mũ 3 khi phân tích a! thành thừa số nguyên tố thì số kẹo và vỏ Tuấn còn lại là T – x.

            Làm sao để tính được khi phân thích thừa số nguyên tố thì a! chứa bao nhiêu thừa số 3 ? Ta có công thức sau :

            X = a/31 + a/32 + …. + a/3log3(n).

            Vậy là xong, công thức vi diệu đã xuất hiện, T – x = a / 1 = a. Vậy ta chỉ cần chọn cách mua làm sao mà a là lớn nhất, chính là bằng số tiền của Tuấn chia cho giá tiền cây kẹo ít nhất.

            CM công thức số mũ giai thừa, các bạn có thể dùng bao hàm loại trừ (inclusive – exclusive) nhưng mình sẽ để dành nó cho bài G :D.

 

BÀI G :

*MAY QUÁ KHÔNG AI GIẢI RA BÀI NÀY

            Trước hết, mình hi vọng không ai A/C để Ami được vui mừng :D.

            Với những bài tìm số lớn thứ c của một dãy số như thế này, các bạn có thể dùng thuật toán chặt nhị phân.

            Gọi x là kết quả của bài toán và hàm D(t) là số các số tự nhiên y thỏa mãn :

                        *y <= t

                        *GCD(y , b) = 1.

            Vậy D(x) – D(a) = c và x là nhỏ nhất có thể.

            Ta có thể tính sẵn P = D(a). Ta chặt nhị phân số x, và tính hàm D(x). Nếu D(x) – P >= c, ta sẽ lưu lại kết quả và giảm cận phải lại, ngược lại ta lại tăng cận trái :

            Int phải = 109 , trái = 1 ;

            While (phải >= trái)

            {

                        Int x = (phải + trái) / 2 ;

                        If (D(x) – P >= c) result = x , phải = x – 1 ;

                        Else trái = x + 1;

            }

           

            Rõ ràng sau hàm chặt nhị phân này, ta sẽ tìm được kết quả. Vấn đề cuối cùng là làm sao để tính được D(x) trong thời gian cho phép ? Ở đây mình sẽ dùng lí thuyết bao hàm loại trừ.

            Giả sử số x có P1,P2,P3,…,PK là các ước số nguyên tố. Từ các ước nguyên tố, ta có thể sinh ra tất cả các số S1,S2,…,SG với Si được tạo ra bằng tích của một hay nhiều số Pi và mỗi số Pi chỉ được dùng tối đa một lần. Vậy ta dãy S sẽ có khoảng 2n số. Từ đó, số các số nguyên tố cùng nhau với x và nhỏ hơn x sẽ bằng x + quan với :

  • quan -= x / Si   nếu Si là tích của lẻ số trong dãy P.
  • quan += x / Si nếu Si là tích của chẵn số trong dãy P.

Với mọi Si có thể tạo ra từ dãy P, ta sẽ tính quan theo công thức trên.

Nhận thấy rằng một số nguyên n sẽ không có quá 2 * sqrt(n) ước, vì vậy độ phức tạp

Cho mỗi query tối đa sẽ là O(log(n) * sqrt(n)).

            Credit :

Bài này là một bài trên Codeforces.

Cảm ơn anh CaiWinDao đã phổ cập cho mình lí thuyết bao hàm loại trừ.

 

CÁC PHẢN HỒI

  • L9QuangLD - 21/02/19 21:45
    Anh chu đáo quá =))
  • a516ami_crush_tuyetni - 21/02/19 22:01
    cảm ơn bạn, solution là bắt buộc của contest mà, từ h những contest nào ít nhất do mình tổ chức đều có sol cả, nếu các bạn cần hỏi gì cứ comment mình sẽ trả lời nhé
  • L9QuangLD - 21/02/19 22:35
    OH NO!!! Chủ nhật có Free Contest r anh ơi.
  • a516ami_crush_tuyetni - 21/02/19 22:47
    Bạn muốn tham gia một kì thi chỉ có 4 bài, và chưa chắc độ khó đã phù hợp với các bạn, có thể không có solution chỉ có code, hay 1 kì thi có 7 bài, mức độ khó được điều chỉnh để phù hợp các bạn và có solution chỉ sau 1 --> 2 tiếng ? Tùy các bạn thôi
  • L9CaoThuNoSeo - 21/02/19 22:53
    em thấy anh làm thế này là hay quá rồi. chỉ tiếc là không tham gia đc. khi nào anh lại tổ chức ạ?
  • a516ami_crush_tuyetni - 21/02/19 23:02
    sau chủ nhật thì khoảng 1 2 tuần sau mình mới định viết tiếp nên các bạn cố gắng tham gia nhé
  • L7haidang07 - 22/02/19 08:24
    Chủ nhật contest tổ chức mấy giờ vậy anh?
  • L9zipdang2004 - 22/02/19 21:02
    Cho e xin info bài G ạ =))) e tò mò quá =))
  • CaiWinDao - 22/02/19 21:48
    Vinh dự khi được master Ami mentioned trong bài viết :)))
  • L9CaoThuNoSeo - 23/02/19 22:39
    zip: đúng rồi đó. bài A div 3 mà áp dụng chặt nhị phân + số học thì hơi khủng đó
  • L9CaoThuNoSeo - 23/02/19 22:40
    nếu div 3 thì nó ít nhất phải là bài C => ami đã troll chúng ta và đó là bài A div 1? that's cú lừa! cuộc sống mà!
Back to Top