Free Contest 67 - DIKE

# Free Contest 67 - DIKE **Lời giải** : _Nguyễn Phú Vinh_ (THPT Quang Trung) ## Đề bài Các bạn hãy để đọc qua đề bài và nghĩ thử ở [đây](https://oj.vnoi.info/problem/fc067_dike) Có bạn nào đọc xong mà vẫn không hiểu đề không Thực sự lúc mới đọc đề mình cũng không hiểu đề nó nói gì.Nhưng ở đây,ta cần một chút đọc hiểu để có thể hiểu bài này **Tóm tắt đề:** Bạn hãy nhìn vào ảnh này: ![image](https://hackmd.io/_uploads/S1OmOf1jA.png) Đoạn dài màu trắng chính là độ dài cửa vịnh,các ô màu đỏ là chính là các đoạn thả nhím biển và các đoạn màu xanh là các ô được bỏ trống Các ô có độ dài là được quy định như sau: có $1$ đoạn độ dài $K$ ô, $2$ đoạn độ dài $K − 1$ ô, $3$ đoạn độ dài $K − 2$ ô,..., $K$ đoạn độ dài $1$ ô Ví dụ như trong ảnh dưới: ![image](https://hackmd.io/_uploads/BJPUsGyoC.png) Với $K=1$ thì có $1$ ô độ dài $1$ Với $K=2$ thì có $1$ ô độ dài $2$ và $2$ ô độ dài $1$ Với $K=3$ thì có $1$ ô độ dài $3$, $2$ ô độ dài $2$ và 3 ô độ dài $1$ Ta có thể thấy nếu $K$ quá lớn thì tổng độ dài các ô sẽ vượt quá $n$.Vậy nhiệm vụ của ta bây giờ là tìm $K$ lớn nhất để tổng độ dài các ô sẽ vượt quá $n$ ## Lời giải Ta có nhận xét như sau: Nếu là $K$ càng lớn thì càng không thoả mãn $\Longrightarrow$ Ta sẽ chặt nhị phân bài này Để chặt được bài này,ta cần tính được tổng độ dài với từng $K$ Bắt đầu ở đề bài ta được biểu thức $A=1 \times K + 2 \times (K-1) + 3\times(K-2) +...+ K \times 1$ là tổng độ dài của các ô chứa nhím Và để tính tổng số ô thì ta cần tính thêm các ô trống nữa Tiếp tục dựa vào đề bài,đề bài cho ta các khoảng trống giữa 2 ô là ít nhất là một,nhưng ta để $K$ tối đa,ta sẽ chỉ cho đoạn ô trống là $1$ vậy tổng độ dài của các ô trống bằng bao nhiêu nhỉ? **Ví dụ**,$K=3$ ![image](https://hackmd.io/_uploads/Bk5IRG1sA.png) Ta thấy có 6 ô thả nhím và có 5 ô trống,tổng số ô trống này là $5$ Hay bạn có thể luận ra ngay là: **tổng số ô trống** $=$ **số lượng ố trống** $=$ **số lượng ô thả nhím $-1$** Vậy giờ ta cần tìm số lượng ô thả nhím nữa là được Lại nhìn vào ảnh trên,có $1$ ô độ dài $3$,$2$ ô độ dài $2$ và $3$ ô độ dài $1$. Bạn có nhận ra điều gì ở đây không? Số lượng các ô tăng theo cấp số cộng,với công sai $d=1$ Hay số lượng ô chính là tổng của dãy $S_1=1+2+3+4+...+K$ Áp dụng công thức Faulhaber( bạn có thể tham khảo ở [đây](https://vi.wikipedia.org/wiki/C%C3%B4ng_th%E1%BB%A9c_Faulhaber)) $\Longrightarrow$ $S_1=\frac{K\times(K+1)}{2}$ $\Longrightarrow$ tổng độ dài của các ô $S= A + S_1-1= A +\frac{K\times(K+1)}{2}-1$ Ở đây $S_1-1$ đã là công thức có thể tính trong $O(1)$ Bây giờ ta cần biến đổi cái $A$ để cũng có thể tính trong $O(1)$ $A=1 \times K + 2 \times (K-1) + 3\times(K-2) +...+ K \times 1$ **Ta có:** $1 \times K = K\times K - K\times (K-1)$ $2 \times (K-1) = K\times(K-1) - (K-1)\times(K-2)$ $...........$ $K \times 1 = K \times 1 - 1 \times 0$ Gộp hết lại,ta được $A = K \times S_1 + (0\times 1 + 1 \times 2 + .... + K\times (K-1))$ $\Longleftrightarrow$ $A= \frac{K^2\times(K+1)}{2} + (0\times 1 + 1 \times 2 + .... + K\times (K-1))$ Bây giờ trong $A$ cái đám $\frac{K^2\times(K+1)}{2}$ đã có thể tính trong $O(1)$ còn đám $0\times 1 + 1 \times 2 + .... + K\times (K-1)$ thì ta phải biến đổi tiếp Đặt $B=0\times 1 + 1 \times 2 + .... + K\times (K-1)$ $\Longleftrightarrow$ $3\times B =3 \times 0\times 1 + 3\times 1 \times 2 +3\times 2 \times 3 .... + 3\times K\times (K-1)$ $\Longleftrightarrow$ $3\times B =1 \times 2 \times (3-0)+2 \times 3 \times (4 - 1) + ..... + (K-1) \times K \times [(K+1) - (K-2)]$ $\Longleftrightarrow$ $3\times B = -0\times 1 \times 2 + 1 \times 2\times 3 - 1 \times 2 \times 3 + 2 \times 3\times 4 - 2 \times 3 \times 4 + .... + (K-1) \times K \times (K + 1)$ $\Longleftrightarrow$ $3 \times B=(K-1) \times K \times (K + 1)$ $\Longleftrightarrow$ $B=\frac{(K-1) \times K \times (K + 1)}{3}$ $\Longleftrightarrow$ $A=\frac{K^2\times(K+1)}{2} + \frac{(K-1) \times K \times (K + 1)}{3}$ Rồi ta quay lại thế $A$ và $S$,ta được $S=\frac{K\times(K+1)}{2}-1 + \frac{K^2\times(K+1)}{2} + \frac{(K-1) \times K \times (K + 1)}{3}$ $\Longleftrightarrow$ $S=\frac{3 \times K\times(K+1)}{6} + \frac{3 \times K^2\times(K+1)}{6} + \frac{2 \times (K-1) \times K \times (K + 1)}{6} -\frac{6}{6}$ $\Longleftrightarrow$ $S=\frac{3\times k\times(k+1) + 3 \times K^2\times(K+1) + 2 \times (K-1) \times K \times (K + 1) - 6}{6}$ $\Longleftrightarrow$ $S=\frac{K\times (K+1)\times (3\times K - 2\times (K-1) + 3)-6}{6}$ $\Longleftrightarrow$ $S=\frac{K\times (K+1)\times (K+5)-6}{6}$ Và đến đây các bạn chặt như bình thường **Code cho các bạn tham khảo:** :::spoiler ```cpp=1 #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define el cout<<"\n" #define sz(x) (int)(x).size() #define all(x) (x).begin(),(x).end() #define f0(i,n) for(int i=0;i<n;i++) #define f1(i,n) for(int i=1;i<=n;i++) #define pll pair<ll,pair<ll,ll>> #define faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file(name) if(fopen(name".inp","r")){freopen(name".INP","r",stdin);freopen(name".OUT","w",stdout);} const int MAXN = 1e6+5; const int mod =1e9+7; int main(){ faster; file(); ll n;cin>>n; int l=0,r=2e6; while(r-l>1){ int mid=l+r>>1; if((1ll*mid*(mid+1)*(mid+5)-6)/6 <= n) l=mid; else r=mid; } cout<<l; } ``` :::