ÔN TẬP – CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT BÀI 1. XÂU NHỊ PHÂN CÓ K BIT 1. TỔ HỢP TIẾP THEO. HOÁN VỊ KẾ TIẾP.
CHỌN SỐ TỪ MA TRẬN VUÔNG CẤP N. SẮP XẾP QUÂN HẬU 1. SẮP XẾP QUÂN HẬU 2. SỐ NHỎ NHẤT CÓ N ƯỚC SỐ.
NGƯỜI DU LỊCH. KÝ TỰ LẶP TRONG HAI XÂU LIÊN TIẾP. TÌM KIẾM NHỊ PHÂN. GẤP ĐÔI DÃY SỐ.
SỐ FIBONACCI THỨ N. LŨY THỪA MA TRẬN. CHIA HẾT CHO 2. BẢNG HÌNH CHỮ NHẬT.
SẮP XẾP CÔNG VIỆC. SỐ MAY MẮN. NHẦM CHỮ SỐ. XÂU CON CHUNG DÀI NHẤT.
DÃY CON TĂNG DÀI NHẤT. DÃY CON CÓ TỔNG BẰNG S. DÃY CON DÀI NHẤT CÓ TỔNG CHIA HẾT CHO K. XÂU CON ĐỐI XỨNG DÀI NHẤT.
HÌNH VUÔNG LỚN NHẤT. SỐ CÓ TỔNG CHỮ SỐ BẰNG K. ĐƯỜNG ĐI NHỎ NHẤT. SẮP XẾP ĐỔI CHỖ TRỰC TIẾP.
SẮP XẾP CHỌN. SẮP XẾP CHÈN. SẮP XẾP NỔI BỌT. SẮP XẾP NHANH.
SẮP XẾP KHÔNG NHANH. SẮP XẾP LẠI DẠI CON. MUA CÀ PHÊ. TRÒ CHƠI VÒNG TRÒN.
BIỂU THỨC HẬU TỐ 1. BIỂU THỨC HẬU TỐ 2. DÃY NGOẶC ĐÚNG DÀI NHẤT. KIỂM TRA DÃY NGOẶC ĐÚNG.
SỬA LẠI DÃY NGOẶC. TÍNH TOÁN GIÁ TRỊ BIỂU THỨC. PHẦN TỬ BÊN PHẢI ĐẦU TIÊN LỚN HƠN. HÌNH CHỮ NHẬT LỚN NHẤT.
HÌNH CHỮ NHẬT 0-1. 30 BÀI 67: SỐ THỨ TỰ DẤU NGOẶC. 31 BÀI 68: PREFIX TO INFIX. 31 BÀI 69: PREFIX TO POSTFIX.
32 BÀI 70: POSTFIX TO PREFIX. 32 BÀI 71: POSTFIX TO INFIX. 33 BÀI 72: INFIX TO POSTFIX. 33 BÀI 73: DƯ THỪA DẤU NGOẶC.
ĐẢO NGƯỢC. CẤU TRÚC DỮ LIỆU HÀNG ĐỢI 1. CẤU TRÚC DỮ LIỆU HÀNG ĐỢI 2. HÀNG ĐỢI HAI ĐẦU (DEQUEUE).
ĐƯỜNG NGUYÊN TỐ. QUAY HÌNH VUÔNG. 39 BÀI 83: GIÁ TRỊ NHỎ NHẤT CỦA XÂU. SỐ NHỊ PHÂN.
BỘI SỐ CHỈ CÓ 0 VÀ 9. SỐ BDN NHỎ NHẤT CHIA HẾT CHO N. BIẾN ĐỔI VỀ 1. CHUYỂN TỪ DANH SÁCH CẠNH SANG DANH SÁCH KỀ.
CHUYỂN TỪ DANH SÁCH KỀ SANG DANH SÁCH CẠNH. CHUYỂN MA TRẬN KỀ SANG DANH SÁCH KỀ. CHUYỂN DANH SÁCH KỀ SANG MA TRẬN KỀ. ĐẾM SỐ AO.
TÌM ĐƯỜNG ĐI TRONG ĐỒ THỊ VÔ HƯỚNG. KIỂM TRA ĐỒ THỊ CÓ PHẢI LÀ CÂY HAY KHÔNG. ĐỒ THỊ HAI PHÍA. SỐ LƯỢNG HÒN ĐẢO.
THUẬT TOÁN BFS. THUẬT TOÁN DFS. THÀNH PHẦN LIÊN THÔNG - BFS. THÀNH PHẦN LIÊN THÔNG -DFS.
CÂY KHUNG CỦA ĐỒ THỊ THEO THUẬT TOÁN BFS. CÂY KHUNG CỦA ĐỒ THỊ THEO THUẬT TOÁN DFS. ĐỈNH KHỚP CỦA ĐỒ THỊ. CẠNH CẦU CỦA ĐỒ THỊ.
CÂY KHUNG NHỎ NHẤT. ĐƯỜNG ĐI NGẮN NHẤT 1. ĐƯỜNG ĐI NGẮN NHẤT 2. CÂY NHỊ PHÂN TÌM KIẾM.
ĐỘ SÂU CỦA CÂY. NODE TRUNG GIAN. DUYỆT THEO THỨ TỰ GIỮA. XÂU NHỊ PHÂN CÓ K BIT 1 Hãy in ra tất cả các xâu nhị phân độ dài N, có K bit 1 theo thứ tự từ điển tăng dần.
Input: Dòng đầu tiên là số lượng bộ test T (T ≤ 20). Mỗi test gồm 2 số nguyên N, K (1 ≤ K ≤ N ≤ 16). Output: Với mỗi test, in ra đáp án tìm được, mỗi xâu in ra trên một dòng. Ví dụ: Input Output 2 0011 4 2 0101 3 2 0110 1001 1010 1100 011 101 110 BÀI 2.
XÂU AB Một xâu kí tự S = (s1, s2, ., sn) được gọi là xâu AB độ dài n nếu với mọi siS thì si hoặc là kí tự A hoặc si là kí tự B. Ví dụ xâu S = “ABABABAB” là một xâu AB độ dài 8. Cho số tự nhiên N và số tự nhiên K (1K<N15 được nhập từ bàn phím), hãy viết chương trình liệt kê tất cả các xâu AB có độ dài N chứa duy nhất một dãy K kí tự A liên tiếp. Dữ liệu vào chỉ có một dòng ghi hai số N và K.
Kết quả ghi ra màn hình theo khuôn dạng: Dòng đầu tiên ghi lại số các xâu AB thỏa mãn yêu cầu bài toán; Những dòng kế tiếp, mỗi dòng ghi lại một xâu AB thỏa mãn. Các xâu được ghi ra theo thứ tự từ điển. Ví dụ: INPUT OUTPUT 5 3 5 AAABA AAABB ABAAA BAAAB BBAAA BÀI 3. TỔ HỢP TIẾP THEO Cho số nguyên dương (1<N<40) và số nguyên dương K<N.
Với 1 tổ hợp chập K phần tử của N, hãy cho biết tổ hợp tiếp theo sẽ có bao nhiêu phần tử mới. Nếu tổ hợp đã cho là cuối cùng thì kết quả là K. Dữ liệu vào: Dòng đầu ghi số bộ test, không quá 20. Mỗi bộ test viết trên hai dòng Dòng 1: hai số nguyên dương N và K (K<N) Dòng 2 ghi K số của tổ hợp ban đầu.
Theo đúng thứ tự tăng dần, không có số nào trùng nhau. 5 Kết quả: Với mỗi bộ dữ liệu in ra số lượng phần tử mới. Ví dụ: INPUT OUTPUT 3 1 5 3 2 1 3 5 4 5 3 1 4 5 6 4 3 4 5 6 BÀI 4. HOÁN VỊ KẾ TIẾP Hãy viết chương trình nhận vào một chuỗi (có thể khá dài) các ký tự số và đưa ra màn hình hoán vị kế tiếp của các ký tự số đó (với ý nghĩa là hoán vị có giá trị lớn hơn tiếp theo nếu ta coi chuỗi đó là một giá trị số nguyên).
Chú ý: Các ký tự số trong dãy có thể trùng nhau. Ví dụ: 123 -> 132 279134399742 -> 279134423799 Cũng có trường hợp sẽ không thể có hoán vị kế tiếp. Ví dụ như khi đầu vào là chuỗi 987. Dữ liệu vào: Dòng đầu tiên ghi số nguyên t là số bộ test (1 ≤ t ≤ 1000).
Mỗi bộ test có một dòng, đầu tiên là số thứ tự bộ test, một dấu cách, sau đó là chuỗi các ký tự số, tối đa 80 phần tử. Kết quả: Với mỗi bộ test hãy đưa ra một dòng gồm thứ tự bộ test, một dấu cách, tiếp theo đó là hoán vị kế tiếp hoặc chuỗi “BIGGEST” nếu không có hoán vị kế tiếp. Ví dụ: INPUT OUTPUT 3 1 132 1 123 2 279134423799 2 279134399742 3 BIGGEST 3 987 BÀI 5. CHỌN SỐ TỪ MA TRẬN VUÔNG CẤP N Cho ma trận vuông Ci,j cấp N (1 i, j N10) gồm N2 số tự nhiên và số tự nhiên K (các số trong ma trận không nhất thiết phải khác nhau và đều không quá 100, K không quá 104).
Hãy viết chương trình lấy mỗi hàng, mỗi cột duy nhất một phần tử sao cho tổng các phần tử này đúng bằng K. Dữ liệu vào: Dòng 1 ghi hai số N và K. N dòng tiếp theo ghi ma trận C. Kết quả: dòng đầu ghi số cách tìm được.
Mỗi dòng tiếp theo ghi một cách theo vị trí của số đó trong lần lượt từng hàng của ma trận. Xem ví dụ để hiểu rõ hơn. Ví dụ: INPUT OUTPUT 3 10 2 2 4 3 1 3 2 1 3 6 3 2 1 4 2 4 6 BÀI 6. SẮP XẾP QUÂN HẬU 1 Cho một bàn cờ vua có kích thước n * n, ta biết ràng quân hậu có thể di chuyển theo chiều ngang, dọc, chéo.
Vấn đề đặt ra rằng, có n quân hậu, bạn cần đếm số cách đặt n quân hậu này lên bàn cờ sao cho với 2 quân hậu bất kì, chúng không “ăn” nhau. Input: Một số nguyên dương n duy nhất (không quá 10) Output: Số cách đặt quân hậu. Ví dụ: Input Output 4 2 BÀI 7. SẮP XẾP QUÂN HẬU 2 Cho một bàn cờ 8 x 8, mỗi ô có một giá trị A[i][j] nhất định (0 ≤ A[i][j] ≤ 100), tương ứng với điểm số đạt được nếu như bạn đặt một quân cờ vào đó.
Nhiệm vụ của bạn là đặt 8 quân hậu lên bàn cờ, sao cho không có 2 quân nào ăn nhau, và số điểm đạt được là lớn nhất. Input: Dòng đầu tiên là số lượng bộ test T (T ≤ 20). Mỗi test gồm 8 dòng, mỗi dòng 8 số nguyên mô tả bàn cờ. Output: Với mỗi test, in ra đáp án trên một dòng.
Ví dụ: Input Output 1 260 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 48 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 BÀI 8. SỐ NHỎ NHẤT CÓ N ƯỚC SỐ Cho số nguyên dương N. Nhiệm vụ của bạn là tìm số K nhỏ nhất, sao cho K có đúng N ước. Input đảm bảo rằng đáp án không vượt quá 1018.
Input: Dòng đầu tiên là số lượng bộ test T (T ≤ 10). Mỗi test gồm 1 số nguyên N ( 1 ≤ N ≤ 1000). Output: Với mỗi test, in ra đáp án trên một dòng. Ví dụ: Input Output 2 6 4 12 6 7 BÀI 9.
TÌM BỘI SỐ Cho số nguyên N. Nhiệm vụ của bạn cần tìm số nguyên X nhỏ nhất là bội của N, và X chỉ chứa hai chữ số 0 và 9. Input: Dòng đầu tiên là số lượng bộ test T (T ≤ 10000). Mỗi bộ test chứa số nguyên N trên một dòng (1 ≤ N ≤ 500).
Output: Với mỗi test in ra đáp án tìm được trên một dòng. Ví dụ: Input Output 3 90 2 90 5 99 11 BÀI 10. MÁY ATM Một máy ATM hiện có n (n ≤ 30) tờ tiền có giá trị t[1], t[2], …, t[n]. Hãy tìm cách trả ít tờ nhất với số tiền đúng bằng S (các tờ tiền có giá trị bất kỳ và có thể bằng nhau).
Input: Dòng đầu tiên gồm 2 số nguyên n và S (S ≤ 109). Dòng thứ hai chứa n số nguyên t[1], t[2], …, t[n] (t[i] ≤ 109) Output: Số tờ tiền ít nhất phải trả. Ví dụ Input Output 3 5 1 1 4 5 BÀI 11. XEM PHIM Nông dân John đang đưa các con bò của anh ta đi xem phim.
Xe tải của anh ta thì có sức chứa tối đa là C (100 ≤ C ≤ 7000) kg, anh ta muốn đưa 1 số con bò đi xem phim sao cho tổng khối lượng của những con bò này là lớn nhất, đồng thời xe tải của anh ta vẫn còn có thể chở được. Cho N (1 ≤ N ≤ 25) con bò và khối lượng W_i của từng con, hãy cho biết khối lượng bò lớn nhất mà John có thể đưa đi xem phim là bao nhiêu. Dữ liệu vào: Dòng 1: 2 số nguyên cách nhau bởi dấu cách: C và N Dòng 2.