Bài tập phần Backtracking

Bài tập phần Backtracking: download.

Ôn tập Olympic 2015

Gửi các bạn tham dự ôn tập Olympic Tin học 2015:

Tài liệu tham khảo:

1. Tài liệu thuật toán của Lê Minh Hoàng: download.

2. Tài liệu “Art of Programming Contest”, 2nd Edition: download.

Bài học ngày 31-01-2015:

1. Bài tập trên lớp và về nhà: download.

2. Bài giải cho các bài tập trên lớp: download.

Bài giảng Phân tích, thiết kế và đánh giá thuật toán

Sách gối đầu giường cho lập trình viên thi lập trình

Được viết bởi “Ahmed Shamsul Arefin” và nhận được nhiều lời đánh giá cao của các chuyên gia cũng như các lập trình viên tham gia các cuộc thi lập trình online trên mạng. Đây là một trong những cuốn sách mà sinh viên năm nhất của nghành Công nghệ Thông tin, Học sinh Phổ thông, đặc biệt là những ai hay tham gia thi lập trình nên đọc.
Địa chỉ download

Bài 2: Số Hamming

Các số Hamming lần đầu tiên được đưa ra trong một bài tập của Richard W. Hamming, người đã phát minh ra các mã Hamming. Theo định nghĩa một số Hamming là một số nguyên dương có thể phân tích thành tích của một số các thừa số được chọn ngẫu nhiên nào đó. Chẳng hạn nếu tập các thừa số là {2, 3, 5} thì 90 = 2*3*3*5 là một số Hamming nhưng 70 = 2*5*7 lại không phải là một số Hamming vì nó còn chia hết cho 7 (không nằm trong tập các thừa số). Số 1 luôn được xem là một số Hamming cho dù các thừa số được chọn như thế nào đi chăng nữa.
Hãy viết chương trình xác định số Hamming thứ n với một tập các thừa số cho trước.
Input
Dòng đầu của file input là một tập các thừa số ngăn cách với nhau bằng 1 dấu cách, số các thừa số không vượt quá 50, một thừa số có giá trị lớn hơn 1 và nhỏ hơn 300. Dòng thứ hai là số N (1 ≤ N ≤ 100000).
Output
Đưa ra kết quả là số Hamming thứ N.
Ví dụ
Input 1:
2 3 5
15
Output 1:
24
Input 2:
2 2 2 4 4 4 8 8 8
11
Output 2:
1024
Input 3:
7 9 14 6
52
Output 3:
4802

Bài 1: Tổng các số nguyên tố

Một số số nguyên có thể biểu diễn dưới dạng tổng của một hoặc nhiều số nguyên tố liên tiếp. Chẳng hạn 53 có thể biểu diễn thành 5 + 7 + 11 + 13 + 17 hoặc 53. 41 có 3 cách biểu diễn khác nhau là: 2 + 3 + 5 + 7 + 11 + 13 = 11 + 13 + 17 = 41. Chú ý là các biểu diễn trên sử dụng các số nguyên tố liên tiếp và không lặp lại.
Hãy viết chương trình tính xem một số nguyên bất kỳ có thể có bao nhiêu cách biểu diễn như trên.
Input
Dữ liệu của chương trình cho trong một file text gồm các số nguyên (nhỏ hơn 10000 và lớn hơn 1) viết trên các dòng riêng biệt, kết thúc file input là 1 dòng ghi số 0.
Output
Với mỗi số nguyên trong file input hãy đưa ra số cách biểu diễn tương ứng trên 1 dòng của file output.
Ví dụ:
Input

2
3
17
41
20
666
12
53
0
Output:
1
1
2
3
0
0
1
2

Olympic Tin học – ACM 2009

Thời gian: đầu tháng 10-2009 (trước 9/10/2009)
Địa điểm: Đại học Thủy sản Nha Trang – Thành phố Nha Trang.

Lịch ôn tập (dự kiến):

Tuần 1: Từ :24 / 08 đến : 30 / 08 Kỹ thuật duyệt. Đệ qui và thuật toán đệ qui
Tuần 2: Từ : 31 / 08 đến : 06 / 09 Lý thuyết đồ thị. Kỹ thuật duyệt đồ thị theo chiều sâu DFS
Tuần 3: Từ : 06 / 09 đến : 13 / 09 Kỹ thuật duyệt đồ thị theo chiều rộng BFS. Thuật toán tìm đường đi ngắn nhất trên đồ thị Dijkstra, Floyd.
Tuần 4: Từ : 14/09 đến : 20 /09 Qui hoạch động. Các bài toán cơ sở
Tuần 5: Từ :21 / 09 đến : 27 /09 Qui hoạch động (tiếp)
Tuần 6 Từ :28 / 09 đến : 04 /10 Dự trữ
Danh sách đội dự tuyển:
Đỗ Tiến Hoàng Giang CNT48ĐH
Lê Quyết Tiến CNT47ĐH
Nguyễn Đức Văn CNT46ĐH
Lê Mạnh Quyền CNT48ĐH
Lê Văn Vinh CNT49ĐH1
Nguyễn Đắc Xuân Duy CNT47ĐH
Nguyễn Duy An CNT47ĐH
Công cụ lập trình: DevCpp (xem trong phần lập trình C++ hoặc DevTools).
Một số links tham khảo: http://www.hkoi.org