Link Sub: http://www.spoj.com/PTIT/problems/P175SUME/
Người Gửi: Dương Lee
- Problem:
Do những ngày hè quá nóng bức và nhàm chán nên Tide đã nghĩ ra một trò chơi khá thú vị với queue. Ban đầu trong queue có 5 số 1, 2, 3, 4, 5 với mỗi lượt chơi Tide sẽ xóa phần tử ở đầu queue và cho 2 phần tử đó xuống cuối của queue và cứ tiếp tục cho đến khi Tide cảm thấy mệt và không chơi được nữa. Ví dụ tại lượt chơi thứ nhất trạng thái của queue là 1, 2, 3 ,4 ,5
Tại lượt chơi thứ 2 trạng thái của queue là 2, 3, 4, 5, 1, 1
Các bạn hãy giúp Tide xác định xem số đầu tiên của queue tại lượt chơi thứ N nhé.
Input
Gồm duy nhất số N (N<=10^9)
Output
Kết quả tìm được.
Example:
Kết quả tìm được.
Input
1
Output:
1
Input
6
Output:
1
- Solution:
Ở bài này chỉ cần quan tâm đến các thông số số đầu tiên là độ lặp số (Giải thích: mặc dù các dãy số theo quy luật nhưng nó chỉ xét đến các số đầu tiên của dãy nên chỉ cần biết số đầu tiên đó thuộc kiểu dãy nào là được)
Kiểu dạng duyệt được nó sẽ giống như: [1 2 3 4 5] [1 1 2 2 3 3 4 4 5 5] [1 1 1 2 2 2 ...
-> N=6 -> 1
-> N=1 -> 1
Cấu trúc: (data)
begin: 1; end: 5; index: 1 - tương ứng đại diện dãy loại 1: 1 2 3 4 5
begin: 6; end: 15; index: 2 - tương ứng đại diện với dãy loại 2: 1 1 2 2 3 3 4 4 5 5
...
tương tự như vậy... cho đến khi end > 10^9;
Sau khi cấu trúc xong và nhập N thì chỉ cần tìm xem N thuộc dãy loại nào?
VD: N=8 thuộc [6,15] -> dãy loại 2 (index=2) -> stt = N-6+1 = 3 -> thuộc số thứ 3 của dãy loại 2 -> KQ: 2 (Vì mỗi số sẽ có lượng số là = index chỉ cần xét riêng từng khoảng số là tìm được)Input
6
Output:
1