Về các bài toán đặc biệt (Ad-hoc problems)

1. Giới thiệu:
Các bài toán đặc biệt là các bài toán không thể phân loại vào bất cứ lớp bài toán nào, và các phương pháp giải quyết bài toán được coi là độc đáo. Các bài toán này có thể được phân loại thành hai dạng: đơn giản và bài toán mô phỏng (bài toán có một số quy tắc mô phỏng câu trả lời).
Các bài toán đặc biệt thường xuất hiện trong các cuộc thi lập trình. Trong một bộ đề chuẩn (10 bài), có thể có 1 - 2 bài toán đặc biệt. Nếu bài toán đơn giản, nó là bài toán đầu tiên mà các thí sinh (hoặc đội thi - ở đây gọi tắt là đội) chọn để giải quyết. Nhưng vẫn tồn tại những bài toán mang tính phức tạp, một số thí sinh (đội) sẽ chọn chiến thuật gác lại bài này để làm các bài khác cho đến hết giờ làm bài.
2. Ví dụ:
Bài toán: UVa 100 - The 3n + 1 Problems.
Nguồn bài: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36.

1. Phân tích đề bài:
• Đề cho một giải thuật:
1. Nhập vào số n.
2. In ra số n.
3. Nếu n = 1 thì dừng lại.
4. Nếu n là số lẻ thì n := 3n + 1, ngược lại n := n / 2.
5. Quay lại bước 2.
• Và cho một ví dụ:
Với n = 22, theo thuật toán, ta sẽ in ra màn hình các số như sau: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1. Như vậy, từ lúc nhập vào số n cho đến lúc n = 1, ta sẽ in ra 16 con số, và con số đó được gọi là chu kỳ của số n.
• Yêu cầu:
Cho hai số i và j. Hãy tìm số n (i ≤ n ≤ j) sau cho chu kỳ của số n là lớn nhất.
2. Triển khai thuật toán:
1. Từ hai số i, j đã nhập vào. Nếu i > j ta đổi chỗ i, j.
2. x := i, max (chu kỳ lớn nhất) := 0.
3. Nếu x > y thì in kết quả max, kết thúc chương trình.
4. n := x.
5. k := 1.
6. Nếu n = 1 chuyển sang bước 9.
7. Nếu n là số lẻ thì n := 3n + 1, ngược lại n := n / 2.
8. k := k + 1.
9. Nếu k > max thì max := k.
10. x := x + 1. Quay lại bước 3.
3. Một số bài toán khác:
• UVa 272 - TEX Quotes.
• UVa 394 - Mapmaker.
• UVa 483 - Word Scramble.
• UVa 573 - The Snail.
• UVa 661 - Blowing Fuses.
• UVa 739 - Soundex Indexing.
• UVa 837 - Light and Transparencies.
• UVa 941 - Permutations.
• UVa 10082 - WERTYU.
• UVa 10141 - Request for Proposal.
• UVa 10281 - Average Speed.
• UVa 10363 - Tic Tac Toe.
• UVa 10420 - List of Conquests.
• UVa 10528 - Major Scales.
• UVa 10683 - The decadary watch.
• UVa 10703 - Free spots.
• UVa 10812 - Beat the Spread.
• UVa 10921 - Find the Telephone.
• UVa 11044 - Searching for Nessy.
• UVa 11150 - Cola.
• UVa 11223 - O: dah, dah, dah!.
• UVa 11340 - Newspaper.
• UVa 11498 - Division of Nlogonia.
• UVa 11547 - Automatic Answer.
• UVa 11616 - Roman Numerals.
• UVa 11727 - Cost Cutting.
• UVa 11800 - Determine the Shape.
• SPOJ HAM12 - Khoảng cách Hamming.
• SPOJ FIBVAL - Bản vanxơ Fibonacci.

Tài liệu tham khảo:
Steven Halim, Felix Halim - Competitive Programing - First Edition. National University of Singapore.
USACO Traning Gateway - Ad-hoc Problems.

Chia sẻ:

• Đề bài chuẩn ở đây tương ứng với đề thi ACM/ICPC. Đề chuẩn của các kỳ thi tin học ở cấp THPT hay Olympic tin học sinh viên gồm 3 bài. Riêng đối với thi học sinh giỏi Quốc gia thì có 2 đề, tương ứng với 6 bài thi. Những bài thuộc lớp bài toán đặc biệt thường rơi vào bài số 3 (bài khó nhất). Đôi khi, nó cũng xuất hiện ở bài đầu tiên, nhưng ở mức độ dễ.
• Các lớp bài toán có thể là: Đệ quy, NP, Quy hoạch động, các bài toán không giải được, ...