30/09/2018, 18:21

Cho e cách giải quyết bài này với .thank

Một người mỗi ngày phải uống đúng một nửa viên thuốc. Anh ta lấy ra từ lọ thuốc một viên ngẫu nhiên sau đó tách ra làm đôi, dùng một nửa rồi lại bỏ một nửa vào lọ. Hôm sau cũng vậy, nếu lấy ra ngẫu nhiên được một nửa viên thì dùng ngay, còn nếu lấy ra một viên còn nguyên thì lại tách làm đôi.

Giả sử mỗi lần lấy ra một viên nguyên thì ghi ra chữ W, nếu lấy ra một nửa viên thì ghi chữ H. Bài toán đặt ra là cho trước một số lượng viên thuốc trong lọ. Hãy xác định xem có bao nhiêu cách uống hết chỗ thuốc đó (tức là có bao nhiêu xâu ký tự khác nhau có thể được tạo ra).

Input
Gồm không quá 1000 bộ test, mỗi bộ test ghi số nguyên dương là số viên thuốc trong lọ (không quá 30). Dòng cuối cùng ghi số 0.

Output
ghi trên một dòng số nguyên dương là số cách khác nhau tìm được.

Gió viết 20:37 ngày 30/09/2018

Bạn coi w như dấu ( và h như ) sẽ trở thành bài toán đếm số cách hình thành dãy ngoặc đúng. Bài toán có liên quan đến catalan number https://en.m.wikipedia.org/wiki/Catalan_number

Bài liên quan
0