Xin chào các thành viên của CLAOJ. Nhân dịp tết Trung thu đã cận kề, chúng mình đã quay trở lại với CLAOJ Mid Autumn Contest (Regular Contest 7). CLAOJ Mid Autumn Contest hứa hẹn sẽ là một sân chơi lập trình bổ ích và thú vị, với những bài tập vô cùng chất lượng đến từ ban chuyên môn của CLAOJ. Đặc biệt, các bạn đạt thành tích tốt trong kì thi này sẽ nhận được phần thưởng từ ban tổ chức (cụ thể bên dưới).

Một số thông tin về kì thi:

• Ban ra đề: DangHung845, kieuphat159, hoangphat120805, bachminhkhang, lds.
• Thời gian: ~20:00 - 22:30~ Thứ bảy, ngày ~30~ tháng ~9~ năm ~2023~.
• Thời lượng: ~2~ tiếng ~30~ phút.
• Lượng bài tập: ~5~ bài.
• Kì thi sẽ được tính rating cho tất cả thành viên của trang web.
• Cơ cấu giải thưởng:
  • Top ~1~: ~200\, 000~ đồng
  • Top ~2~: ~100\, 000~ đồng
  • Top ~3~: ~50\, 000~ đồng
  • Giải may mắn dành cho ~2~ thí sinh ngẫu nhiên không thuộc top ~3~ và có số điểm ~ > 0~: ~50\, 000~ đồng Hình thức phát thưởng: chuyển khoản ngân hàng hoặc Momo.

Lưu ý: Các thí sinh tham gia với tinh thần học hỏi và giao lưu, vui lòng không tạo nhiều acc clone để tham gia kì thi. Các hành vi chép code, gian lận dưới mọi hình thức sẽ bị loại khỏi kì thi và cấm tài khoản khỏi trang web.

UPD: Vậy là CLAOJ Regular Contest 7 đã khép lại sau ~150~ phút diễn ra vô cùng kịch tính. CLAOJ xin chúc mừng tất cả các bạn thí sinh đã hoàn thành bài thi của mình.

Xin chúc mừng ~3~ bạn:

1. ti21_phnam: ~500~ điểm
2. tkhoi: ~480~ điểm
3. sangph2612: ~460~ điểm

đã xuất sắc dành vị trí nhất, nhì, ba. Ngoài ra, chúng mình còn có ~2~ giải may mắn dành cho ~2~ bạn thí sinh tham gia contest nhưng không nằm trong top ~3~ và có số điểm lớn hơn ~0~. Xin chúc mừng ~2~ bạn:

• votansach2008
• naniore

Các bạn hãy dùng mail đã đăng kí trên trang và gửi thông tin chuyển khoản (ngân hàng hoặc momo) đến địa chỉ [email protected] để nhận thưởng nhé.

💖 Chúng mình xin gửi lời cảm ơn đến anh bachtam2001 đã hỗ trợ server và trình chấm ổn định để contest diễn ra thành công.

📬 Xin mời các bạn đánh giá kì thi qua form này để chúng mình có thể cải thiện chất lượng cho các kì thi sau: https://forms.gle/EN5Z6ckbFSxPdjmF8

🌟 Ngoài ra, các bạn có thể thảo luận về kì thi này ở server discord của chúng mình: https://discord.gg/VYQqA7yy

🫶 Cảm ơn các bạn đã quan tâm và nỗ lực hoàn thành kì thi. Hẹn gặp lại các bạn ở các kì thi tiếp theo.

Happy coding, CLAOJ.

Vào ngày ~16 - 17/9~ vừa qua, kì thi HSG tỉnh vòng ~2~ đã diễn ra vô cùng căng thẳng với ~36~ thí sinh đến từ các trường THPT trên khắp địa bàn tỉnh Long An. Sau nhiều ngày chờ đợi, kết quả của kì thi HSG tỉnh cũng đã được hé lộ. Team IT-CLA xin chúc mừng tất cả các bạn đã hoàn thành kì thi này.

