Bedao Regular Contest 09 - DEVIL

View as PDF

Submit solution


Points: 0.30 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Rimuru 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àngsố 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

Please read the guidelines before commenting.



  • -4
    t_huynn93   commented on Sept. 15, 2022, 9:11 p.m.

    int main() { iosbase::syncwith_stdio(0); cin.tie(NULL); cin >> n; int tem = sqrt(n);

    int ans = INT_MAX;
    Ford(i,tem,1) if(n%i==0) ans = min(ans,abs(i-n/i)) ;
    
    Ford(i,tem,2){
        if(i%2 == 1 ) if(n%i == 1+i/2 || n%i == i/2) ans = min(ans, abs(1 + n/i - i));
        if(i%2 == 0 ) if(n%i == i/2) ans = min(ans , abs(1+n/i - i));
    }
    ans = min(ans,n - 1);
    cout << ans <<"\n";
    return 0 ;
    

    } sai o dau the mn nhi


  • -5
    Kaiden   commented on Sept. 2, 2022, 11:08 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 0
      14362302   commented on Sept. 2, 2022, 6:34 p.m.

      Đổi thành fan Chelsea chứ


      • -1
        thongcoder1   commented on Sept. 7, 2022, 9:53 p.m.

        fan arsenal chứ


  • -5
    hypotheiss   commented on Aug. 30, 2022, 3:41 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.