Bài 9: Độ phức tạp thuật toán, đọc ghi file và cách bài được chấm trên Online Judge (AC, WA, TLE)

Series: Nhập môn lập trình thuật toán Độ khó: Dễ Bài 9 / Kiến thức nền tảng Độ phức tạp thuật toán

// Nhập môn lập trình · Bài 9

Độ phức tạp thuật toán, đọc ghi file và cách bài được chấm trên Online Judge

Code chạy đúng trên máy mình chưa chắc đã được điểm. Bài này giúp em hiểu máy chấm làm gì, vì sao bị TLE, WA, RTE và cách ước lượng trước chương trình nhanh hay chậm.

Lời mở đầu

Sau 8 bài, em đã viết được kha khá chương trình. Nhưng khi nộp lên ClueOJ, Codeforces hay đi thi học sinh giỏi, rất nhiều bạn gặp cảnh: “Thầy ơi em chạy ví dụ ra đúng mà sao chỉ được 40 điểm?”. Nguyên nhân thường không nằm ở ý tưởng mà ở ba thứ: chương trình chạy quá chậm với dữ liệu lớn, tràn số, hoặc quên đọc ghi file đúng yêu cầu đề. Bài này là “bài học sống còn” trước khi bước vào thế giới thuật toán: em sẽ biết cách ước lượng thời gian chạy chỉ bằng việc nhìn giới hạn đề bài, từ đó chọn được thuật toán đủ nhanh ngay từ đầu.

Bài 1Lập trình là gì? Nên học C++ hay Python?Bài 2Cài Code::Blocks, nhập xuất, kiểu dữ liệuBài 3Câu lệnh điều kiện rẽ nhánhBài 4Vòng lặp for, whileBài 5Hàm (chương trình con)Bài 6Mảng 1 chiều, vectorBài 7Mảng 2 chiều, ma trậnBài 8Xâu ký tự (string)Bài 9Độ phức tạp, đọc ghi file, chấm bàiBài 10Struct, pair, sắp xếp nhiều tiêu chíBài 11STL: vector, set, map, stack, queueBài 12Số học: ước, UCLN, số nguyên tố, sàngBài 13Mảng đánh dấu, đếm phân phối, cộng dồnBài 14Tổng ôn và đề thi thử nhập môn

Trong bài này bạn sẽ học: cách một bài được chấm tự động trên Online Judge và ý nghĩa các trạng thái AC, WA, TLE, MLE, RTE, CE; khái niệm độ phức tạp và ký hiệu O lớn: $O(1)$, $O(\log n)$, $O(n)$, $O(n^2)$…; quy tắc $10^8$ phép tính mỗi giây để đoán thuật toán cần dùng; đọc ghi file bằng freopen, đọc đến hết file; tràn số và tăng tốc nhập xuất. Có khung chạy tay đếm số phép tính, mô phỏng “máy ước lượng thời gian” và 8 bài tập kèm gợi ý.

Lộ trình bài viết, bấm vào từng phần để nhảy tới:

Phần 1Máy chấm làm gìPhần 2Độ phức tạp O lớnPhần 3Ước lượng thời gianPhần 4Đọc ghi filePhần 5Tràn số, nhập xuất nhanhBài tập8 bài + gợi ý

Phần 1Máy chấm (Online Judge) làm gì với bài của em?

Khi em bấm Nộp bài, máy chấm không “đọc hiểu” code của em như thầy cô. Nó chỉ làm đúng một việc lặp đi lặp lại: biên dịch chương trình, rồi chạy nó với từng bộ test (dữ liệu vào bí mật do người ra đề chuẩn bị), so kết quả em in ra với đáp án. Mỗi test đúng được một phần điểm. Mỗi lần chạy bị giới hạn thời gian (thường 1 giây) và bộ nhớ (thường 256 MB).

Máy chấm biên dịch, chạy từng test trong giới hạn thời gian và bộ nhớ, rồi so kết quả. Mỗi test trả về một trạng thái.