Top ~6~ dự kiến của kì thi gồm có:

1. Lê Thành Đạt (lds)
2. Phạm Thanh Sang (sangph2612)
3. Võ Trần Ngọc Vy (votranngocvy)
4. Lương Huỳnh Gia Bảo (BvoJa)
5. Nguyễn Huỳnh Huy Phát (HPhat)
6. Hàng Lê Gia Bảo (ily1903)

Ngoài ra, chúng mình còn tổng hợp được rating trên CLAOJ của các bạn thí sinh xuất sắc nằm trong top 10 kì thi HSG tỉnh Long An như sau:

1. Lê Thành Đạt (lds): 1419
2. Phạm Thanh Sang (sangph2612): 2036
3. Võ Trần Ngọc Vy (votranngocvy): 1990
4. Lương Huỳnh Gia Bảo (BvoJa): 1451
5. Nguyễn Huỳnh Huy Phát (HPhat): 1770
6. Hàng Lê Gia Bảo (ily1903): 1836
7. Nguyễn Thanh Bình
8. Phạm Minh Quang (JackTor_Guy): 1781
9. Cao Thái Bảo (baonguyen): 1487
10. Phan Minh Anh (Solitude_shu): 1590

Một lần nữa, team IT-CLA xin được chúc mừng các bạn đã đạt được kết quả cao trong kì thi HSG tỉnh năm ~2023~. Hãy cùng chờ đợi 6 gương mặt xuất sắc nhất tỉnh sẽ bước vào kì thi chọn Học sinh giỏi Quốc gia năm ~2023~ vào tháng ~12~ sắp tới.

Số nguyên tố là số rất thường xuất hiện trong các bài toán học và tin học. Trong bài viết này, chúng mình sẽ giúp các bạn hiểu được bản chất của số nguyên tố và kiểm tra xem một số bất kì có phải là số nguyên tố hay không bằng các phương pháp cơ bản và phổ biến nhất. Qua đó các bạn có thể giải quyết hiệu quả các bài tập liên quan đến số nguyên tố.

1. Khái niệm

Số nguyên tố (Prime number) là số tự nhiên lớn hơn $1$ chỉ có đúng hai ước số là $1$ và chính nó. Ví dụ: $2, 3, 5, 7, 11, 13, 17,$ ... là những số nguyên tố.

Hợp số (Composite number) là số tự nhiên lớn hơn $1$ và có nhiều hơn $2$ ước. Ví dụ: $4, 9, 15, 27, 111,$ ... là những hợp số.

2. Cài đặt

Đề bài: Xét một số nguyên dương $N$ xem số đó có phải là số nguyên tố hay không.

2.1 Cài đặt ngây thơ

Nhận xét

Ta dựa vào tính chất đã nêu trên để xét. Cụ thể, ta thử chia hết $N$ cho các số từ $2$ đến $N- 1$ để tìm các ước, nếu có $1$ ước trở lên thì $N$ không phải là số nguyên tố.

Code mẫu

    bool isPrime(int n) {
        for(int i = 2; i < n; i++) { 
            if(n % i == 0) {        // nếu tìm được một ước thì nó không là số nguyên tố
                return 0;
            }
        }
        return n > 1;
    }

Độ phức tạp

Độ phức tạp thời gian: $\mathcal{O}(n)$

Độ phức tạp không gian: $\mathcal{O}(1)$

2.2 Cải tiến

Nhận xét

Ta nhận thấy rằng nếu $N$ không phải là số nguyên tố, $N$ có dạng $N=A \cdot B$ và hiển nhiên $A,B$ không thể cùng lớn hơn $\sqrt{N}$ vì nếu như vậy thì $A \cdot B > \sqrt{N} \cdot \sqrt{N}=N$. Vậy nên trong các ước số của $N$ thì ít nhất một trong các ước sẽ nhỏ hơn $\sqrt{N}$. Tóm lại, ta chỉ cần xét từ $2$ đến $\sqrt{N}$, nếu có ước trong đoạn này thì $N$ không phải là số nguyên tố .

