Nội dung Bài tập
- Mã:
- OLP17.SC3.PIROUETTE
- Tên:
- Xoay tròn
- Dạng thi:
- oi
- Thang điểm:
- 100 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Nguồn bài tập:
- Olympic tin học 2017
- Được tạo bởi:
- admin
Cho một số nguyên dương N và một căn phòng có chiều dài 2*N + 2 được xét như một đoạn thẳng đóng [-N-1, N+1]
Ban đầu vũ nữ ba lê Mathilde Froustey đứng ở điểm trung tâm C của căn phòng (C = 0). Cô ấy phải thực hiện T bước nhảy có độ dài 1, bước đầu tiên hướng về phía bên phải. Trong số 2*N điểm khác nhau có toạ độ nằm bên trong căn phòng có đánh dấu K điểm xoay khác nhau. Khi vũ nữ ba lê đạt đến một điểm xoay, cô sẽ dừng lại và thực hiện động tác xoay tròn. Động tác này sẽ làm thay đổi hướng di chuyển của vũ nữ, và điểm xoay ở điểm đó sẽ bị xóa bỏ.
Không được đặt điểm xoay nào tại các điểm với tọa độ -N-1, 0 và N + 1. Hơn nữa, do các điểm với tọa độ -N-1 và N + 1 là ở sát với tường của căn phòng nên chúng là các điểm xoay vĩnh cửu, nghĩa là chúng sẽ không bị xóa khi vũ nữ di chuyển qua, còn điểm với tọa độ C = 0 là vị trí xuất phát của Mathilde (xem hình vẽ minh họa ở trên).
Yêu cầu: Cho các giá trị của T, N và K, hãy tính xem có bao nhiêu cách đánh dấu K điểm xoay khác nhau để sau khi thực hiện đúng T bước di chuyển, Mathilde quay trở về điểm bắt đầu C.
Dữ liệu: gồm một dòng chứa ba số nguyên T, N và K được ghi cách nhau bởi dấu cách có ý nghĩa như đã nêu ở trên (0 ≤ T ≤ 200; 1 ≤ N ≤ 100; 0 ≤ K ≤ 2*N).
Kết quả: xuất một số nguyên là phần dư trong phép chia của giá trị tìm được cho 1000000007 (109+7).
Ví dụ:
Input Output
Giải thích: Vũ nữ phải thực hiện T = 6 bước nhảy trong căn phòng dạng đoạn thẳng độ dài 2*N + 2 = 2*3 + 2 = 8, và phải di chuyển qua K = 4 điểm xoay. Có 7 cách đặt điểm xoay thỏa mãn yêu cầu đầu bài:
Ký hiệu '.' là vị trí tự do, 'x' là vị trí có điểm xoay, còn 'C' là vị trí xuất phát
Xoay tròn (Pirouette): Là một động tác trong múa ba lê đòi hỏi vũ công thực hiện xoay vòng toàn thân trên ngón chân hoặc bàn chân.
Mathilde Froustey với biệt danh "cô bé Pháp" - vũ công ballet nổi tiếng thế giới có bà ngoại là người gốc Việt. Cô đã từng biểu diễn ở Việt nam năm 2016, trước đó năm 2008 cô đã có 3 tháng du lịch ở Việt nam.
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <bits/stdc++.h>using namespace std;int main(){ int a1,a2,a3,b1...