Trạng thái	Nghĩa là	Nguyên nhân hay gặp
AC	Đúng và đủ nhanh	Chúc mừng 🎉
WA	Kết quả sai	Sai thuật toán, sót trường hợp đặc biệt ($n = 1$, số âm, số 0), tràn số, in thiếu/thừa dấu cách hoặc xuống dòng sai định dạng
TLE	Chạy quá thời gian	Thuật toán có độ phức tạp quá lớn so với $n$, vòng lặp vô hạn, nhập xuất chậm
MLE	Quá bộ nhớ	Khai báo mảng quá to (ví dụ long long a[10000][10000] ≈ 800 MB)
RTE	Chương trình bị “sập”	Truy cập ngoài mảng, chia cho 0, đệ quy quá sâu, mảng lớn khai báo trong main
CE	Không biên dịch được	Thiếu thư viện, sai cú pháp, chọn nhầm ngôn ngữ khi nộp

Vì sao code “chạy ví dụ đúng” vẫn chưa đủ?

Ví dụ trong đề thường rất nhỏ ($n = 5$), còn test chấm thật có thể tới $n = 10^6$ hay $10^{18}$. Một chương trình đúng nhưng chậm sẽ AC các test nhỏ và TLE ở các test lớn, tức là chỉ được một phần điểm. Vì vậy trước khi code, em luôn phải đọc kỹ phần giới hạn: $n$ tối đa bao nhiêu, các số lớn tới đâu. Hai phần tiếp theo sẽ dạy em cách biến con số giới hạn đó thành lựa chọn thuật toán.

Mô phỏng trực quan. Em đã biết AC, WA, TLE là gì, nhưng tận mắt thấy máy chấm làm việc vẫn dễ nhớ hơn nhiều. Em chọn một trong bốn bài nộp cho đề "tính 1 + 2 + … + n", bấm Tiếp để xem máy chấm chạy từng test, bấm giờ, so đáp án; để ý vì sao có bài qua hết test nhỏ mà vẫn trượt test lớn.

MÔ PHỎNGMáy chấm chạy bài của em trên từng testChọn bài nộp, có thể sửa danh sách test (mỗi test là một số n). Giới hạn thời gian 1 giây.

Bài nộpCông thức + long longCông thức + intVòng lặp O(n)Công thức gõ nhầmCác test (n)

ChậmVừaNhanh

AC: đúngWA: sai đáp ántest đang chấm / TLE: quá thời gian

Phần 2Độ phức tạp thuật toán và ký hiệu O lớn

Để biết chương trình nhanh hay chậm, ta không bấm giờ mà đếm số phép tính cơ bản (cộng, so sánh, gán…) nó phải làm, tính theo kích thước dữ liệu $n$. Ta chỉ quan tâm số phép tính tăng nhanh cỡ nào khi $n$ tăng, bỏ qua hằng số nhỏ. Cách viết gọn đó là ký hiệu O lớn: nếu chương trình làm khoảng $3n + 5$ phép tính, ta nói nó có độ phức tạp $O(n)$; khoảng $\frac{n(n-1)}{2}$ phép tính thì là $O(n^2)$.

Ví dụ 1: tính tổng $1 + 2 + \dots + n$. Cách dùng vòng lặp làm $n$ lần cộng, độ phức tạp $O(n)$. Cách dùng công thức Gauss $\frac{n(n+1)}{2}$ chỉ làm 3 phép tính dù $n$ lớn cỡ nào, độ phức tạp $O(1)$. Khung chạy tay dưới đây có biến dem đếm số lần vòng lặp chạy để em thấy rõ:

Code C++ và Python

#include <iostream>
using namespace std;

int main(){
    long long n;
    cin >> n;
    long long s1 = 0, dem = 0;
    for(long long i = 1; i <= n; i++){
        s1 += i;
        dem++;
    }
    long long s2 = n * (n + 1) / 2;
    cout << s1 << " " << s2 << " " << dem;
    return 0;
}

n = int(input())
s1 = dem = 0
for i in range(1, n + 1):      # O(n): n lần cộng
    s1 += i
    dem += 1
