Hướng dẫn giải của Bedao Regular Contest 09 - DEVIL
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả: bedao
Ta dễ thấy với tất cả các hàng có số slime bằng nhau cách chia có dạng là ~i \times j~ với ~i~ là số slime trên một hàng và ~j~ là số hàng. Dễ thấy khi ~i~ vượt qua ~\sqrt{n}~ thì cặp ~i , j~ lặp lại nên ta chỉ cần duyệt trâu số hàng ~j~ rồi tìm ~i~ tương ứng sao cho ~i \times j = n~ là được.
Trường hợp còn lại của bài, cũng gọi ~i , j~ như trên nhưng lần này đặt biệt hơn ~i~ là số slime bé nhất trên một hàng (nên theo đề bài số slime lớn nhất là ~i + 1~) .Vì chênh lệch số slime giữa ~2~ hàng bất kỳ không vượt quá ~1~ nên ta có hai trường hợp đặt ra:
- Hàng chẵn có số slime là ~i + 1~ , hàng lẻ có số slime là ~i~.
- Hàng chẵn có số slime là ~i~ , hàng lẻ có số slime là ~i + 1~.
~\rightarrow~ Nếu ~j~ chẵn thì hai trường hợp tương đương nhau, nhưng ~j~ lẻ thì khác. Cách làm, tính chất tương tự như số slime bằng nhau nhưng cần biến tấu hơn.
Code mẫu
#include <bits/stdc++.h> #define int long long #define ii pair<int,int> #define nd second #define st first #define endl "\n" using namespace std; const int MAXN = 1e5 + 5; const int MAXX = 1e7 + 5; int n, last[MAXN], pre[MAXN][30], ans = 1e18; string s; void Min(int &x, int y){ if (x > y) x = y; } void program(){ cin >> n; for (int i = 1; i <= min(n, MAXX); i++) { if (n % i == 0) { int x = abs(n / i - i); Min(ans, x); } else { int x = abs(i - n / i - 1); if ((i & 1) && (n % i == i / 2 || n % i == (i / 2 + 1))) { Min(ans, x); } if (!(i & 1) && n % i == i / 2) { Min(ans, x); } } } cout << ans; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int test = 1; while (test--) program(); }
Bình luận
Ở chỗ "Nếu i chẵn thì hai trường hợp tương đương nhau , nhưng i lẻ thì khác." hình như phải là j mới đúng chứ nhỉ
Bọn mình đã sửa lại, cảm ơn bạn đã góp ý