Mỗi thanh sô cô la có dạng thanh dài với kích thước 1 x n đơn vị, trên thanh sô cô la người ta xẻ các rãnh chia thanh sô cô la theo kích thước 1 x 1 cho dễ bẻ. Yêu cầu xác định: Có bao nhiêu cách bẻ thanh sô cô la theo các rãnh đã xẻ thành nhiều phần.

Ví dụ: thanh sô cô la chiều dài n = 3, ta có ba cách bẻ: Cách 1: bẻ thành 3 thanh độ dài 1: 1,2,3; Cách 2: bẻ thành 2 thanh, một thanh độ dài 2: 1-2 và một thanh độ dài 1 là 3 (cách bẻ 1, 2-3 coi như đã tính); Cách 3 là giữ nguyên cả thanh.

Dữ liệu vào: chứa duy nhất số nguyên n là chiều dài thanh sô cô la.

Dữ liệu ra: ghi số cách bẻ tìm được.

Giới hạn:   0 < n < 1001; Có 50% số test n < 31.

Nguồn: DHBB2012