Bedao Regular Contest 09 - DEVIL
View as 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 ~.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
Đổi thành fan Chelsea chứ
fan arsenal chứ
This comment is hidden due to too much negative feedback. Show it anyway.
tôi ce
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.