Code mẫu

    bool isPrime(long long n) {
        for(int i = 2; i * i <= n; i++) { // chạy đến căn của n
            if(n % i == 0) {              // nếu tìm được một ước thì nó không là số nguyên tố        
                return 0;                   
            }
        }
        return n > 1;
    }

Độ phức tạp

Độ phức tạp thời gian: $\mathcal{O}(\sqrt{n})$

Độ phức tạp không gian: $\mathcal{O}(1)$

3. Sàng Eratosthenes (Sieve of Eratosthenes)

3.1 Khái niệm

Sàng Eratosthenes dùng để tìm các số nguyên tố nhỏ hơn hoặc bằng số nguyên $N$ nào đó.

Nguyên lí hoạt động của sàng là vào mỗi lần duyệt, ta chọn một số nguyên tố và loại ra khỏi sàng tất cả các bội của số nguyên tố đó mà lớn hơn số đó. Sau khi duyệt xong, các số còn lại trong sàng đều là số nguyên tố.

3.2 Code mẫu

vector <bool> prime(n + 1, true);             // khởi tạo mảng prime với giá trị true

for (int i = 2; i * i <= n; i++) {
    if (prime[i] == true) {                   // nếu i là số nguyên tố
        for (int j = i * i; j <= n; j += i) {   // thì loại bỏ các số là bội của i
            prime[j] = false;
        }
    } 
}

Độ phức tạp

Độ phức tạp thời gian: $\mathcal{O}(n\log{n})$

Độ phức tạp không gian: $\mathcal{O}(n)$

Ứng dụng

Sàng Eratosthenes rất hữu dụng cho các bài tìm số nguyên tố nhiều truy vấn vì khi khởi tạo xong chỉ tốn $\mathcal{O}(1)$ cho từng lần kiểm tra.

Kết hợp với mảng cộng dồn ta có thể dễ dàng tính được số lượng số nguyên tố trên đoạn $l$ đến $r$.

4. Tìm hiểu thêm

• Thuật toán Miller - Rabin
• Phép thử Fermat

5. Bài tập làm thêm

• VL11 - Kiểm tra số nguyên tố
• Đếm số lượng nguyên tố
• Số nguyên tố đặc biệt
• Số nguyên tố ghép

Nguồn tham khảo

• Kiểm tra số nguyên tố
• Số học 2 - Số nguyên tố, Sàng Eratosthenes

Xin chào các thành viên của CLAOJ, chúng mình đã quay trở lại với CLAOJ Beginner Contest 3. Đây là contest nằm trong chuỗi kì thi hướng đến các bạn học sinh cấp ~2~ hay các bạn vừa nhập môn Lập trình thi đấu. Với các bài tập chất lượng, CLAOJ Beginner Contest 3 sẽ là một sân chơi lập trình thú vị và bổ ích dành cho các bạn thí sinh.

Link contest: claoj.edu.vn/contest/claojbc3

Một số thông tin về kì thi:

• Ban ra đề: dinhwe2612, kieuphat159, hoangphat120805, bachminhkhang, lds.
• Thời gian: ~20:00 - 22:00~ Chủ nhật, ngày ~27~ tháng ~8~ năm ~2023~.
• Thời lượng: ~2~ tiếng.
• Lượng bài tập: ~4~ bài.
• Kì thi sẽ có tính rating cho các thành viên có rating dưới 1600 (từ Specialist trở xuống).

Lưu ý: Các hành vi chép code, gian lận dưới mọi hình thức sẽ bị loại khỏi kì thi và cấm tài khoản khỏi trang web.

UPD: Vậy là sau hơn 120 phút, CLAOJ Beginner Contest 3 đã khép lại đầy kịch tính. Xin chúc mừng tất cả các thí sinh tham gia đã hoàn thành bài thi của mình.

