Editorial for Bedao Regular Contest 09 - DEVIL


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 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();
}

Comments

Please read the guidelines before commenting.



  • 4
    nguyenhuunhan  commented on Sept. 1, 2022, 4:51 p.m.

    Ở 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ỉ


    • 4
      bedao  commented on Sept. 6, 2022, 9:27 a.m.

      Bọn mình đã sửa lại, cảm ơn bạn đã góp ý