s2 = n * (n + 1) // 2          # O(1): chỉ 3 phép tính
print(s1, s2, dem)

C++▶ Chạy tay từng dòng codeSo sánh cách cộng dồn O(n) với công thức Gauss O(1): biến dem đếm số lần vòng lặp chạy.

Dữ liệu vào (stdin) – sửa thoải mái6

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main(){

5 long long n;

6 cin >> n;

7 long long s1 = 0, dem = 0;

8 for(long long i = 1; i <= n; i++){

9 s1 += i;

10 dem++;

11 }

12 long long s2 = n * (n + 1) / 2;

13 cout << s1 << " " << s2 << " " << dem;

14 return 0;

15}

ChậmVừaNhanhRất nhanh

Ví dụ 2: hai vòng lặp lồng nhau, $O(n^2)$. Đếm số cặp chỉ số $(i, j)$ với $i \lt j$ mà $a_i + a_j = k$. Cách “thử hết” dùng hai vòng for lồng nhau: với mỗi $i$, $j$ chạy từ $i + 1$ tới $n - 1$. Tổng số cặp phải xét là $(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}$, cỡ $n^2$. Khi $n$ gấp đôi, thời gian gấp bốn.

Code C++ và Python

#include <iostream>
using namespace std;

int a[100005];

int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    long long dem = 0, solan = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            solan++;
            if(a[i] + a[j] == k) dem++;
        }
    }
    cout << dem << " " << solan;
    return 0;
}

n, k = map(int, input().split())
a = list(map(int, input().split()))
dem = solan = 0
for i in range(n):
    for j in range(i + 1, n):    # O(n^2): n(n-1)/2 cặp
        solan += 1
        if a[i] + a[j] == k:
            dem += 1
print(dem, solan)

C++▶ Chạy tay từng dòng codeHai vòng lặp lồng nhau xét mọi cặp (i, j) với i < j: biến solan đếm số cặp đã xét, đúng bằng n(n−1)/2.

Dữ liệu vào (stdin) – sửa thoải mái5 7 3 4 2 5 1

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int a[100005];

5

6int main(){

7 int n, k;

8 cin >> n >> k;

9 for(int i = 0; i < n; i++) cin >> a[i];

10 long long dem = 0, solan = 0;

11 for(int i = 0; i < n; i++){

12 for(int j = i + 1; j < n; j++){

13 solan++;

14 if(a[i] + a[j] == k) dem++;

15 }

16 }

17 cout << dem << " " << solan;

18 return 0;

19}

ChậmVừaNhanhRất nhanh

Ví dụ 3: chia đôi liên tục, $O(\log n)$. Cứ mỗi bước chia $n$ cho 2 (bỏ phần dư) tới khi còn 1. Số bước chỉ khoảng $\log_2 n$: với $n = 10^9$ chỉ cần khoảng 30 bước, $n = 10^{18}$ cũng chỉ 60 bước! Đây là lý do tìm kiếm nhị phân ở bài 6 nhanh như vậy.

Code C++ và Python

#include <iostream>
using namespace std;

int main(){
    long long n;
    cin >> n;
    int dem = 0;
    while(n > 1){
        n /= 2;
        dem++;
    }
    cout << dem;
    return 0;
}

n = int(input())
dem = 0
while n > 1:        # O(log n)
    n //= 2
    dem += 1
print(dem)

C++▶ Chạy tay từng dòng codeChia đôi n tới khi còn 1: số bước xấp xỉ log2(n), cực kỳ ít dù n rất lớn.

Dữ liệu vào (stdin) – sửa thoải mái100

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main(){

5 long long n;

6 cin >> n;

7 int dem = 0;

8 while(n > 1){

9 n /= 2;

10 dem++;

11 }

12 cout << dem;

13 return 0;

14}

ChậmVừaNhanhRất nhanh

Độ phức tạp càng “cao” thì đường càng dựng đứng: chỉ cần $n$ tăng một chút, số phép tính đã bùng nổ.

