# MK Regular Round #1 Editorial
## DND - Dungeons and Dragons
### Hướng dẫn
Gọi $AddStr$ và $AddInt$ lần lượt là số điểm ta dùng để nâng $2$ chỉ số. Vì $AddStr+AddInt=Exp$ nên $AddInt=Exp-AddStr$. Từ đó, ta có bất phương trình:
$str+AddStr>int + Exp-AddStr$

$2AddStr>Exp+int-str$

$2AddStr\ge Exp+int-str+1$

$AddStr \ge \left \lceil \frac{Exp + int - str + 1}{2} \right \rceil$

Vì $AddStr$ có thể là số âm nên:

$AddStr \ge max(0,\left \lceil \frac{Exp + int - str + 1}{2} \right \rceil)$

$AddStr \ge max(0, \frac{Exp + int - str + 2}{2})$

$minAddStr$ là kết quả của $max(0, \frac{Exp + int - str + 2}{2})$. $AddStr$ sẽ thuộc $[minAddStr, Exp]$. Vậy nên số cách nâng sẽ là $max(0,Exp-minAddStr+1)$
### Cài đặt

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int a,b,c;
	cin>>a>>b>>c;
	int min=max(0,(b+c-a+2)/2);
	cout<<max(0,c-min+1);
	
	return 0;
}

## DRAGONFIGHT - Đánh rồng
### Hướng dẫn
Ta sẽ có hai trường hợp là có nâng sức mạnh cho hiệp sĩ đánh rồng hay không.

Nếu không nâng sức mạnh cho hiệp sĩ đánh rồng thì ta cần tìm được hiệp sĩ có sức mạnh $a_i \ge x$. Ta chọn hiệp sĩ có sức mạnh nhỏ nhất có thể trong các hiệp sĩ có sức mạnh lớn hơn hoặc bằng $x$. Sức mạnh của các hiệp sĩ còn lại sẽ là $\sum\limits_{j=1}^n a_j - a_i$. Vậy nên số đồng tiền cần dùng là $\max(0, y - (\sum\limits_{j=1}^n a_j - a_i))$.

Nếu nâng sức mạnh cho hiệp sĩ đánh rồng thì ta cần tìm được hiệp sĩ có sức mạnh $a_i<x$. Ta chọn hiệp sĩ có sức mạnh gần nhất với giá trị $x$. Vì vậy cần $x-a_i$ đồng tiền để nâng sức mạnh cho hiệp sĩ đánh rồng cộng thêm số đồng tiền để nâng sức mạnh cho các hiệp sĩ còn lại $\max(0, y - (\sum\limits_{j=1}^n a_j - a_i))$.

Ta dùng tìm kiếm nhị phân để tìm được giá trị $a_i$ gần với $x$.
### Cài đặt

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vector<long long> a;
	long long sum=0;
	for (int i=0;i<n;i++){
		long long x;
		cin>>x;
		a.push_back(x);
		sum+=x;
	}
	sort(a.begin(),a.end());
	long long x,y;
	cin>>x>>y;
	auto it=lower_bound(a.begin(),a.end(),x);
	long long ans=999999999999999;
	if (it!=a.end()){
		ans=min(ans,max(0LL,y-(sum-(*it))));
	}
	if (it!=a.begin()){
		ans=min(ans,max(0LL,y-(sum-(*(it-1))))+max(0LL,x-*(it-1)));
	}
	cout<<ans;
	
	return 0;
}

## BUS - Chuyến xe
### Hướng dẫn
Qua quan sát đề bài, ta có thể nghĩ ngay đến việc sử dụng cấu trúc dữ liệu Stack (ngăn xếp). Vì vậy, các bước giải sẽ như sau:

1. Sắp xếp lại mảng không giảm.
2. Mỗi một hành khách nhút nhát, đưa vào Stack vị trí mà hành khách ấy chọn.
3. Mỗi một hành khách cời mở, lấy ra khỏi Stack phần tử trên cùng.
### Cài đặt

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vector<pair<int,int>> a;
	string s;
	for (int i=0;i<n;i++){
		int x;
		cin>>x;
		a.push_back({x,i+1});
	}
	sort(a.begin(),a.end());
	stack<int> b;
	cin>>s;
	int j=0;
	for (int i=0;i<2*n;i++){
		if (s[i]=='0'){
			cout<<a[j].second<<" ";
			b.push(a[j].second);
			j++;
		}
		else{
			cout<<b.top()<<" ";
			b.pop();
		}
	}
	
	return 0;
}