Bedao Regular Contest 09 - DEVIL
Xem dạng PDFRimuru vừa được isekai đến thế giới mới. Trong chuyến phiêu lưu vào hang của ~fan MU~, Rimuru gặp Veldora tempest và muốn cậu ta hòa vào trong cơ thể của mình. Để chứng minh mình có đủ trình để mang rồng Veldora ra khỏi hang của những con quỷ đỏ Rimuru được Veldora thử thách một bài toán:
Được biết chênh lệch giữa 2 số ~a~ và ~b~ là ~|a-b|~, ta cần xếp ~N~ con slime vào các hàng sao cho :
- Chênh lệch số slime giữa 2 hàng liên tiếp đều bằng ~0~ hoặc đều bằng ~1~.
- Chênh lệch số slime giữa 2 hàng bất kỳ không vượt quá ~1~.
Lưu ý : Ta có thể chia tất cả ~N~ con slime vào 1 hàng và cách chia này luôn đúng.
Với mỗi cách xếp, ta gọi tempest của cách xếp đó là chênh lệch giữa số slime nhiều nhất của ~1~ hàng và số hàng của cách xếp đó. Bạn hãy giúp Rimuru hấp thụ Veldora tempest và thoát khỏi hang ~MU~ bằng cách tính tempest nhỏ nhất trong tất cả các cách chia ~N~ con slime.
Input
Gồm ~1~ dòng chứa số nguyên dương ~N~ ~(1 \le N \le 10^{12})~.
Output
In ra kết quả là tempest nhỏ nhất có thể.
Subtask
- ~20\%~ số test có ~N \le 10^{3}~.
- ~30\%~ số test tiếp theo có ~N \le 10^{6}~.
- ~50\%~ số test còn lại không có điều kiện gì thêm.
Sample Input
6
Sample Output
1
Note
Ta chia các con slime thành ~2~ hàng :
- Hàng đầu có ~3~ con slime.
- Hàng thứ nhì có ~3~ con slime.
- Vậy tempest ~= 3 - 2 ~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Đổi thành fan Chelsea chứ
fan arsenal chứ
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
tôi ce
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.