Cách nhẩm nhanh độ phức tạp

1 vòng lặp chạy $n$ lần → $O(n)$. 2 vòng lồng nhau mỗi vòng $n$ lần → $O(n^2)$; ba vòng → $O(n^3)$. Vòng lặp mà biến nhân/chia đôi mỗi bước → $O(\log n)$. Vòng lặp for(i = 1; i * i <= n; i++) → $O(\sqrt{n})$. Hàm sort có sẵn → $O(n \log n)$. Hai đoạn code chạy nối tiếp nhau thì lấy cái lớn hơn: $O(n) + O(n^2) = O(n^2)$.

Mô phỏng trực quan. Ký hiệu O lớn nghe khá trừu tượng, nên em hãy xem nó như một cuộc đua: bốn chương trình trong phần này cùng chạy với một giá trị n, mỗi bước mỗi chương trình làm một phép tính. Em tăng dần n (8, 12, 16) để thấy làn O(n²) bị bỏ xa thế nào.

MÔ PHỎNGCuộc đua O(1), O(log n), O(n), O(n²)Nhập n từ 1 đến 16. Mỗi bước = 1 phép tính của mỗi chương trình; thanh màu cho biết đã làm được bao nhiêu.

n

ChậmVừaNhanh

đang chạyđã về đích

Phần 3Ước lượng thời gian: quy tắc 10⁸ phép tính mỗi giây

Một máy chấm bình thường làm được khoảng $10^8$ phép tính đơn giản mỗi giây (con số ước lượng, đủ dùng). Vậy với giới hạn 1 giây, em chỉ cần thay $n$ lớn nhất của đề vào độ phức tạp: nếu ra dưới khoảng $10^8$ thì yên tâm, vượt quá nhiều thì chắc chắn TLE. Bảng “tra ngược” dưới đây cho biết với $n$ cỡ nào thì nên nghĩ tới thuật toán nào:

Giới hạn $n$ trong đề	Độ phức tạp chấp nhận được	Gợi ý thuật toán
$n \le 10$ – $20$	$O(2^n)$, $O(n!)$	Duyệt mọi trường hợp, quay lui
$n \le 500$	$O(n^3)$	Ba vòng lặp lồng nhau
$n \le 5000$	$O(n^2)$	Hai vòng lặp lồng nhau
$n \le 10^6$	$O(n \log n)$ hoặc $O(n)$	Sắp xếp, tìm kiếm nhị phân, mảng cộng dồn, đếm phân phối
$n \le 10^{12}$	$O(\sqrt{n})$	Duyệt tới căn bậc hai (ước số, nguyên tố)
$n \le 10^{18}$	$O(\log n)$ hoặc $O(1)$	Công thức toán, chia đôi, lũy thừa nhanh

Em hãy thử “máy ước lượng” dưới đây: nhập $n$, máy tính giúp số phép tính và thời gian chạy dự kiến của từng độ phức tạp, đối chiếu với giới hạn 1 giây.

MÔ PHỎNGMáy ước lượng thời gian chạyNhập n (có thể viết 1e6, 10^9…) rồi bấm Ước lượng, hoặc chọn nhanh một giá trị bên dưới. Giả sử máy chấm làm 10⁸ phép tính mỗi giây, giới hạn 1 giây.

Đang tải mô phỏng…

Đừng quên: hằng số và bộ nhớ

Quy tắc $10^8$ chỉ là ước lượng. Phép chia, phép %, truy cập mảng nhảy lung tung chậm hơn phép cộng vài lần, còn Python chậm hơn C++ khoảng 10 – 50 lần (vì vậy thi HSG nên dùng C++). Ngoài thời gian, hãy tính cả bộ nhớ: một int tốn 4 byte, long long 8 byte; mảng $10^7$ số int tốn khoảng 40 MB, vẫn ổn với giới hạn 256 MB, nhưng $10^8$ số long long (800 MB) thì MLE.

Phần 4Đọc ghi file với freopen