Xin chúc mừng ba bạn

• tkhoi - ~400~
• nhamtan - ~400~
• MinhHieu_LTT - ~400~

Đã xuất sắc dành vị trí nhất, nhì và ba.

Các tài khoản có rating dưới 1600 đã được rated.

🖥Đáng tiếc, kì thi này xuất hiện hành vi chép code và tụi mình đã xử phạt bằng việc hủy kết quả thi và không tính rating cho các tài khoản vi phạm. Nếu có thắc mắc xin phản hồi đến chúng mình. Cụ thể ở đây:

l4adeveloper và lasdkjiasjduhu

l4adeveloper và lasdkjiasjduhu

dbthuan208 và ImBoo

Lưu ý: Trường hợp bị disqualify 3 lần sẽ bị BAN tài khoản vĩnh viễn.

Xin mời các bạn đánh giá kì thi qua form này để chúng mình có thể cải thiện chất lượng cho các kì thi sau: form

Đặc biệt chúng mình xin gửi lời cảm ơn đến anh bachtam2001 đã hỗ trợ server và trình chấm ổn định để contest diễn ra thành công.

Cảm ơn các bạn đã quan tâm và nỗ lực hoàn thành kì thi. Hẹn gặp lại các bạn ở các kì thi tiếp theo.

Happy coding, CLAOJ.

Xin chào các thành viên của CLAOJ, chúng mình đã quay trở lại với CLAOJ Regular Contest 6 rồi đây. CLAOJ Regular Contest 6 hứa hẹn sẽ là một sân chơi dành cho các bạn học sinh yêu thích lập trình thi đấu có thể luyện tập, trau dồi thêm những kiến thức bổ ích. Đặc biệt, các bạn đạt thành tích tốt trong kì thi này sẽ nhận được giải thưởng đến từ ban tổ chức (cụ thể bên dưới).

Link contest: claoj.edu.vn/contest/claojre6

Một số thông tin về kì thi:

• Ban ra đề: dinhwe2612, kieuphat159, bachminhkhang, lds, haruxne.
• Thời gian: ~20:00~ - ~22:30~ Chủ nhật, ngày ~13~ tháng ~8~ năm ~2023~.
• Thời lượng: ~2~ tiếng ~30~ phút.
• Lượng bài tập: ~5~ bài.
• Kì thi sẽ được tính rating cho tất cả thành viên của trang web.
• Cơ cấu giải thưởng:
  • Top ~1~: ~100 \ 000~ đồng
  • Top ~2~: ~60 \ 000~ đồng
  • Top ~3~: ~30 \ 000~ đồng

Hình thức phát thưởng: chuyển khoản ngân hàng hoặc Momo.

Lưu ý: Các hành vi chép code, gian lận dưới mọi hình thức sẽ bị loại khỏi kì thi và cấm tài khoản khỏi trang web.

Chúc các bạn có một kì thi vui vẻ và bổ ích!

Happy coding, CLAOJ.

1. Độ phức tạp thời gian của thuật toán

• Trong các cuộc thi lập trình, chương trình của bạn cần chạy xong trong một khung thời gian nhất định. Với quy ước hiện nay mỗi giây máy tính có thể tính được $10^8 - 5 \cdot 10^8$ phép tính. Vì vậy việc tối ưu phép tính trong việc giải các bài toán rất quan trọng trong lập trình thi đấu.
• Độ phức tạp thời gian là một khái niệm trong khoa học máy tính, là kết quả ước lượng thời gian thực hiện các chương trình cài đặt thuật toán để xử lí một lượng dữ liệu đầu vào có độ lớn $n$. Ước lượng này thể hiện số phép toán cần thiết để thực hiện thuật toán khi đã biết dữ liệu đầu vào có kích thước $n$.

🌻Ngăm và CLAOJ xin trân trọng cảm ơn sự hỗ trợ của anh Nguyễn Đức Thuận - một trong những cá nhân tiêu biểu trong cộng đồng lập trình thi đấu Việt Nam.

