---
# System prepended metadata

title: 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$ <span style="font-size: 20px;">$S_1=\frac{K\times(K+1)}{2}$</span>

$\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$ <span style="font-size: 20px;">$A= \frac{K^2\times(K+1)}{2} + (0\times 1 + 1 \times 2 + .... + K\times (K-1))$ 
</span>
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)$

<span style="font-size: 30px;"></span>$\Longleftrightarrow$ <span style="font-size: 20px;">$B=\frac{(K-1) \times K \times (K + 1)}{3}$</span>

$\Longleftrightarrow$ <span style="font-size: 20px;">$A=\frac{K^2\times(K+1)}{2} + \frac{(K-1) \times K \times (K + 1)}{3}$
</span>
Rồi ta quay lại thế $A$ và $S$,ta được
<span style="font-size: 20px;">$S=\frac{K\times(K+1)}{2}-1 + \frac{K^2\times(K+1)}{2} + \frac{(K-1) \times K \times (K + 1)}{3}$</span>

$\Longleftrightarrow$ <span style="font-size: 20px;">$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}$</span>

$\Longleftrightarrow$ <span style="font-size: 20px;">$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}$</span>

$\Longleftrightarrow$ <span style="font-size: 20px;">$S=\frac{K\times (K+1)\times (3\times K - 2\times (K-1) + 3)-6}{6}$</span>

$\Longleftrightarrow$ <span style="font-size: 20px;">$S=\frac{K\times (K+1)\times (K+5)-6}{6}$</span>


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;
}
```
:::