[C10_HCM_PTNK_24] Số may mắn
Xem dạng PDFTrên bàn có một dãy các ô, các ô đánh số liên tiếp bắt đầu từ ~1~, từ trái sang phải. An có một bộ bài gồm ~n~ lá bài có số hiệu là ~1, 2, 3, ..., n~. Để chọn ra lá bài may mắn bạn An thực hiện các thao tác như sau:
Bước 1: An chia các lá bài hiện có vào các ô liên tiếp bắt đầu từ ô thứ nhất với số hiệu các lá bài theo thứ tự tăng dần.
Bước 2: An nhặt các lá bài trong các ô có số thứ tự chia cho ~3~ dư ~2~ và loại bỏ các lá bài còn lại trên dãy. Nếu số lá bài nhặt được nhiều hơn ~1~ thì quay lại thực hiện Bước ~1~. Trong trường hợp nhặt được đúng ~1~ lá bài thì lá bài đó là lá bài may mắn.
Ví dụ: Với ~n = 15~:
- Lần thứ nhất An sẽ chia các lá bài:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 - Lần thứ hai An sẽ chia các lá bài:
2 5 8 11 14 - Lần thứ ba An sẽ chia các lá bài:
5 14
Nhặt lá bài ~14~ là lá bài may mắn.
Yêu cầu
Cho biết ~n~, hãy tìm ra số hiệu của lá bài may mắn.
Dữ liệu đầu vào
Gồm một số nguyên dương ~n~ ~(2 \le n \le 10^9)~.
Dữ liệu đầu ra
Gồm một số nguyên dương duy nhất là số hiệu của lá bài may mắn.
Ràng buộc dữ liệu
- Có 50% số test với ~n \le 1000~.
- 50% số test còn lại không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
INPUT
15
OUTPUT
14
Bình luận
bảo + tài + đăng bel
thầy tuyên béo
hi