Đề thi học sinh giỏi thường yêu cầu: “Dữ liệu vào từ file BAI1.INP, kết quả ghi ra file BAI1.OUT”. Nếu em vẫn đọc từ bàn phím, máy chấm sẽ không đưa dữ liệu cho em và chương trình bị chấm 0 điểm dù thuật toán đúng hoàn toàn. Đây là lỗi mất điểm “oan” phổ biến nhất ở các kỳ thi! Cách đơn giản nhất trong C++ là thêm 2 dòng freopen ở đầu main: mọi lệnh cin/cout phía sau tự động đọc ghi file, phần còn lại của code giữ nguyên.

Code C++ và Python

#include <iostream>
using namespace std;

int main(){
    freopen("BAI1.INP", "r", stdin);    // "r" = read: đọc từ file
    freopen("BAI1.OUT", "w", stdout);   // "w" = write: ghi ra file
    int a, b;
    cin >> a >> b;          // giờ cin đọc từ BAI1.INP
    cout << a + b;          // giờ cout ghi vào BAI1.OUT
    return 0;
}

import sys
sys.stdin = open("BAI1.INP", "r")
sys.stdout = open("BAI1.OUT", "w")
a, b = map(int, input().split())    # input() giờ đọc từ file
print(a + b)                        # print() giờ ghi vào file

4 lỗi freopen hay gặp

1. Sai tên file: phải giống hệt đề, kể cả chữ hoa chữ thường và đuôi (.INP khác .inp trên máy chấm Linux). 2. Đặt freopen sau lệnh cin: phải đặt ngay đầu main. 3. Nộp lên OJ không dùng file mà vẫn để freopen → đọc file không tồn tại, chương trình không có dữ liệu. Mẹo: khi luyện trên ClueOJ, đề nào ghi “dữ liệu vào từ bàn phím” thì xóa hoặc thêm // trước 2 dòng freopen. 4. Test trên máy mình: nhớ tạo file BAI1.INP cùng thư mục với file code rồi mới chạy, kết quả nằm trong BAI1.OUT chứ không hiện ra màn hình.

Đọc đến hết file. Có đề không cho biết trước có bao nhiêu số, chỉ nói “file gồm nhiều số nguyên”. Khi đó dùng while(cin >> x): biểu thức cin >> x trả về “đúng” nếu đọc được một số, và trả về “sai” khi đã hết dữ liệu, vòng lặp tự dừng. Khung chạy tay dưới đây giả sử dữ liệu vào đã được freopen từ file:

Code C++ và Python

#include <iostream>
using namespace std;

int main(){
    long long x, tong = 0;
    int dem = 0;
    while(cin >> x){
        tong += x;
        dem++;
    }
    cout << dem << " " << tong;
    return 0;
}

import sys
a = list(map(int, sys.stdin.read().split()))   # đọc toàn bộ file, tách thành các số
print(len(a), sum(a))

C++▶ Chạy tay từng dòng codeĐọc số tới khi hết dữ liệu: cin >> x trả về sai khi không còn gì để đọc, vòng while tự dừng.

Dữ liệu vào (stdin) – sửa thoải mái3 5 -2 10 7

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main(){

5 long long x, tong = 0;

6 int dem = 0;

7 while(cin >> x){

8 tong += x;

9 dem++;

10 }

11 cout << dem << " " << tong;

12 return 0;

13}

ChậmVừaNhanhRất nhanh

Phần 5Tràn số và tăng tốc nhập xuất

Tràn số là nguyên nhân số một gây WA “bí ẩn”. Kiểu int chỉ chứa được số trong khoảng $\pm 2{,}1 \cdot 10^9$. Nếu kết quả phép tính vượt quá, máy không báo lỗi mà “quay vòng” sang một số rất vô lý (thường là số âm). Ví dụ $n = 100000$ thì $n \cdot n = 10^{10}$ vượt quá int. Cách chữa: dùng long long (tới khoảng $9{,}2 \cdot 10^{18}$) và chú ý ép kiểu trước khi nhân: 1LL * n * n. Viết long long c = n * n; với n là int vẫn tràn, vì phép nhân được làm trên int trước rồi mới gán.