🌻Tính đến thời điểm hiện tại, cuộc thi Charity Coding Marathon “Đường đến La Ngâu” của Ngăm x CLAOJ đã được sự tham gia nhiệt liệt của các bạn. Chúng mình rất lấy làm biết ơn vì sự ủng hộ ấy. Chúng mình xin được phép cập nhật thêm một số thông tin về Phase ~2~ của cuộc thi:

🌻Link contest: https://claoj.edu.vn/contest/claoj_ngam

• Các bài tập trong đợt ~2~ của contest sẽ có độ khó cao hơn đợt ~1~.
• Nhằm để contest thêm phần kịch tính và hấp dẫn, chúng mình sẽ bổ sung bài mới theo từng ngày. Cụ thể:
  • Ngày thứ nhất ~(24/7)~ chúng mình sẽ đăng ~2~ bài.
  • Các ngày còn lại, mỗi ngày lúc ~8:00~ chúng mình sẽ đăng thêm ~1~ hoặc ~2~ bài tập cho đến hết ngày ~26/7~.
  • Các bài tiếp theo sẽ có số điểm ~> 100~.
• Cập nhật về việc góp quỹ: Mỗi bài nộp AC ứng với ~7.000~đ được góp vào quỹ Chuyến đi Nắng của Ngăm. Điều này cũng được áp dụng với các bài tập ở Phase ~1~. (~5.000~đ của CLAOJ và ~2.000~đ do anh Nguyễn Đức Thuận tài trợ).

🌻Xin chào các thành viên của CLAOJ. Nhận thấy sự cần thiết về việc giúp đỡ các em nhỏ trước thềm năm học mới cùng với sự hưởng ứng nhiệt tình của các thí sinh ở các kì thi trước, chúng mình đã quyết định tổ chức một kì thi hoàn toàn mới, thú vị và đầy ý nghĩa mang tên NGĂM X CLAOJ: CHARITY CODING MARATHON .🌻

Sứ mệnh đằng sau cuộc thi này không chỉ dừng lại ở việc thử thách và phát triển tài năng lập trình mà còn hướng tới mục tiêu cao cả hơn, đó là gây quỹ cho tổ chức thiện nguyện NGĂM để giúp đỡ các em học sinh đang sinh sống tại vùng núi xã La Ngâu, huyện Tánh Linh, tỉnh Bình Thuận.

🌻Với mỗi bài nộp AC (Đáp án đúng), CLAOJ sẽ góp ~5.000~ đồng vào quỹ Chuyến đi Nắng của NGĂM.🌻

Link contest: https://claoj.edu.vn/contest/claoj_ngam

Sau đây là một số thông tin về kì thi:

• Ban ra đề: BJMinhNhut, dinhwe2612, hoangphat120805, kieuphat159, bachminhkhang, lds, haruxne. Ban ra đề bao gồm thành viên đạt giải HSGQG, thành viên đạt giải Tin học trẻ khu vực & toàn quốc, thành viên đạt huy chương OLP ~30/4~, cựu đội tuyển HSGQG môn Tin học tỉnh Long An.
• Thời gian: ~8:00~ - Thứ ~6~, ngày ~21~ tháng ~7~ năm ~2023~
• Thời lượng: ~7~ ngày
• Lượng bài tập: ~10~ bài, chia làm hai đợt:
  • Đợt ~1~ ~(21/7)~ gồm ~5~ bài với độ khó dễ, trung bình.
  • Đợt ~2~ ~(24/7)~ gồm thêm ~5~ bài với độ khó trung bình, khó.
• Kì thi sẽ tính rating cho tất cả thí sinh tham gia
• Tổng số tiền quyên góp sẽ được công khai ngay sau khi kì thi kết thúc

Lưu ý: Các hành vi chép code, gian lận dưới mọi hình thức sẽ bị loại khỏi kì thi và cấm tài khoản khỏi trang web.

