---
# System prepended metadata

title: 'MK Beginner Round #4'

---

# MK Beginner Round #4
## A - Nhân viên tổng đài
Người ra đề: HickWhither

Ta sẽ sử dụng mảng đếm để biết được số lần xuất hiện của mỗi phần tử trong mảng. 
### Code
```cpp    
#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007
#define BASEH1 31
#define ll long long
#define ld long double

int b[100000+10];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	int a[n+1];
	int ans=-1;
	int res=-1;
	for (int i=1;i<=n;i++){
		cin>>a[i];
		b[a[i]]++;
	}
	for (int i=0;i<=1e5+1;i++){
		if (b[i]>ans){
			ans=b[i];
			res=i;
		}
	}
	cout<<res;
}
```

## B - Lại là cấp số cộng
Người ra đề: Hnhat1234

Đây là một biến thể của bài toán dãy con tăng dài nhất.

$dp[x]$ : Cấp số cộng gồm nhiều phần tử nhất tính tới vị trí thứ $x$.
Và cuối cùng kết quả sẽ là phần tử lớn nhất trong mảng $dp$.
### Code 
```cpp
#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007
#define BASEH1 31
#define ll long long
#define ld long double

vector<int> f(100000+5,1);
int a[100000+5];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,d;
	cin>>n>>d;
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
	int ans=0;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=i-1;j++){
			if (a[i]-a[j]==d)	
                f[i]=max(f[i],f[j]+1);
		}
	}
	for (int i=1;i<=n;i++){
		ans=max(f[i],ans);
	}
	cout<<ans;
}
```
## C - Chia kẹo
Người ra đề: si23

Đề bài yêu cầu tìm $i + j + k = n$.

Vì $i < j < k$ mà $i + j + k = n$ $\rightarrow$ $i < n / 3$. Vậy ta sẽ duyệt $i$ từ $1 ... n / 3 - 1$. Biến đổi phương trình trên ta được $j + k = n - i$.

Bài toán quy về dạng tìm $a, b$ sao cho $a + b = x$,  tổng cộng có $x$ cặp như vậy. 

Nhưng đề bài yêu cầu $a < b$ nên ta sẽ loại bỏ hết các trường hợp $a > b$. Vì số trường hợp $a < b$ bằng số trường hợp $a > b$ nên ta sẽ chia $2$. Số cặp $a < b$ bằng số cặp $a > b$ vì cứ mỗi khi có một cặp $x, y$ thõa mãn, ta sẽ có thêm cặp $y, x$. Sau đó ta sẽ loại bỏ đi trường hợp $a = b$. Chỉ có một trường hợp là khi $x$ chẵn $\rightarrow$ $a = b = x / 2$, vậy khi $x$ chẵn ta sẽ trừ đi $1$.

Ngoài ra ta cần loại bỏ các trường hợp $j + k$ mà $j \le i$ $\rightarrow$ ta cần trừ thêm $i$ vào $t$ (có $i$ trường hợp $j \le i$).

### Code
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, ans(0);
    cin >> n;
    for (int i = 1; i < n / 3; ++i) {
        int t = (n - i) / 2;
        if (t % 2 == 0) t--;
        ans += max(t - i, 0);
    }
    cout << ans;
}
```