Code C++ và Python

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    int a = n * n;
    long long b = n * n;
    long long c = 1LL * n * n;
    cout << a << endl << b << endl << c;
    return 0;
}

n = int(input())
# Python tự mở rộng số nguyên nên KHÔNG bao giờ tràn số
print(n * n)

C++▶ Chạy tay từng dòng codeSo sánh 3 cách tính n × n: int bị tràn, gán vào long long vẫn tràn, chỉ 1LL * n * n là đúng.

Dữ liệu vào (stdin) – sửa thoải mái100000

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main(){

5 int n;

6 cin >> n;

7 int a = n * n;

8 long long b = n * n;

9 long long c = 1LL * n * n;

10 cout << a << endl << b << endl << c;

11 return 0;

12}

ChậmVừaNhanhRất nhanh

Tăng tốc nhập xuất. Khi phải đọc tới $10^6$ số, bản thân việc nhập xuất bằng cin/cout cũng có thể làm TLE. Hai thói quen nên có trong mọi bài thi:

Code C++ và Python

#include <bits/stdc++.h>          // gộp mọi thư viện chuẩn (dùng được trên máy chấm)
using namespace std;

int main(){
    ios::sync_with_stdio(false);  // tắt đồng bộ với scanf/printf → cin, cout nhanh gấp nhiều lần
    cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cout << i << '\n';        // dùng '\n' thay cho endl (endl xả bộ đệm mỗi lần nên rất chậm)
    return 0;
}

import sys
input = sys.stdin.readline           # đọc nhanh hơn input() mặc định
n = int(input())
print('\n'.join(str(i) for i in range(1, n + 1)))   # in một lần thay vì in n lần

Khung chương trình chuẩn cho mọi bài thi

Từ giờ, em có thể bắt đầu mọi bài bằng khung: #include <bits/stdc++.h>, using namespace std;, trong main viết ngay freopen (nếu đề yêu cầu) và hai dòng tăng tốc nhập xuất, dùng long long cho các đại lượng có thể lớn, in xuống dòng bằng '\n'. Trước khi nộp, tự hỏi: độ phức tạp của mình với $n$ lớn nhất là bao nhiêu phép tính?

Bài tậpLuyện tư duy độ phức tạp

Mỗi bài đều có giới hạn rất lớn: cách “thử hết” sẽ bị TLE. Trước khi xem gợi ý, em hãy tự tính xem cách đơn giản nhất mất bao nhiêu phép tính, rồi nghĩ cách giảm xuống.

Bài 1Tổng từ 1 đến nDễ

Cho $n$ ($1 \le n \le 10^9$). Tính $1 + 2 + \dots + n$.

Input

1000000000

Output

500000000500000000

💡 Gợi ý

Vòng lặp $10^9$ lần mất khoảng 10 giây → TLE. Dùng công thức $\frac{n(n+1)}{2}$, độ phức tạp $O(1)$. Kết quả tới $5 \cdot 10^{17}$ nên bắt buộc dùng long long.

Xem code tham khảo (C++ / Python)

#include <iostream>
using namespace std;

int main(){
    long long n;
    cin >> n;
    cout << n * (n + 1) / 2;
    return 0;
}