🌟Chúc các bạn có một kì thi vui vẻ và bổ ích! 💖

Happy coding, CLAOJ.

Xin chào các thành viên của CLAOJ. Sau một thời gian vắng bóng thì chúng mình đã trở lại cùng với CLAOJ Beginner Contest 2, tiếp nối CLAOJ Beginner Contest 1 đã nhận được sự tham gia nhiệt tình của các bạn. Contest này nằm trong chuỗi kì thi hướng tới đối tượng là các bạn học sinh cấp 2, hay các bạn mới nhập môn lập trình thi đấu. Đặc biệt, các bạn đạt thành tích tốt trong kì thi này sẽ nhận được phần thưởng từ ban tổ chức (cụ thể bên dưới).

Link contest: https://claoj.edu.vn/contest/claojbc2

Sau đây là một số thông tin về kì thi:

• Ban ra đề: dinhwe2612, hoangphat120805, kieuphat159, lds, haruxne.
• Thời gian: $19:30$ - $21:30$ Chủ nhật, ngày $16$ tháng $7$ năm $2023$.
• Thời lượng: $2$ tiếng.
• Lượng bài tập: $4$ bài.
• Kì thi sẽ có tính rating dành cho các bạn có rating dưới 1600 (từ Specialist trở xuống).
• Cơ cấu giải thưởng:
  • Top 1: $50\,000$ đồng
  • Top 2: $30\,000$ đồng
  • Top 3: $20\,000$ đồng
• Hình thức phát thưởng: chuyển khoản ngân hàng hoặc Momo.

Lưu ý: Các hành vi chép code, gian lận dưới mọi hình thức sẽ bị loại khỏi kì thi và cấm tài khoản khỏi trang web.

UPD: Kì thi đã kết thúc, chúng mình xin cảm ơn các bạn đã nhiệt tình tham gia kì thi. Chúng mình xin chúc mừng các bạn đã có thành tích tốt và nhận thưởng trong kì thi lần này:

1. HPhat - ~400~ điểm
2. JackTor_Guy - ~362~ điểm
3. minhanh - ~338~ điểm

Lưu ý: Bảng xếp hạng trên là top ~3~ các bạn có tất cả tài khoản rating dưới 1600 (từ Specialist trở xuống).

Các bạn HPhat, JackTor_Guy, minhanh hãy dùng mail đã đăng kí trên trang và gửi thông tin chuyển khoản (ngân hàng hoặc momo) đến địa chỉ [email protected] để nhận thưởng.

Đặc biệt chúng mình xin gửi lời cảm ơn đến anh bachtam2001 đã hỗ trợ server và trình chấm ổn định để contest diễn ra thành công.

Hẹn gặp lại các bạn ở những kì thi sắp tới!

Happy coding, CLAOJ.

1. Sử dụng thư viện bits/stdc++.h

• C++ có rất nhiều thư viện, để sử dụng các hàm hay cấu trúc dữ liệu ta cần phải khai báo thư viện chứa các cấu trúc dữ liệu/hàm tương ứng. Ví dụ:

#include <iostream>
#include <vector>
#include <set>
#include <string>
using namespace std;

int main(){
    cout << "Hello CLAOJ!";
    return 0;
}

• Trong đó:

  • Thư viện iostream được dùng cho các lệnh nhập - xuất trong C++.
  • Thư viện vector dùng cho các thao tác trên cấu trúc dữ liệu vector trong C++.
  • Và tương tự với các cấu trúc dữ liệu khác như string, set,...

• Để tránh việc phải khai báo quá nhiều thư viện khi code C++, ta có thể khai báo một thư viện duy nhất là bits/stdc++.h. Đây là một thư viện lớn chứa tất cả các thư viện chuẩn của C++. Thư viện bits/stdc++.h vô cùng hữu dụng vì tiết kiệm thời gian khai báo từng thư viện, đặc biệt là trong Lập trình thi đấu.

#include <bits/stdc++.h>