Phương pháp sinh ngẫu nhiên
Duyệt mọi cách cắt + Thoát duyệt mỗi cách cắt đúng lúc khi cách đó không cắt tốt hơn phương án cũ.
Duyệt đệ quy theo mức k + Tham
Loang qua ít cạnh nhất. Chú ý:
Gọi F[i] là tổng các số từ 1→ i, kết quả là Max(F[i] – F[j]) thì chương trình có độ phức tạp O(N2), không khả thi với N = 100000 (Chương trình 2).
Cải tiến:
Max(F[i] – F[j]) = F[i] – Min( F[0], F[1], F[2], .., F[i-1]) = F[i] – F[c[i]]
c[i] là chỉ số của phần tử nhỏ nhất trong dãy F đứng trước F[i]. Độ phức tạp của chương trình sẽ là O(N).
Lưu ý. Sử dụng kiểu tập hợp để nhận biết hoán vị.
Duyệt theo n và các ước nhỏ hơn của n.
Sử dụng thuật toán so khớp xâu Knuth – Morris – Pratt
Thuật toán tính giá trị biểu thức trung tố nhờ chuyển nó thành biểu thức hậu tố (Biểu thức Ba lan)
Hạn chế thời gian: 2 giây. Hạn chế bộ nhớ: 256MB
Bạn có một thanh sô cô la hình chữ nhật gồm m×n ô vuông đơn vị. Bạn muốn ăn đúng k ô vuông, nên bạn có thể cần phải bẻ thanh sô cô la. Trong một lần bẻ, bạn cần bẻ phần sô cô la hình chữ nhật thành hai miếng hình chữ nhật. Bạn chỉ có thể bẻ theo các dòng nằm giữa các hình vuông: theo một chiều ngang hoặc theo một chiều dọc. Tiền chi phí cho một lần bẻ là bình phương của chiều dài đường bẻ. Ví dụ, nếu bạn có một thanh sô cô la bao gồm 2 × 3 ô vuông, bạn có thể bẻ nó theo chiều ngang và nhận được hai miếng 1 × 3 (chi phí như vậy là 32 = 9), hoặc bạn có thể bẻ nó theo chiều dọc theo hai cách và nhận được hai phần: 2 × 1 và 2 × 2 (chi phí như vậy là 22 = 4). Đối với các số n, m và k nhất định tìm tổng số tiền chi phí tối thiểu khi bẻ. Bạn có thể ăn đúng k ô vuông sô cô la nếu sau mọi lần bẻ có được một tập hợp các miếng sô cô la hình chữ nhật mà tổng của chúng bằng k ô vuông. Phần còn lại là m×n – k ô vuông không nhất thiết phải tạo thành hình chữ nhật.
Input. Tên tệp là chocola.inp
Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 40910) — là số bộ giá trị n, m và k cần xử lý. Mỗi dòng trong t dòng tiếp theo là ba số nguyên n, m và k (1 ≤ n, m ≤ 30, 1 ≤ k ≤ min(n×m, 50)) — tương ứng là kích thước thanh sô cô la và số ô vuông mà bạn muốn ăn.
Output. Tên tệp là chocola.out
Với mỗi bộ n, m và k hãy in ra giá tiền chi phí nhỏ nhất cần để bẻ thanh sô cô la tạo ra được đúng k ô vuông để ăn.
Ví dụ
input
4
2 2 1
2 2 3
2 2 2
2 2 4
output
5
5
4
0
Giải thích
Trong truy vấn thứ nhất của ví dụ cần thực hiện 2 lần bẻ:
Trong truy vấn thứ hai, muốn ăn 3 ô vuông cần dùng chiến thuật bẻ như truy vấn trên.
Hạn chế thời gian: 2 giây. Hạn chế bộ nhớ: 256MB
Trong giờ Toán, Va-xa rất say sưa đếm những con quạ bên ngoài cửa sổ. Hôm nay là một ngày không bình thường vì có rất nhiều quạ, ngoài ra chúng gồm đúng hai loại đen và trắng. Đến giữa giờ học, Va-xa thôi không đếm nữa – nó đã dếm được a con quạ trắng và b con quạ đen ngoài cửa sổ.
Bây giờ đến cuối giờ học không còn nhiều thời gian nên Va-xa quyết định nghe thầy giáo giảng bài. Đúng lúc này, thầy giáo đang giảng về ước số chung lớn nhất của hai số nguyên. Va-xa là một cậu bé tài năng nó hiểu ngay khái niệm này. Nó tính ngay được ước chung lớn nhất của hai số a và b. Sau đó nó nghĩ ra một khái niệm mới là ước chung dễ thương của hai số x và y đó là ước số chung của x và y có tổng các chữ số là lớn nhất.
Input. Tên tệp là mcd.inp
Một dòng duy nhất chứa hai số nguyên a và b (1≤a, b≤109)
Output. Tên tệp là mcd.out
Một dòng chứa ước chung dễ thương của a và b. Nếu có nhiều kết quả thì dẫn ra một kết quả nào đó.
| MCD.INP | MCD.OUT |
| 220 440 | 55 |
Time Limit: 0.5 giây / test
Memory Limit: 64 MB, 8 MB ngăn xếp
Hãy xem xét các số nguyên N và D. Xác định số lượng các cặp số A và B mà cả hai số A và B đều không vượt quá N và có ước số chung lớn nhất là D.
Input. Dòng đầu tiên của file cntgcd.in là hai số nguyên N và D ngăn cách bởi một dấu trống
Output. Dòng đầu tiên của file cntgcd.out sẽ chứa một số nguyên T là số cặp số nguyên không vượt quá N và có ước số chung lớn nhất bằng D.
Hạn chế.
Ví dụ.
| Cntgcd.in | Cntgcd.out |
| 20 5 | 6 |
Giải thích. Sáu cặp là:
(5, 5) (5, 10) (5, 15) (5, 20) (10, 15) (15, 20)
Nội dung kiểm tra cuối khóa học 1 năm trước khi dự thi OLP’24 năm 2015. Sau khi Nhà trường tổ chức kiểm tra và gửi bài làm về, trang web sẽ đăng đề bài, hướng dẫn giải và chương trình code (vào khoảng 14-11-2015)
Nội dung bài kiểm tra: tư duy thông minh, quy hoạch động, luồng cực đại.
Chúc các bạn thi đấu tự tin, bình tĩnh, có chiến thuật giành kết quả.
Thân ái,
Tuần 1 (1/10-8/10): Ba bài tập về dãy số, xử lý bít, đường đi qua nhiều đỉnh nhất (xem trong PROB 10-2015 week 1). Ngày 8/10 sẽ có lời giải (xem trong SOL 10-2015 week 1)
Tuần 2 (8/10-15/10): Ba bài tập về số học, xử lý bít, xâu và đồ thị (xem trong PROB 10-2015 week 2). Ngày 15/10 sẽ có lời giải (xem trong SOL 10-2015 week 2)
Tuần 3 (15/10-22/10): Ba bài tập về đồ thị và quy hoạch động, thuật toán greedy (xem trong PROB 10-2015 week 3). Ngày 22/10 sẽ có lời giải (xem trong SOL 10-2015 week 3)
Tuần 4 (22/10-31/10): Ba bài tập về số học, hình học, quy hoạch động (xem trong PROB 10-2015 week 4). Ngày 31/10 sẽ có lời giải (xem trong SOL 10-2015 week 4)
Đề nghị các bạn học viên sau khi nhận được đề bài, hãy bố trí thời gian tự làm bài tập trong khoảng thời gian quy định của đề và gửi bài làm từng tuần về trandohungvn@gmail.com.
Thân ái.
Gồm 12 bài tập từ 21 đến 32 với nội dung: Ôn tập quy hoạch động và đồ thị
Tiếp tục luyện bài tập đồ thị về tìm chu trình, cây khung, đường đi ngắn nhất, cây khung ngắn nhất: từ bài 12 đến bài 20.
Ngày 23/7 có lời giải.
Bài tập tháng 5 gồm 11 bài (1-11) về những nội dung ban đầu của lý thuyết đồ thị:
– Khái niệm cơ bản. Biểu diễn đồ thị
– Tìm kiếm DFS và BFS
– Tính liên thông của đồ thị
– Vài ứng dụng của tìm kiếm DFS và BFS:
Định chiều đồ thị,
Khớp và cầu,
Cây khung,
Song liên thông,
Nửa liên thông
Tháng 4 năm 2015, không ra đề bài mới. Học viên ôn tập lại các bài tập (83 bài) để chuẩn bị cho kỳ thi Olempic cấp trường vào ngày 26/4.
Chúc các bạn ôn tập tốt
Gồm các bài tập về Quy hoạch động (Từ bài 72 đến bài 83).
Những bài tập về quy hoạch động rất phong phú, các bạn có thể tham khảo trên nhiều tài liệu khác. Trong phạm vi trang web, chỉ trình bày một số bài tập trong Tài liệu Giáo khoa Chuyên Tin.
tuoitrekthc 