C11XOA - Xoa day
Giới hạn- Thời gian: 1.5s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Songuku95 đố hgminh95 một bài toán như sau:
Xếp n củ Carrot trên một hình tròn ( các củ carrot được đánh số từ 1 -> n)
Khánh lấy n đoạn dây buộc 2 củ carrot liên tiếp lại (Cử 1 buộc với củ 2, củ 2 buộc với củ 3, …, củ n-1 buộc với cử n, củ n buộc với củ 1)
Bây giờ Songuku95 đố HgMinh95 bỏ một vài đoạn dây nối đi sao cho mỗi củ carrot còn ít nhất 1 đoạn dây nối. H gMinh95 thông minh vốn sẵn tính trời nên việc này hoàn toàn là đơn giản với HgMinh95 (Thực chất chả bỏ dây nào cũng đã đúng rồi :3)
Cơ mà sau đấy, Songuku95 lại thách HgMinh95 đếm số cách bỏ một vài đoạn dây để vẫn thỏa mãn “mỗi củ carrot còn ít nhất 1 đoạn dây nối”. Bài toán này làm hgminh trằn trọc suy nghĩ suốt nhiều ngày liền. Vì quá khó nên HgMinh95 đã nhờ đến sự cứu trợ từ người không quen (hoặc quen) :))
Các bạn hãy giúp HgMinh95 bài toán này nhé.
Input
Cho số test là T (t <= 5)
T dòng tiếp theo chứa T số nguyên N (3 <= N <= 50000)
Output
Gồm T dòng
Dòng thứ i in ra số R = số cách bỏ một vài đoạn dây sao cho mỗi củ carrot vẫn còn ít nhất 1 dây nói đến nó.
Example
Input: 2 3 6 Output: 4 18
Giải thích
N=3. Có 4 cách xóa: Không xóa cạnh nào, xóa cạnh 1-2, xóa cạnh 2-3, xóa cạnh 3-1
Giới hạn
20% số test có N <= 25
- Người up: songuku95