n = int(input())
print(n * (n + 1) // 2)

Bài 2Đếm bội số trong đoạnDễ

Cho $a, b, k$ ($1 \le a \le b \le 10^{18}$, $1 \le k \le 10^{18}$). Đếm số các số nguyên trong đoạn $[a, b]$ chia hết cho $k$.

Input

1 20 3

Output

6

💡 Gợi ý

Từ 1 tới $b$ có đúng $\lfloor b / k \rfloor$ số chia hết cho $k$. Vậy đáp án là $\lfloor b / k \rfloor - \lfloor (a - 1) / k \rfloor$, chỉ 2 phép chia, không cần duyệt.

Xem code tham khảo (C++ / Python)

#include <iostream>
using namespace std;

int main(){
    long long a, b, k;
    cin >> a >> b >> k;
    cout << b / k - (a - 1) / k;
    return 0;
}

a, b, k = map(int, input().split())
print(b // k - (a - 1) // k)

Bài 3Tổng các số trong fileDễ

File TONG.INP chứa nhiều số nguyên (không biết trước bao nhiêu số, nằm trên nhiều dòng), mỗi số có trị tuyệt đối không quá $10^9$. Ghi ra file TONG.OUT tổng của chúng. (Trên khung ví dụ, coi như đọc từ bàn phím.)

Input

3 5
-2 10
7

Output

23

💡 Gợi ý

Dùng while(cin >> x) như phần 4 để đọc tới hết file, nhớ freopen hai file. Tổng có thể vượt int nên dùng long long. Python: sum(map(int, sys.stdin.read().split())).

Xem code tham khảo (C++ / Python)

#include <iostream>
using namespace std;

int main(){
    // freopen("TONG.INP", "r", stdin);
    // freopen("TONG.OUT", "w", stdout);
    long long x, tong = 0;
    while(cin >> x) tong += x;
    cout << tong;
    return 0;
}

import sys
# sys.stdin = open("TONG.INP"); sys.stdout = open("TONG.OUT", "w")
print(sum(map(int, sys.stdin.read().split())))

Bài 4Lũy thừa của 2Dễ

Cho $n$ ($1 \le n \le 10^{18}$). Tìm số nguyên $k$ lớn nhất sao cho $2^k \le n$.

Input

100

Output

6

💡 Gợi ý

Chia đôi $n$ liên tục tới khi còn 1 và đếm số lần chia (giống ví dụ 3), chỉ khoảng 60 bước. Hoặc nhân một biến p = 1 lên gấp đôi cho tới khi p * 2 > n, cẩn thận tràn số ở bước nhân.

Xem code tham khảo (C++ / Python)

#include <iostream>
using namespace std;

int main(){
    long long n;
    cin >> n;
    int k = 0;
    while(n > 1){
        n /= 2;
        k++;
    }
    cout << k;
    return 0;
}

n = int(input())
print(n.bit_length() - 1)     # hoặc chia đôi như C++

Bài 5Cặp có tổng chẵnTrung bình

Cho dãy $n$ số nguyên ($2 \le n \le 10^5$). Đếm số cặp chỉ số $i \lt j$ sao cho $a_i + a_j$ là số chẵn.

Input

5
1 2 3 4 5

Output

4

💡 Gợi ý

Hai vòng lặp lồng nhau là $O(n^2) \approx 5 \cdot 10^9$ → TLE. Nhận xét: tổng chẵn khi hai số cùng chẵn hoặc cùng lẻ. Đếm $c_0$ số chẵn, $c_1$ số lẻ; số cách chọn 2 trong $c$ phần tử là $\frac{c(c-1)}{2}$. Đáp án $\frac{c_0(c_0-1)}{2} + \frac{c_1(c_1-1)}{2}$, độ phức tạp $O(n)$.

Xem code tham khảo (C++ / Python)

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    long long c0 = 0, c1 = 0;
    for(int i = 0; i < n; i++){
        long long x;
        cin >> x;
        if(x % 2 == 0) c0++;
        else c1++;
    }
    cout << c0 * (c0 - 1) / 2 + c1 * (c1 - 1) / 2;
    return 0;
}

n = int(input())
a = list(map(int, input().split()))
c0 = sum(1 for x in a if x % 2 == 0)
c1 = n - c0
print(c0 * (c0 - 1) // 2 + c1 * (c1 - 1) // 2)

Bài 6Tổng chữ sốDễ

Cho số nguyên dương $n$ ($n \le 10^{18}$). Tính tổng các chữ số của $n$.

Input

9876543210

Output

45

💡 Gợi ý

Lấy chữ số cuối bằng n % 10, bỏ chữ số cuối bằng n /= 10, lặp tới khi $n = 0$. Số lần lặp bằng số chữ số (tối đa 19), độ phức tạp $O(\log_{10} n)$. Nhớ dùng long long.

Xem code tham khảo (C++ / Python)

#include <iostream>
using namespace std;

int main(){
    long long n;
    cin >> n;
    int tong = 0;
    while(n > 0){
        tong += n % 10;
        n /= 10;
    }
    cout << tong;
    return 0;
}

n = input().strip()
print(sum(int(c) for c in n))

Bài 7Đếm ước sốTrung bình

Cho $n$ ($1 \le n \le 10^{12}$). Đếm số ước nguyên dương của $n$.

Input

36

Output

9

💡 Gợi ý

Duyệt $i$ từ 1 tới $n$ là $10^{12}$ phép tính → TLE. Nhận xét: ước luôn đi theo cặp $(i, n / i)$, trong đó một số $\le \sqrt{n}$. Duyệt for(i = 1; i * i <= n; i++), nếu n % i == 0 thì cộng 2 (cặp $i$ và $n/i$), riêng khi i * i == n chỉ cộng 1. Chỉ $10^6$ bước, độ phức tạp $O(\sqrt{n})$. Bài 12 sẽ học kỹ hơn.

Xem code tham khảo (C++ / Python)

#include <iostream>
using namespace std;

int main(){
    long long n;
    cin >> n;
    long long dem = 0;
    for(long long i = 1; i * i <= n; i++){
        if(n % i == 0){
            if(i * i == n) dem += 1;
            else dem += 2;
        }
    }
    cout << dem;
    return 0;
}

n = int(input())
dem = 0
i = 1
while i * i <= n:
    if n % i == 0:
        dem += 1 if i * i == n else 2
    i += 1
print(dem)

Bài 8Cặp số có tổng bằng xKhá

Cho dãy $n$ số nguyên dương tăng dần chặt ($n \le 10^6$) và số $x$. Đếm số cặp $i \lt j$ có $a_i + a_j = x$.

Input

6 10
1 2 4 6 8 9

Output

3

💡 Gợi ý

Hai vòng lặp → $O(n^2) = 10^{12}$, TLE. Dùng hai con trỏ: $l = 0$ ở đầu, $r = n - 1$ ở cuối. Nếu $a_l + a_r = x$ thì đếm và dịch cả hai vào trong; nếu tổng nhỏ hơn $x$ thì tăng $l$ (cần số lớn hơn); nếu lớn hơn thì giảm $r$. Mỗi bước loại được ít nhất 1 phần tử nên chỉ mất $O(n)$.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int a[1000005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long x;
    cin >> n >> x;
    for(int i = 0; i < n; i++) cin >> a[i];
    int l = 0, r = n - 1;
    long long dem = 0;
    while(l < r){
        long long s = (long long)a[l] + a[r];
        if(s == x){ dem++; l++; r--; }
        else if(s < x) l++;
        else r--;
    }
    cout << dem;
    return 0;
}

n, x = map(int, input().split())
a = list(map(int, input().split()))
l, r, dem = 0, n - 1, 0
while l < r:
    s = a[l] + a[r]
    if s == x:
        dem += 1; l += 1; r -= 1
    elif s < x:
        l += 1
    else:
        r -= 1
print(dem)

Bài tiếp theo · Bài 10

Struct, pair và sắp xếp theo nhiều tiêu chí

Gom họ tên, điểm, tuổi của một học sinh vào một biến; sắp xếp bảng điểm theo điểm giảm dần, bằng điểm thì theo tên.

Học bài 10 →

← Bài 8: Xâu ký tự (string)Xem cả series Nhập môn lập trình

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Bản quyền thuộc về Thầy Nguyễn Việt Nam Sơn. Bài viết, lời giải, hình minh hoạ và mã nguồn trên trang là công sức biên soạn của thầy qua nhiều năm giảng dạy. Vui lòng không sao chép, đăng lại hay sử dụng dưới mọi hình thức khi chưa được sự đồng ý của tác giả. Nếu thấy hữu ích, hãy chia sẻ bằng đường link bài gốc nhé. Cảm ơn bạn!