## VQ44_FLOWERS
- Đề bài
- Hướng giải
Chọn các loại đèn khác nhau, sau đó chọn đèn có tuần suất xuất hiện nhiều nhất.
- Code

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, k;
    cin>>n>>k;
    unordered_map<int, int> mp;
    set<int> a;
    for (int i = 0; i < n; i++) {
    	int tmp;
        cin >> tmp;
        mp[tmp]++; 
        a.insert(tmp);
    }
    priority_queue<pair<int, int>> pq;
    for (pair<int,int> i:mp) {
        pq.push({i.second, i.first});
    }
    vector<int> res(a.begin(),a.end());
    if(res.size()>=k){
    	int cnt = 0;
    	for(int i:res){
    		cnt++;
    		cout<<i<<" ";
    		if(cnt==k)return 0;
		}
	}
    while (res.size()<k) {
        pair<int,int> i = pq.top();
		pq.pop();
        res.push_back(i.second);
        i.first--;
        if (i.first > 0) pq.push({i.first, i.second});
    }
    sort(res.begin(), res.end());
    for (int i:res)cout<<i<<" ";
}

## Point2D
- Đề bài
- Hướng giải
Lưu các giá trị y theo x. Sau đó sort giảm dần theo arr[x].
- Code

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	unordered_map<int,vector<int>> arr;
	set<int> un;
	for(int i = 0; i < n; i++){
		int tm1,tm2;
		cin>>tm1>>tm2;
		arr[tm1].push_back(tm2);
		un.insert(tm1);
	}
	for(int i : un){
		sort(arr[i].rbegin(),arr[i].rend());
		for(int j : arr[i]){
			cout<<i<<" "<<j<<"\n";
		}
	}
}

## VS14_Gifts
- Đề bài
- Hướng giải
Áp dụng kĩ thuật 2 con trỏ để tìm cặp số lớn nhất bé hơn k.
- Code

#include<bits/stdc++.h>
using namespace std;
int n,x,mx=0;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>x;
	vector<int> arr;
	for(int i = 0; i < n; i++){
		int tm;
		cin>>tm;
		arr.push_back(tm);
	}
	sort(arr.begin(),arr.end());
	int l=0,r=n-1;
	while(l!=r){
		int sum = arr[l] + arr[r];
		if(sum<=x){
			mx = max(sum,mx);
			l++;
		}else{
			r--;
		}
	}
	cout<<mx;
}

## PasswordStrength
- Đề bài
- Hướng giải
Đặt điều kiện theo các công thức của đề bài.
- Code

#include<bits/stdc++.h>
using namespace std;
bool checkKoHopLe(char i){
	return (i=='.'||i=='\\'||i=='/'||i==' '||i==',');
}
bool checkChuHoa(char i){
	return (i>='a'&&i<='Z');
}
bool checkKyTu(char i){
	return (i=='!'||i=='@'||i=='#'||i=='$'||
			i=='%'||i=='^'||i=='&'||i=='*'||
			i=='?'||i=='_'||i=='~');
}
bool checkChuSo(char i){
	return (i>='0'&&i<='9');
}
bool checkChuThuong(char i){
	return (i>='a'&&i<='z');
}
int main(){
	string a;
	cin>>a;
	if(a.size()<8){
		cout<<"KhongHopLe";
		return 0;
	}
	vector<bool> combo(3); //0:chu hoa, 1:ky tu dac biet, 2:chu so
	int BaseScore = 40, Bonus_Excess = 3, Bonus_Upper = 4, Bonus_Number = 5, Bonus_Symbols = 5;
	int Bonus_Combo=0,Bonus_FlatLower=0,Bonus_FlatNumber=0,
		Number_Execess=0,Number_Upper=0,Number_Numbers=0,Number_Symbols=0;
	bool thuong = false;
	for(char i : a){
		if(checkKoHopLe(i)){
			cout<<"KhongHopLe";
			return 0;
		}
		if(checkChuHoa(i)){
			combo[0]=true;
			Number_Upper++;
		}
		if(checkKyTu(i)){
			combo[1]=true;
			Number_Symbols++;
		}
		if(checkChuSo(i)){
			combo[2]=true;
			Number_Numbers++;
		}
		if(checkChuThuong(i)){
			thuong=true;
		}
	}
	
	int cntCombo=0;
	for(bool i:combo)if(i)cntCombo++;
	if(cntCombo==2)Bonus_Combo=15;
	if(cntCombo==3)Bonus_Combo=25;
		
	if(!combo[0]&&!combo[1]&&!combo[2])Bonus_FlatLower=-15;
	
	if(!combo[0]&&!combo[1]&&combo[2]&&!thuong)Bonus_FlatNumber=-35;

	Number_Execess=a.size()-8;
	
	int score = BaseScore 
				+ Number_Execess*Bonus_Excess 
				+ Number_Upper*Bonus_Upper 
				+ Number_Numbers*Bonus_Number 
				+ Number_Symbols*Bonus_Symbols 
				+ Bonus_Combo + Bonus_FlatLower + Bonus_FlatNumber;

	if(score<50)cout<<"Yeu";
	if(score>=50&&score<75)cout<<"Vua";
	if(score>=75&&score<100)cout<<"Manh";
	if(score>=100)cout<<"RatManh";
}

## CaesarCipher
- Đề bài
- Hướng giải
Giải theo công thức trong đề bài.
- Code

#include<bits/stdc++.h>
using namespace std;
int n;
char caesarCipher(char c,int k){
	return (c-'A'+k)%26+'A';
}
int main(){
	cin>>n;
	string a;
    cin.ignore();
	getline(cin,a);
	for(char i : a){
		if(i>='A'&&i<='Z')cout<<caesarCipher(i,n);
		else cout<<" ";
	}
}

## ReversingEncryption
- Đề bài
- Hướng giải
Theo công thức trên đề bài, ta duyệt tất ước d theo thứ tự giảm dần, sau đó đảo ngược chuỗi từ vị trí 1 -> d. Vậy ta chỉ cần làm ngược đề bài,
- Code

#include<bits/stdc++.h>
using namespace std;
int main(){
	string a;
	cin>>a;
    int n = a.size();
	for(int i = 1; i <= n; i++){
		if(n%i==0)reverse(a.begin(), a.begin()+i);
	}
	cout<<a;
}

## Messages
- Đề bài
- Hướng giải
Tìm a trong b, nếu không tìm được thì bỏ vị trí đầu tiên của a.
- Code

#include<bits/stdc++.h>
using namespace std;
string a,b;
int main(){
	cin>>a>>b;
	string tm=a;
	int index = 1;
	while(index){
		index = b.find(tm);
		if(!index){
			a+=b.substr(tm.size());
			break;
		}else{
			tm.erase(0,1);
		}
	}
	cout<<a.size()<<"\n"<<a;
}

## Binary Search 1
- Đề bài
- Hướng giải
Đếm mỗi giá trị pivot đi qua.
- Code

#include<bits/stdc++.h>
using namespace std;
int n,cnt=0;
vector<int> arr;
int binarySearch(int a){
	int l=0,r=n-1;
	while(l<=r){
		int pivot=(l+r)>>1;
		cnt++;
		if(arr[pivot]==a){
			return pivot;
		}
		if(arr[pivot]>a)r=pivot-1;
		else l=pivot+1;
	}
	return -1;
}
int main(){
	cin>>n;
	int index=0;
	for(int i = 0; i < n; i++){
		int temp;
		cin>>temp;
		arr.push_back(temp);
	}
	cin>>index;
	int res = binarySearch(index);
	if(res==-1)cout<<-1;
	else{
		cout<<res<<"\n";
		cout<<cnt;
	} 
}

## Binary Search 2
- Đề bài
- Hướng giải
Vì mảng này được sắp xếp theo từ điển, nên chúng ta vẫn có thể sử dụng binary search để tìm vị trí.
- Code

#include<bits/stdc++.h>
using namespace std;
int n,cnt=0;
vector<string> arr;
int binarySearch(string a){
	int l=0,r=n-1;
	while(l<=r){
		int pivot=(l+r)>>1;
		cnt++;
		if(arr[pivot]==a){
			return pivot;
		}
		if(arr[pivot]>a)r=pivot-1;
		else l=pivot+1;
	}
	return -1;
}
int main(){
	cin>>n;
	string index;
	for(int i = 0; i < n; i++){
		string temp;
		cin>>temp;
		arr.push_back(temp);
	}
	cin>>index;
	int res = binarySearch(index);
	if(res==-1)cout<<-1;
	else{
		cout<<res<<"\n";
		cout<<cnt;
	} 
}

## Linear Search 1
- Đề bài
- Hướng giải
Truy cập tới tất cả các giá trị trong mảng.
- Code

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> arr;
int linearSearch(int a){
	for(int i = 0; i < n; i++){
		if(arr[i]==a){
			cout<<i<<"\n";
			cout<<i+1<<"\n";
			break;
		}
	}
	int cnt = 0;
	for(int i = n-1; i>=0; i--){
		cnt++;
		if(arr[i]==a){
			cout<<cnt-1<<"\n";
			cout<<cnt<<"\n";
			return 0;
		}
	}
	return -1;
}
int main(){
	cin>>n;
	int index=0;
	for(int i = 0; i < n; i++){
		int temp;
		cin>>temp;
		arr.push_back(temp);
	}
	cin>>index;
	if(linearSearch(index)==-1)cout<<-1;
}

## Linear Search 2
- Đề bài
- Hướng giải
Duyệt tất cả giá trị trong mảng, và lưu vị trí và sô lần duyệt vào mảng. Vị trí lẻ trong mảng là vị trí và số chẵn là số lần duyệt, tổng số phần tử chia 2 là số phần tử.
- Code

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> arr,res;
int linearSearch(int a){
	int cnt = 0;
	for(int i = 0; i < n; i++){
		if(arr[i]==a){
			res.push_back(i);
			res.push_back(i+1);
		}
	}
	return res.size();
}
int main(){
	cin>>n;
	int index=0;
	for(int i = 0; i < n; i++){
		int temp;
		cin>>temp;
		arr.push_back(temp);
	}
	cin>>index;
	cout<<linearSearch(index)/2<<"\n";
	int cnt = 0;
	for(int i:res){
		if(cnt%2)
		cout<<i<<"\n";
		else
		cout<<i<<" ";
		cnt++;
	}
}

## Linear Search 3
- Đề bài
- Hướng giải
Khi nhập 1 số thì số đó sẽ được đánh dấu lại. Sau đó tăng dần số cho tới khi nào gặp số chưa được đánh dấu.
- Code

#include<bits/stdc++.h>
using namespace std;
int n,res=0;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	vector<bool> check(2*1000001);
	for(int i = 0; i < n; i++){
		int temp;
		cin>>temp;
		check[temp]=true;
		while(check[res])res++;
		cout<<res<<" ";
	}
}

## Linear Search 5
- Đề bài
- Hướng giải
Sort mảng, sau đó lấy 2 đầu của mảng trừ nhau.
- Code

#include<bits/stdc++.h>
using namespace std;
void run(){
	int n;
	cin>>n;
	vector<int> arr;
	for(int i = 0; i < n; i++){
		int tm;
		cin>>tm;
		arr.push_back(tm);
	}
	sort(arr.begin(),arr.end());
	int sum1=arr[n-1]-arr[0],sum2 = (arr.size()>3)?arr[n-2]-arr[1]:0;
	if(arr.size()==2)cout<<sum1<<"\n";
	else cout<<sum1+sum2<<"\n";
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	for(int i = 0; i < t; i++)run();
}

## VW05p_Enrichement
- Đề bài
- Hướng giải
Đếm mỗi 3x3 mỗi phần tử trong mảng 2 chiều.
- Code

#include<bits/stdc++.h>
using namespace std;
int n,m,mn=INT_MAX;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	vector<vector<int>> arr(n,vector<int>(m));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin>>arr[i][j];
		}
	}
	for(int i = 1; i < n-1; i++){
		for(int j = 1; j < m-1; j++){
			int sum = arr[i-1][j-1] + arr[i-1][j] + arr[i-1][j+1] 
					+ arr[i][j-1] + arr[i][j] + arr[i][j+1] 
					+ arr[i+1][j-1] + arr[i+1][j] + arr[i+1][j+1];
			mn=min(mn,sum);
		}
	}
	cout<<mn;
}

## BÀI KIỂM TRA
**Đề bài**

**Hướng giải**
1. Mỗi học sinh được đánh số từ 1 đến `n` theo thứ tự phát đề: bàn 1 vị trí 1 → bàn 1 vị trí 2 → bàn 2 vị trí 1 → ...
2. Ta quy đổi vị trí `(p, q)` của Alice thành chỉ số `alice_index = (p - 1) * 2 + q`.
3. Giả sử đề phát theo chu kỳ `1 → 2 → ... → k → 1 → ...`, nên nếu Bob có cùng đề với Alice thì chỉ số Bob phải cách `alice_index` đúng bội số của `k`.
4. Xét hai trường hợp:
- `alice_index - k` còn trong khoảng `1..n`: ưu tiên chọn vì gần Alice hơn.
- Nếu không, thử `alice_index + k`.
- Nếu cả hai đều không hợp lệ thì in `-1`.

- **Code**

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k, p, q;
    cin >> n >> k >> p >> q;
    
    int alice = (p - 1) * 2 + q;
    
    if (alice - k > 0) {
        int bob = alice - k;
        cout << (bob + 1) / 2 << " " << (bob % 2 == 0 ? 2 : 1);
    }
    else if (alice + k <= n) {
        int bob = alice + k;
        cout << (bob + 1) / 2 << " " << (bob % 2 == 0 ? 2 : 1);
    }
    else cout << -1;
}

## an.512.Trộn 2 mảng
**Đề bài**

**Hướng giải**
1. Đây là bài toán cơ bản trong kỹ thuật Merge Sort: trộn hai mảng đã sắp sẵn.
2. Duyệt song song cả hai mảng `A` và `B`:
- Nếu `A[i] <= B[j]` thì lấy `A[i]`, ngược lại lấy `B[j]`.
- Khi một mảng đã hết, sao chép phần còn lại của mảng kia vào.
3. Làm lần lượt cho từng test case.

- **Code**

#include <bits/stdc++.h>
using namespace std;

void merge(int *a, int n, int *b, int m, int *c) {
    int i = 0, j = 0, k = 0;
    while (i < n && j < m) {
        if (a[i] <= b[j]) c[k++] = a[i++];
        else c[k++] = b[j++];
    }
    while (i < n) c[k++] = a[i++];
    while (j < m) c[k++] = b[j++];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        int *a = new int[n];
        int *b = new int[m];
        int *c = new int[n + m];
        
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < m; i++) cin >> b[i];
        
        merge(a, n, b, m, c);
        
        for (int i = 0; i < n + m; i++) cout << c[i] << " ";
        cout << "\n";
        
        delete[] a;
        delete[] b;
        delete[] c;
    }
    return 0;
}

## Point3D
- **Đề bài**

- **Hướng giải**
1. Ta lưu tất cả các điểm vào một mảng hoặc vector struct `Point`.
2. Viết hàm so sánh (`cmp`) để sắp xếp theo thứ tự:
- `x` tăng dần
- Nếu `x` bằng, `y` giảm dần
- Nếu `x` và `y` bằng, `z` tăng dần
3. Dùng thuật toán QuickSort tự cài để sắp xếp với điều kiện trên.
(Lý do dùng QuickSort tự cài có thể là yêu cầu tối ưu hiệu năng hoặc tránh dùng `sort()` trong thư viện)

- **Code**

#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x, y, z;
};

bool cmp(const Point &a, const Point &b) {
    if (a.x != b.x) return a.x < b.x;
    if (a.y != b.y) return a.y > b.y;
    return a.z < b.z;
}

void swap(Point &a, Point &b) {
    Point temp = a;
    a = b;
    b = temp;
}

int partition(vector<Point> &arr, int low, int high) {
    Point pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (cmp(arr[j], pivot)) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<Point> &arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<Point> a(n);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y >> a[i].z;
    }

    quickSort(a, 0, n - 1);

    for (auto &i : a) {
        cout << i.x << " " << i.y << " " << i.z << "\n";
    }

    return 0;
}

## TÌM MEX CỦA MẢNG
- **Đề bài**

- **Hướng giải**
1. Vì `ai ≤ 10^9` nhưng `N ≤ 10^5`, ta không thể dùng mảng đánh dấu từ `0` đến `10^9` ⇒ tối ưu chỉ cần kiểm tra từ `0 → N` là đủ.
2. Dùng mảng `check[0...N]` kiểu `bool` để đánh dấu sự xuất hiện của các số từ `0 → N`.
3. Duyệt mảng gốc:
- Nếu phần tử `a[i] ≤ N`, đánh dấu `check[a[i]] = true`.
- Nếu `a[i] > N`, bỏ qua vì không ảnh hưởng đến MEX trong khoảng `0 → N`.
4. Duyệt từ `0 → N`, in ra số đầu tiên chưa được đánh dấu.
5. Nếu không tìm được, nghĩa là tất cả từ `0 → N` đều có ⇒ MEX là `N + 1`.

- **Code**

#include <bits/stdc++.h>
using namespace std;

int n;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    int temp;
    vector<bool> check(n + 1);

    for (int i = 0; i < n; i++) {
        cin >> temp;
        if (temp <= n) check[temp] = true;
    }

    for (int i = 0; i <= n; i++) {
        if (!check[i]) {
            cout << i;
            return 0;
        }
    }

    cout << n + 1;
    return 0;
}

## Point2D (template)
- **Đề bài**

- **Hướng giải**
1. Dữ liệu có thể lên đến `10^6` điểm ⇒ cần thuật toán sắp xếp hiệu quả như QuickSort, MergeSort, hoặc STL `sort`.
2. Sử dụng cấu trúc `pair<int, int>` để lưu điểm `(x, y)`.
3. So sánh 2 điểm:
- Nếu `x1 < x2` thì `p1 < p2`.
- Nếu `x1 == x2` thì `p1 < p2` nếu `y1 > y2`.
4. Cài đặt QuickSort theo quy tắc so sánh trên.

- **Code**

#include <bits/stdc++.h>
using namespace std;

int partition(vector<pair<int, int>> &a, int low, int high) {
    pair<int, int> pivot = a[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (a[j].first < pivot.first || (a[j].first == pivot.first && a[j].second > pivot.second)) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[high]);
    return i + 1;
}

void quickSort(vector<pair<int, int>> &a, int low, int high) {
    if (low < high) {
        int pi = partition(a, low, high);
        quickSort(a, low, pi - 1);
        quickSort(a, pi + 1, high);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;

    quickSort(a, 0, n - 1);

    for (auto &p : a) cout << p.first << " " << p.second << "\n";

    return 0;
}

## KHÓA SỐ
- **Đề bài**

- **Hướng giải**
Đây là bài toán tìm **số lớn nhất chia hết cho 3** bằng cách **xóa một số ít chữ số** và **sắp xếp lại các chữ số** theo thứ tự giảm dần.
**Các ý chính**:
1. Một số chia hết cho 3 nếu tổng các chữ số chia hết cho 3.
2. Nếu tổng chia 3 dư 1, ta cần:
- Xóa 1 chữ số chia 3 dư 1 hoặc
- Xóa 2 chữ số chia 3 dư 2.
3. Nếu tổng chia 3 dư 2, ta cần:
- Xóa 1 chữ số chia 3 dư 2 hoặc
- Xóa 2 chữ số chia 3 dư 1.
4. Sau khi xử lý, ta in ra xâu số lớn nhất (đã sắp xếp giảm dần).

- **Code**

#include<bits/stdc++.h>
using namespace std;

bool del = false;

void fi_re(string &n, int mod, bool del_2){
	int cnt = del_2 ? 2 : 1;
	for(int i = n.size()-1; i >= 0 && cnt > 0; i--) {
		if((n[i]-'0') % 3 == mod){
			n.erase(i, 1);
			del = true;
			cnt--;
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	string n;
	cin >> n;
	sort(n.rbegin(), n.rend());
	int sum = 0;
	for(char i : n){
		sum += i - '0';
	}
	if(sum % 3 == 0){
		cout << n;
		return 0;
	}
	else if(sum % 3 == 1){
		fi_re(n, 1, del);
		if(!del) fi_re(n, 2, !del);
	}else{
		fi_re(n, 2, del);
		if(!del) fi_re(n, 1, !del);
	}
	if(n != "") cout << n;
	else cout << 0;
}

## KIỂM KÊ
- **Đề bài**

- **Hướng giải**
1. Vì mỗi mã hàng có thể dài tới 100 ký tự, ta dùng `string` thay vì `int`.
2. Để đếm số mã khác nhau, có thể:
- Dùng `set<string>` (sẽ tự loại bỏ trùng lặp).
- Hoặc sắp xếp toàn bộ mảng mã, sau đó đếm số lần giá trị thay đổi (như đang làm trong đề bài).
3. Độ phức tạp của thuật toán là `O(n log n)` với QuickSort.

- **Code**

#include <bits/stdc++.h>
using namespace std;

int n;
string a[5 * 10000];

void QuickSort(int l, int r) {
    if (l >= r) return;
    string pivot = a[(l + r) / 2];
    int i = l, j = r;
    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) {
            swap(a[i], a[j]);
            i++; j--;
        }
    }
    QuickSort(l, j);
    QuickSort(i, r);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    QuickSort(0, n - 1);

    int cnt = 1; 
    for (int i = 1; i < n; i++) {
        if (a[i] != a[i - 1]) cnt++;
    }

    cout << cnt;
}

## Merge Sort
- **Đề bài**

- **Hướng giải**
1. Dùng phương pháp chia để trị (Divide and Conquer).
2. Gọi đệ quy chia mảng thành hai phần đến khi chỉ còn một phần tử.
3. Sau mỗi lần trộn hai mảng con, in ra toàn bộ mảng, phần tử đang được trộn nằm trong dấu `[ ]`.

- **Code**

#include<bits/stdc++.h>
using namespace std;

void printA(const vector<int>& a, int left, int right) {
    for (int i = 0; i < a.size(); i++) {
        if(i == left) cout << "[ ";
        cout << a[i] << " ";
        if(i == right) cout << "] ";
    }
    cout << "\n";
}

void Merge(vector<int>& a, int left, int mid, int right) {
    inplace_merge(a.begin() + left, a.begin() + mid + 1, a.begin() + right + 1);
    printA(a, left, right);
}

void MergeSort(vector<int>& a, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    MergeSort(a, left, mid);
    MergeSort(a, mid + 1, right);
    Merge(a, left, mid, right);
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    MergeSort(a, 0, n - 1);
    return 0;
}

## Insertion Sort
- **Đề bài**

- **Hướng giải**
1. Duyệt mảng từ phần tử thứ 2 đến cuối.
2. Với mỗi phần tử, tìm đúng vị trí chèn vào phần đã sắp xếp bên trái.
3. Mỗi lần dời phần tử hoặc gán phần tử vào vị trí, in ra mảng.

- **Code**

#include <bits/stdc++.h> 
using namespace std;   

void printA(vector<int> &a){
    for(int i : a) cout << i << " ";  
    cout << "\n"; 
}  

void insertionSort(vector<int> &a, int n){  
    for(int i = 1; i < n; i++){
        int k = a[i], j = i - 1;
        while(j >= 0 && a[j] > k){
            a[j + 1] = a[j];
            j = j - 1;
            printA(a);
        }
        a[j + 1] = k; 
        printA(a);
    }
}

int main(){ 
    int n; 
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    insertionSort(a, n);  
    return 0;
}

## Bubble Sort
- **Đề bài**

- **Hướng giải**
1. Duyệt mảng từ đầu đến gần cuối.
2. Với mỗi vòng lặp, so sánh từng cặp phần tử kề nhau.
3. Nếu phần tử bên trái lớn hơn bên phải thì hoán đổi.
4. Sau mỗi lần hoán đổi, in ra mảng.
5. Nếu trong một vòng không có swap nào xảy ra, dừng lại (tối ưu).

- **Code**

#include <bits/stdc++.h>
using namespace std;

void printA(vector<int>& a) {
    for(int i : a) cout << i << " ";
    cout << "\n";
}

void bubbleSort(vector<int>& a, int n) {
    bool swapped;
    for(int i = 0; i < n - 1; i++) {
        swapped = false;
        for(int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
                printA(a);
            }
        }
        if (!swapped) break;
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    bubbleSort(a, n);
    return 0;
}

## Bubble Sort
- **Đề bài**
Thuật toán tìm kiếm nổi bọt (Bubble Sort).

Hãy cài đặt thuật toán tìm kiếm nổi bọt để sắp xếp tăng dần mảng có N phần tử. Sau mỗi hành động swap (hoán đổi hai phần tử), in ra toàn bộ mảng.

- **Hướng giải**
1. Duyệt mảng từ đầu đến gần cuối.
2. Với mỗi vòng lặp, so sánh từng cặp phần tử kề nhau.
3. Nếu phần tử bên trái lớn hơn bên phải thì hoán đổi.
4. Sau mỗi lần hoán đổi, in ra mảng.
5. Nếu trong một vòng không có swap nào xảy ra, dừng lại (tối ưu).

- **Code**

#include <bits/stdc++.h>
using namespace std;

void printA(vector<int>& a) {
    for(int i : a) cout << i << " ";
    cout << "\n";
}

void bubbleSort(vector<int>& a, int n) {
    bool swapped;
    for(int i = 0; i < n - 1; i++) {
        swapped = false;
        for(int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
                printA(a);
            }
        }
        if (!swapped) break;
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    bubbleSort(a, n);
    return 0;
}

## Selection Sort
- **Đề bài**

- **Hướng giải**
1. Duyệt mảng từ đầu đến gần cuối.
2. Ở mỗi vị trí, tìm phần tử nhỏ nhất trong đoạn còn lại.
3. Nếu phần tử nhỏ nhất không nằm ở vị trí hiện tại, hoán đổi.
4. In ra mảng sau mỗi lần hoán đổi.

- **Code**

#include <bits/stdc++.h>
using namespace std;

void printA(vector<int>& a) {
    for(int i : a) cout << i << " ";
    cout << "\n";
}

void selection(vector<int> &a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int mn = i;
        for (int j = i + 1; j < n; j++) {
            if (a[mn] > a[j]) {
                mn = j;
            }
        }
        if (mn != i) {
            swap(a[i], a[mn]);
            printA(a);
        }
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    selection(a, n);
    return 0;
}

# LinkedList: Tìm nút chung của 2 danh sách liên kết đơn
## ĐỀ BÀI
Tìm nút (node) chung của 2 danh sách liên kết đơn. Cho 2 danh sách liên kết đơn, hãy cài đặt hàm `SinglyLinkedListNode* findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2)` để tìm nút chung (nếu có) của 2 danh sách liên kết đơn này.

Chú ý:
- Hàm `findMergeNode` có tham số `head1`, `head2` là 2 con trỏ trỏ đến nút đầu của 2 danh sách liên kết.
- Hàm này không nằm trong lớp nào cả.
- Hàm trả về con trỏ trỏ đến nút chung của 2 danh sách.
- Nếu 2 danh sách liên kết không có nút chung thì hàm trả về `nullptr`.

class SinglyLinkedListNode {
    public:
        int data;
        SinglyLinkedListNode *next;
        SinglyLinkedListNode(int node_data) {
            this->data = node_data;
            this->next = nullptr;
        }
};

class SinglyLinkedList {
    public:
        SinglyLinkedListNode *head;
};

## HƯỚNG GIẢI

1. Tính độ dài của hai danh sách.
2. Tính độ chênh lệch độ dài giữa hai danh sách.
3. Di chuyển con trỏ của danh sách dài hơn tiến về sau sao cho các danh sách bết đầu từ vị trí bằng nhau.
4. So sánh từng cặp nút của hai danh sách, nếu tìm thấy nút cùng địa chỉ thì trả về nút đó.
5. Nếu không tìm thấy nút chung thì trả về `nullptr`.

## CODE

SinglyLinkedListNode* findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    auto getLength = [](SinglyLinkedListNode* head) {
        int length = 0;
        while (head != nullptr) {
            ++length;
            head = head->next;
        }
        return length;
    };

    int len1 = getLength(head1);
    int len2 = getLength(head2);
    int diff = abs(len1 - len2);

    if (len1 > len2) {
        for (int i = 0; i < diff; ++i)
            head1 = head1->next;
    } else {
        for (int i = 0; i < diff; ++i)
            head2 = head2->next;
    }

    while (head1 != nullptr && head2 != nullptr) {
        if (head1 == head2)
            return head1;
        head1 = head1->next;
        head2 = head2->next;
    }

    return nullptr;
}

# Binary Search Tree: Nút tổ tiên thấp nhất
## ĐỀ BÀI
Source: https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor/problem

Cho một cây nhị phân tìm kiếm (BST), sinh viên hãy cài đặt hàm `lca` để tìm ra nút tổ tiên thấp nhất của 2 nút được cung cấp.

**Tham số:**
- `root`: con trỏ trỏ đến nút gốc của cây BST
- `v1`, `v2`: giá trị của 2 nút cần tìm nút tổ tiên chung thấp nhất

**Hàm trả về:**
- Con trỏ trỏ đến nút tổ tiên gần nhất (lowest common ancestor)

**Ví dụ Input:**

6
4 2 3 1 7 6
1 7

**Output:**

Con trỏ trỏ đến nút có giá trị 4.

**Diễn giải:**

Từ dãy 4 2 3 1 7 6 tạo cây BST, với v1 = 1 và v2 = 7, thì nút chung thấp nhất là nút có giá trị 4 (gốc).

## HƯỚNG GIẢI

1. Do BST có thuộc tính trái < node < phải, ta dùng quy tắc:
2. Nếu cả hai giá trị nhỏ hơn node hiện tại → tìm bên trái.
3. Nếu cả hai giá trị lớn hơn node hiện tại → tìm bên phải.
4. Nếu 1 bên nhỏ, 1 bên lớn hoặc bằng node hiện tại → node đó chính là LCA.

## CODE

SinglyLinkedListNode* findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    auto getLength = [](SinglyLinkedListNode* head) {
        int length = 0;
        while (head != nullptr) {
            ++length;
            head = head->next;
        }
        return length;
    };

    int len1 = getLength(head1);
    int len2 = getLength(head2);
    int diff = abs(len1 - len2);

    if (len1 > len2) {
        for (int i = 0; i < diff; ++i)
            head1 = head1->next;
    } else {
        for (int i = 0; i < diff; ++i)
            head2 = head2->next;
    }

    while (head1 != nullptr && head2 != nullptr) {
        if (head1 == head2)
            return head1;
        head1 = head1->next;
        head2 = head2->next;
    }

    return nullptr;
}

TreeNode* lca(TreeNode* root, int v1, int v2) {
    if (!root) return nullptr;
    if (v1 < root->data && v2 < root->data)
        return lca(root->left, v1, v2);
    else if (v1 > root->data && v2 > root->data)
        return lca(root->right, v1, v2);
    else
        return root;
}

# Tree: Preorder Traversal (NLR) II - Duyệt cây BST theo NLR không đệ quy
## ĐỀ BÀI
Source: https://www.hackerrank.com/challenges/tree-preorder-traversal/problem

Sinh viên cài đặt hàm `void preOrder(Node* root)` với `root` là con trỏ chỉ đến gốc của cây nhị phân; hàm này sẽ in toàn bộ cây nhị phân thành một dòng các giá trị cách nhau với 1 khoảng trắng theo thứ tự duyệt **NLR** (node - left - right).

**Chú ý:** không được sử dụng đệ quy trong bài toán này.

## HƯỚNG GIẢI

1. Sử dụng một stack để lưu các nút cần xử lý thay vì dùng đệ quy.
2. Đẩy nút gốc vào stack ban đầu.
3. Trong khi stack chưa rỗng:
- Lấy phần tử đầu stack ra, in giá trị.
- Nếu có con phải, đẩy con phải vào stack.
- Nếu có con trái, đẩy con trái vào stack (vì L phải được xử lý trước R).
4. Lặp lại đến khi stack rỗng.

## CODE

void preOrder(Node* root) {
    if (root == nullptr) return;
    stack<Node*> st;
    st.push(root);
    while (!st.empty()) {
        Node* current = st.top();
        st.pop();
        cout << current->data << " ";
        if (current->right != nullptr) st.push(current->right);
        if (current->left != nullptr) st.push(current->left);
    }
}

## LinkedList: MergetwoSortedLinkedList

Cho hai mảng đã có thứ tự, hãy trộn chúng thành một mảng cũng có thứ tự.

**INPUT**

Dòng đầu tiên chứa số T (T < 10) là số test case.

Mỗi test case có 3 hàng. Hàng đầu tiên chứa hai số n và m (n,m < 500.000) lần lượt là số phần tử của hai mảng A và B. Hàng thứ hai chứa n số nguyên được sắp theo thứ tự không giảm, đây chính là các phần tử của mảng A. Hàng cuối cùng chứa m số nguyên được sắp theo thứ tự không giảm, đây chính là các phần tử của mảng B.

**OUTPUT**

Ứng với mỗi test case, xuất ra trên một dòng mảng có thứ tự thu được bằng cách trộn hai mảng A và B.

## HƯỚNG GIẢI

1. Khởi tạo hai con trỏ cho danh sách liên kết, một cho mảng A và một cho mảng B.
2. Duyệt qua cả hai danh sách, so sánh từng phần tử và nối vào danh sách kết quả theo thứ tự tăng dần.
3. Khi một trong hai danh sách kết thúc, nối các phần tử còn lại từ danh sách chưa hết vào danh sách kết quả.
4. Trả về danh sách kết quả đã được trộn.

## CODE

SinglyLinkedListNode* mergeTwoSortedLinkedLists(SinglyLinkedListNode* head_list1, SinglyLinkedListNode* head_list2) {
    if (!head_list1) return head_list2;
    if (!head_list2) return head_list1;

    SinglyLinkedListNode* mergedHead = nullptr;
    SinglyLinkedListNode* mergedTail = nullptr;

    while (head_list1 && head_list2) {
        SinglyLinkedListNode* newNode = nullptr;

        if (head_list1->data <= head_list2->data) {
            newNode = new SinglyLinkedListNode(head_list1->data);
            head_list1 = head_list1->next;
        } else {
            newNode = new SinglyLinkedListNode(head_list2->data);
            head_list2 = head_list2->next;
        }

        if (!mergedHead) {
            mergedHead = mergedTail = newNode;
        } else {
            mergedTail->next = newNode;
            mergedTail = newNode;
        }
    }

    while (head_list1) {
        mergedTail->next = new SinglyLinkedListNode(head_list1->data);
        mergedTail = mergedTail->next;
        head_list1 = head_list1->next;
    }

    while (head_list2) {
        mergedTail->next = new SinglyLinkedListNode(head_list2->data);
        mergedTail = mergedTail->next;
        head_list2 = head_list2->next;
    }

    return mergedHead;
}

## LinkedList: Nhap Da Thuc

### ĐỀ BÀI

Định nghĩa Đa thức một biến f(x) có dạng:
S = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ... + a₀

Viết chương trình nhập xuất đa thức một biến f(x). Sau đó nhập giá trị biến x và tính giá trị f(x) với kết quả hiển thị chính xác 2 số sau dấu thập phân.

### INPUT

Dãy các số trong đó:

- Số nguyên đầu tiên (0 <= n <= 100): số lượng đơn thức trong đa thức
- n cặp số tiếp theo, mỗi cặp số là một đơn thức gồm: hệ số (số thực) và số mũ (số nguyên >= 0)
- Các đơn thức được nhập vào theo thứ tự giảm dần của số mũ, và không có đơn thức nào có cùng số mũ.

### OUTPUT

- Xuất đa thức theo dạng chuẩn:
- Biến trong đa thức ký hiệu là x.
- Số mũ ký hiệu là `^`.
- Phép nhân không ghi ký hiệu.
- Các ký tự biểu diễn đa thức ghi liền nhau (không khoảng trắng).
- Đơn thức đầu tiên nếu hệ số là số dương thì không được xuất dấu + trước hệ số.
- Đơn thức có hệ số bằng 0 thì không xuất đơn thức đó.
- Đơn thức có hệ số bằng 1 hoặc -1 thì không xuất số 1.
- Đơn thức có số mũ bằng 0 thì chỉ xuất hệ số của đơn thức.
- Đơn thức có số mũ bằng 1 thì không xuất số mũ.

### HƯỚNG GIẢI

1. Định nghĩa cấu trúc dữ liệu `DATHUC` bao gồm danh sách liên kết các đơn thức.
2. Nhập đa thức từ đầu vào, mỗi đơn thức chứa hệ số và số mũ.
3. Xuất đa thức theo yêu cầu, chú ý đến các quy tắc về dấu và cách thể hiện hệ số và số mũ.
4. Tính giá trị đa thức tại một điểm x.

### CODE

struct DONTHUC {
    double heso;
    int somu;
    DONTHUC(double h, int s) : heso(h), somu(s) {}
};

struct Node {
    DONTHUC* data;
    Node* next;
    Node(DONTHUC* d) : data(d), next(nullptr) {}
};

struct DATHUC {
    Node* head;
    Node* tail;
    DATHUC() : head(nullptr), tail(nullptr) {}
};

void Nhap(DATHUC &B, double heso, int somu) {
    if (heso == 0) return;

    Node* a = new Node(new DONTHUC(heso, somu));

    if (B.head == nullptr)
        B.head = B.tail = a;
    else {
        B.tail->next = a;
        B.tail = a;
    }
}

void Xuat(DATHUC B) {
    if (B.head == nullptr) {
        cout << "0";
        return;
    }
    Node* p = B.head;
    bool first = true;
    while (p != nullptr) {
        double heso = p->data->heso;
        int somu = p->data->somu;

        if (first) {
            first = false;
            if (heso == -1 && somu > 0) cout << "-";
            else if (heso != 1 || somu == 0) cout << heso;
        } else {
            if (heso > 0) cout << "+";
            if (heso == -1 && somu > 0) cout << "-";
            else if (heso != 1 || somu == 0) cout << heso;
        }

        if (somu > 0) cout << "x";
        if (somu > 1) cout << "^" << somu;
        p = p->next;
    }
}

double TinhDaThuc(DATHUC B, double x) {
    double res = 0;
    Node* p = B.head;
    while(p != nullptr) {
        res += p->data->heso * pow(x, p->data->somu);
        p = p->next;
    }
    return res;
}

## LinkedList: Insertion

### ĐỀ BÀI

Chèn một nút vào một danh sách liên kết đơn đã có thứ tự

Cho một danh sách liên kết đơn `L` gồm `N` số đã có thứ tự tăng dần và một số nguyên `x`. Bạn hãy chèn một node có giá trị `x` vào danh sách liên kết `L` sao cho danh sách liên kết vẫn bảo đảm có thứ tự tăng dần.

### INPUT

- Dòng đầu tiên là số lượng phần tử của `N` (0 ≤ N ≤ 100,000).
- N dòng tiếp theo sẽ là giá trị của danh sách liên kết `L` (có thứ tự tăng dần).
- Dòng cuối cùng là giá trị `x` cần được chèn vào danh sách `L` nêu trên.

### OUTPUT

- Danh sách liên kết `L` sau khi chèn giá trị `x` vào, mỗi số cách nhau bằng một dấu khoảng trắng.

### HƯỚNG GIẢI

1. Tạo một nút mới với giá trị `x`.
2. Nếu danh sách rỗng hoặc giá trị `x` nhỏ hơn hoặc bằng giá trị của nút đầu tiên, gắn nút mới làm đầu của danh sách.
3. Nếu không, duyệt qua danh sách để tìm vị trí thích hợp chèn `x`.
4. Chèn nút mới vào đúng vị trí sao cho danh sách vẫn bảo đảm thứ tự tăng dần.
5. In danh sách liên kết sau khi chèn giá trị `x`.

### CODE

struct SinglyLinkedListNode {
    int data;
    SinglyLinkedListNode* next;
    SinglyLinkedListNode(int d) : data(d), next(nullptr) {}
};

SinglyLinkedListNode* insertNode(SinglyLinkedListNode* head, int x) {
    SinglyLinkedListNode* newNode = new SinglyLinkedListNode(x);
    if (!head || x <= head->data) {
        newNode->next = head;
        return newNode;
    }
    SinglyLinkedListNode* current = head;
    while (current->next && current->next->data < x) {
        current = current->next;
    }
    newNode->next = current->next;
    current->next = newNode;
    return head;
}

void printList(SinglyLinkedListNode* head) {
    SinglyLinkedListNode* current = head;
    while (current) {
        cout << current->data;
        if (current->next) cout << " ";
        current = current->next;
    }
    cout << endl;
}

## Kiểm tra biểu thức toán học (Latex)

### ĐỀ BÀI

Kiểm tra tính hợp lệ của chuỗi latex. Biểu thức toán học giúp chúng ta diễn đạt tự nhiên thành các phương trình. Tuy nhiên, từ trước đến nay, các tài liệu văn bản của các học giả, các nhà toán học ghi xuống dưới dạng chữ viết. Bạn X đã viết chương trình chuyển đổi các biểu thức này thành dạng số. Tuy nhiên chương trình của bạn còn chưa được hoàn thiện, đặc biệt là do các dấu ngoặc đóng và mở như `"{"`, `"}"`, `"("`, `")"`, và `"["`, `"]"`. Việc mất cân bằng số lượng giữa các dấu này sẽ khiến máy tính không hiểu và không render được. Hãy giúp X viết chương trình chỉ ra đâu là biểu thức toán học bị sai.

### INPUT

- Dòng đầu tiên chứa chuỗi `s` (1 ≤ N ≤ 10^5).

### OUTPUT

- Nếu hợp lệ hãy xuất ra `1`, còn không hợp lệ xuất ra `0`.

### HƯỚNG GIẢI

1. Sử dụng một stack để theo dõi các dấu ngoặc mở.
2. Duyệt qua chuỗi:
- Nếu gặp dấu ngoặc mở (`{`, `[`, hoặc `(`), push vào stack.
- Nếu gặp dấu ngoặc đóng (`}`, `]`, hoặc `)`), kiểm tra stack:
- Nếu stack rỗng hoặc dấu ngoặc không khớp, trả về sai.
3. Sau khi duyệt hết chuỗi, nếu stack còn chứa bất kỳ dấu ngoặc mở nào, trả về sai.
4. Nếu tất cả dấu ngoặc đều khớp, trả về đúng.

### CODE

#include<bits/stdc++.h>
using namespace std;

bool check(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.empty()) return false;
            char top = st.top(); st.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return st.empty();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s;
    getline(cin, s);  // Đọc toàn bộ dòng, bao gồm cả khoảng trắng
    
    if (check(s)) cout << 1;
    else cout << 0;
}

## LinkedList: Reverse

### ĐỀ BÀI

Cho danh sách liên kết chứa `N` phần tử. Bạn hãy đảo ngược danh sách liên kết này và in danh sách trên một dòng.

### INPUT

- Dòng đầu tiên chứa số nguyên `N` là số lượng phần tử trong danh sách liên kết.
- N dòng tiếp theo mỗi dòng chứa một số nguyên các phần tử theo thứ tự trong danh sách liên kết.

### OUTPUT

- Một dòng gồm `N` số nguyên là các phần tử sau khi đã được đảo ngược.

### HƯỚNG GIẢI

1. Duyệt qua danh sách liên kết ban đầu, thực hiện thao tác đảo ngược danh sách liên kết.
2. Sau khi đảo ngược, in các phần tử của danh sách liên kết đã được thay đổi thứ tự.

### CODE

void insert_node(SinglyLinkedList* llist, int data) {
    SinglyLinkedListNode* new_node = new SinglyLinkedListNode(data);

    if (llist->head == nullptr) {
        llist->head = new_node;
    } else {
        llist->tail->next = new_node;
    }
    llist->tail = new_node;
}

void reverseLinkedList(SinglyLinkedList* llist) {
    SinglyLinkedListNode* prev = nullptr;
    SinglyLinkedListNode* current = llist->head;
    SinglyLinkedListNode* next = nullptr;

    while (current != nullptr) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    llist->tail = llist->head;
    llist->head = prev;
}

void printLinkedList(SinglyLinkedList* llist) {
    SinglyLinkedListNode* node = llist->head;
    while (node != nullptr) {
        cout << node->data;
        if (node->next != nullptr) cout << " ";
        node = node->next;
    }
    cout << endl;
}

## Dec to Bin - Chuyển đổi cơ số

### ĐỀ BÀI

Việc chuyển đổi cơ số từ hệ thập phân sang hệ nhị phân là vô cùng quan trọng. Bởi vì hệ nhị phân (0 và 1) là cách hiểu của mọi thiết bị máy tính hiện nay, cũng như các mạch logic (AND, OR, XOR, NOT, v.v).

Bạn hãy viết chương trình giúp chuyển đổi từ hệ cơ số 10 sang hệ cơ số 2 (nhị phân).

### INPUT

- Dòng đầu tiên chứa số nguyên `x` (1 ≤ x ≤ 10^5), là số tại hệ cơ số 10.

### OUTPUT

- Giá trị nhị phân tương ứng với số `x`.

### HƯỚNG GIẢI

1. Chia số nguyên theo cơ số 2 và lưu lại phần dư của từng phép chia.
2. In phần dư theo thứ tự ngược lại từ phần chia cuối cùng đến phần chia đầu tiên.

### CODE

#include<bits/stdc++.h>
using namespace std;
vector<int> res;

void dec2bin(int num){
    while(num != 0){
        int r = num % 2;
        num /= 2;
        res.push_back(r);
    }
    for(int i = res.size() - 1; i >= 0; i--) {
        cout << res[i];
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int num;
    cin >> num;
    dec2bin(num);
}

# BINARY SEARCH 2
## ĐỀ BÀI
Cho một dãy số nguyên A gồm N phần tử A1, A2, …, AN.

Có Q truy vấn, mỗi truy vấn có dạng type x y.

Nếu x = 1, thì phải in ra vị trí đầu tiên xuất hiện y trong dãy A. Nếu không có thì in ra -1.

Nếu x = 2, thì phải in ra vị trí cuối cùng xuất hiện y trong dãy A. Nếu không có thì in ra -1.

### INPUT:

Dòng đầu tiên là 2 số nguyên dương N, Q (1 ≤ N ≤ 10^5, 1 ≤ Q ≤ 5 × 10^5)

Dòng tiếp theo chứa N số nguyên Ai (−10^9 ≤ Ai ≤ 10^9) là các phần tử của mảng.

Q dòng tiếp theo, mỗi dòng có dạng type x y.

### OUTPUT:

Gồm Q dòng, mỗi dòng gồm một câu trả lời ứng với từng truy vấn.

## HƯỚNG GIẢI

1. Sử dụng thuật toán QuickSort để sắp xếp mảng theo giá trị của các phần tử, lưu lại chỉ số ban đầu của chúng.
2. Sử dụng binary search để tìm vị trí đầu tiên và cuối cùng của giá trị x trong mảng đã sắp xếp.
3. Dựa trên loại truy vấn (x = 1 hoặc x = 2), thực hiện tìm kiếm vị trí đầu tiên hoặc cuối cùng của giá trị y trong mảng.

## CODE

#include <bits/stdc++.h>
using namespace std;

int partition(vector<pair<int, int>>& arr, int low, int high) {
    int pivot = arr[high].first;
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j].first < pivot || (arr[j].first == pivot && arr[j].second < arr[high].second)) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<pair<int, int>>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int landau(const vector<pair<int, int>>& arr, int x) {
    int left = 0, right = arr.size() - 1, res = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid].first == x) {
            res = arr[mid].second + 1;
            right = mid - 1;
        } else if (arr[mid].first < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return res;
}

int lancuoi(const vector<pair<int, int>>& arr, int x) {
    int left = 0, right = arr.size() - 1, res = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid].first == x) {
            res = arr[mid].second + 1;
            left = mid + 1;
        } else if (arr[mid].first < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    vector<pair<int, int>> arr(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        arr[i] = {A[i], i};
    }
    quickSort(arr, 0, N - 1);
    while (Q--) {
        string type;
        int y, val;
        cin >> type >> y >> val;
        if (y == 1) {
            int pos = landau(arr, val);
            cout << pos << "\n";
        } else if (y == 2) {
            int pos = lancuoi(arr, val);
            cout << pos << "\n";
        }
    }
}

# KIỂM KÊ 2
## ĐỀ BÀI
Cửa hàng X có nhiều loại hàng, mỗi loại hàng đều có mã khác nhau. Tuy nhiên, trong lúc bán hàng, nhân viên quên không nhập số lượng mỗi loại mà chỉ nhập mã các loại hàng trên từng dòng. Bạn hãy cho biết với mỗi loại hàng thì cửa hàng đã bán được bao nhiêu?

Ví dụ: Có một số loại hàng có mã lần lượt là [123, 45, 8, 19, 1, 2333].

Bạn nhân viên sẽ nhập theo từng dòng [123, 45, 45, 8, 1, 123, 123, 8, 8].

Từ đây có thể biết:

- Với loại hàng có mã là 1 thì cửa hàng đã bán 1.
- Với loại hàng có mã là 8 thì cửa hàng đã bán 3.
- Với loại hàng có mã là 45 thì cửa hàng đã bán 2.
- Với loại hàng có mã là 123 thì cửa hàng đã bán 3.

### INPUT:

Dòng đầu tiên là số nguyên (1 ≤ N ≤ 5 × 10^4) là số lượng mã loại hàng được nhập.

N dòng tiếp theo, mỗi dòng là một mã của loại hàng được nhập, độ dài của mã có thể lên tới 100.

### OUTPUT:

Gồm nhiều dòng, mỗi dòng gồm 2 thành phần là mã số của một loại hàng và số lượng loại hàng đó. In kết quả theo thứ tự giảm dần theo số lượng từng loại hàng, nếu số lượng bằng nhau thì in theo mã số tăng dần.

Chú ý: So sánh 2 mã theo thứ tự số tự nhiên. Sử dụng '\n' để xuống dòng thay vì endl để tránh bị Time Limit Exceeded (TLE).

## HƯỚNG GIẢI

1. Sử dụng thuật toán QuickSort để sắp xếp mảng mã loại hàng.
2. Duyệt qua danh sách mã hàng để đếm số lần xuất hiện mỗi mã, lưu vào một vector các cặp (mã, số lần).
3. Tiếp tục sử dụng QuickSort để sắp xếp các cặp (mã, số lần) theo yêu cầu: giảm dần theo số lần bán, nếu bằng nhau thì tăng dần theo mã hàng.
4. In kết quả theo thứ tự đã sắp xếp.

## CODE

#include <bits/stdc++.h>
using namespace std;

struct Item {
    string index;
    int cnt;
};

bool compareStrings(const string& a, const string& b) {
    if (a.length() != b.length()) return a.length() < b.length();
    return a < b;
}

bool compareItems(const Item& item1, const Item& item2) {
    if (item1.cnt != item2.cnt) return item1.cnt > item2.cnt;
    return compareStrings(item1.index, item2.index);
}

int partition(vector<string>& item, int low, int high) {
    string pivot = item[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (item[j] < pivot) {
            i++;
            swap(item[i], item[j]);
        }
    }
    swap(item[i + 1], item[high]);
    return i + 1;
}

void quickSort(vector<string>& item, int low, int high) {
    if (low < high) {
        int pi = partition(item, low, high);
        quickSort(item, low, pi - 1);
        quickSort(item, pi + 1, high);
    }
}

int partitionItems(vector<Item>& item, int low, int high) {
    Item pivot = item[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (compareItems(item[j], pivot)) {
            i++;
            swap(item[i], item[j]);
        }
    }
    swap(item[i + 1], item[high]);
    return i + 1;
}

void quickSortItems(vector<Item>& item, int low, int high) {
    if (low < high) {
        int pi = partitionItems(item, low, high);
        quickSortItems(item, low, pi - 1);
        quickSortItems(item, pi + 1, high);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    quickSort(a, 0, n - 1); 

    vector<Item> items;
    int cnt = 1;
    
    for (int i = 1; i < n; i++) {
        if (a[i] == a[i - 1]) {
            cnt++;
        } else {
            items.push_back({a[i - 1], cnt});
            cnt = 1;
        }
    }
    
    items.push_back({a[n - 1], cnt}); 

    quickSortItems(items, 0, items.size() - 1); 

    for (Item& item : items) {
        cout << item.index << " " << item.cnt << "\n";
    }
}

# KHANGTD.XEPHANG2
## ĐỀ BÀI
Một lớp có n sinh viên. Các sinh viên có mã số sinh viên (mssv) theo thứ tự từ 1 đến n. Ban đầu các bạn sinh viên xếp hàng theo đúng thứ tự theo mã số sinh viên từ 1 đến n, nghĩa là sinh viên có mssv là 1 ở đầu, tiếp theo là sinh viên có mssv là 2,..., sinh viên có mssv là n ở đứng cuối cùng. Khi thầy giáo gọi một bạn nào đó, thì bạn đó lên đứng đầu hàng. Cứ mỗi lần gọi trong m lần gọi thì thầy giáo muốn biết sinh viên đứng cuối cùng là bạn nào?

### INPUT:

Dòng thứ nhất gồm hai số nguyên n, m cách nhau một khoảng trắng (1 ≤ n, m ≤ 10^5). n là số sinh viên và m là số lần thầy giáo gọi.

Dòng tiếp theo gồm m số nguyên a1, a2, ..., am mỗi số cách nhau một khoảng trắng 1 ≤ ai ≤ n. ai là mssv của sinh viên được gọi trong lần gọi thứ i.

### OUTPUT:

Kết quả là m số nguyên, mỗi số cách nhau một khoảng trắng, thể hiện là mssv của học sinh cuối cùng sau khi thầy gọi.

## HƯỚNG GIẢI

1. Duy trì một danh sách `line` các sinh viên theo thứ tự mã số sinh viên từ 1 đến n.
2. Sử dụng `unordered_map` để lưu vị trí của từng sinh viên trong danh sách để tiện thao tác nhanh chóng.
3. Mỗi lần thầy gọi một sinh viên, xóa sinh viên đó khỏi vị trí hiện tại và đưa lên đầu danh sách.
4. Sau mỗi lần gọi, in ra mã số sinh viên cuối cùng trong danh sách.

## CODE

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,m; cin>>n>>m;
    list<int> line;
    for(int i=1;i<=n;i++) line.push_back(i);
    unordered_map<int, list<int>::iterator> pos;
    auto it = line.begin();
    for(int i=1;i<=n;i++) pos[i]=it++;
    vector<int> res;
    while(m--){
        int cal; cin>>cal;
        line.erase(pos[cal]);
        line.push_front(cal);
        pos[cal]=line.begin();
        res.push_back(line.back());
    }
    for(int i=0;i<res.size();i++) cout<<res[i]<<" ";
}

# KHANGTD.XEPHANG
## ĐÈ BÀI
Một lớp có n sinh viên. Các sinh viên có mã số sinh viên (mssv) theo thứ tự từ 1 đến n. Ban đầu các bạn sinh viên xếp hàng theo đúng thứ tự theo mã số sinh viên từ 1 đến n, nghĩa là sinh viên có mssv là 1 ở đầu, tiếp theo là sinh viên có mssv là 2,..., sinh viên có mssv là n ở đứng cuối cùng. Khi thầy giáo gọi một bạn nào đó, thì bạn đó lên đứng đầu hàng. Hỏi sau m lần được gọi, thì thứ tự của các bạn sinh viên sẽ như thế nào?

### INPUT:

Dòng thứ nhất gồm hai số nguyên n, m cách nhau một khoảng trắng (1 ≤ n, m ≤ 10^5), n là số sinh viên và m là số lần thầy giáo gọi.

Dòng tiếp theo gồm m số nguyên a1, a2, ..., am mỗi số cách nhau một khoảng trắng (1 ≤ ai ≤ n), ai là mssv của sinh viên được gọi trong lần gọi thứ i.

### OUTPUT:

Kết quả là m số nguyên, mỗi số cách nhau một khoảng trắng, là mssv của sinh viên từ đầu hàng đến cuối hàng.

## HƯỚNG GIẢI

1. Duy trì một danh sách `cal` để lưu trữ các mã số sinh viên được gọi theo thứ tự.
2. Duy trì một bộ nhớ đệm `check` để đánh dấu sinh viên đã được gọi lên đầu.
3. Lấy các sinh viên đã được gọi theo thứ tự từ cuối lên đầu, và thêm vào danh sách kết quả `res`.
4. Sau đó thêm các sinh viên chưa được gọi vào cuối danh sách kết quả `res`.
5. Cuối cùng, in ra thứ tự của các sinh viên trong danh sách kết quả.

## CODE

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,m; cin>>n>>m;
    vector<int> cal,res;
    unordered_map<int,bool> check;
    for(int i=0;i<m;i++){
        int temp; cin>>temp;
        cal.push_back(temp);
    }
    for(int i=m-1;i>=0;i--){
        if(!check[cal[i]]){
            res.push_back(cal[i]);
            check[cal[i]]=true;
        }
    }
    for(int i=1;i<=n;i++){
        if(!check[i]) res.push_back(i);
    }
    for(int i:res) cout<<i<<" ";
}

# BINARY SEARCH 2
## ĐỀ BÀI
Cho một dãy số nguyên A gồm N phần tử A1, A2, …, AN.

Có Q truy vấn, mỗi truy vấn có dạng type x y.

Nếu x = 1, thì phải in ra vị trí đầu tiên xuất hiện y trong dãy A. Nếu không có thì in ra -1.

Nếu x = 2, thì phải in ra vị trí cuối cùng xuất hiện y trong dãy A. Nếu không có thì in ra -1.

### INPUT:

Dòng đầu tiên là 2 số nguyên dương N, Q (1 ≤ N ≤ 10^5, 1 ≤ Q ≤ 5 × 10^5)

Dòng tiếp theo chứa N số nguyên Ai (−10^9 ≤ Ai ≤ 10^9) là các phần tử của mảng.

Q dòng tiếp theo, mỗi dòng có dạng type x y.

### OUTPUT:

Gồm Q dòng, mỗi dòng gồm một câu trả lời ứng với từng truy vấn.

## HƯỚNG GIẢI

1. Sử dụng thuật toán QuickSort để sắp xếp mảng theo giá trị của các phần tử, lưu lại chỉ số ban đầu của chúng.
2. Sử dụng binary search để tìm vị trí đầu tiên và cuối cùng của giá trị x trong mảng đã sắp xếp.
3. Dựa trên loại truy vấn (x = 1 hoặc x = 2), thực hiện tìm kiếm vị trí đầu tiên hoặc cuối cùng của giá trị y trong mảng.

## CODE

#include <bits/stdc++.h>
using namespace std;

int partition(vector<pair<int, int>>& arr, int low, int high) {
    int pivot = arr[high].first;
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j].first < pivot || (arr[j].first == pivot && arr[j].second < arr[high].second)) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<pair<int, int>>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int landau(const vector<pair<int, int>>& arr, int x) {
    int left = 0, right = arr.size() - 1, res = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid].first == x) {
            res = arr[mid].second + 1;
            right = mid - 1;
        } else if (arr[mid].first < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return res;
}

int lancuoi(const vector<pair<int, int>>& arr, int x) {
    int left = 0, right = arr.size() - 1, res = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid].first == x) {
            res = arr[mid].second + 1;
            left = mid + 1;
        } else if (arr[mid].first < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    vector<pair<int, int>> arr(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        arr[i] = {A[i], i};
    }
    quickSort(arr, 0, N - 1);
    while (Q--) {
        string type;
        int y, val;
        cin >> type >> y >> val;
        if (y == 1) {
            int pos = landau(arr, val);
            cout << pos << "\n";
        } else if (y == 2) {
            int pos = lancuoi(arr, val);
            cout << pos << "\n";
        }
    }
}

# KIỂM KÊ 2
## ĐỀ BÀI
Cửa hàng X có nhiều loại hàng, mỗi loại hàng đều có mã khác nhau. Tuy nhiên, trong lúc bán hàng, nhân viên quên không nhập số lượng mỗi loại mà chỉ nhập mã các loại hàng trên từng dòng. Bạn hãy cho biết với mỗi loại hàng thì cửa hàng đã bán được bao nhiêu?

Ví dụ: Có một số loại hàng có mã lần lượt là [123, 45, 8, 19, 1, 2333].

Bạn nhân viên sẽ nhập theo từng dòng [123, 45, 45, 8, 1, 123, 123, 8, 8].

Từ đây có thể biết:

- Với loại hàng có mã là 1 thì cửa hàng đã bán 1.
- Với loại hàng có mã là 8 thì cửa hàng đã bán 3.
- Với loại hàng có mã là 45 thì cửa hàng đã bán 2.
- Với loại hàng có mã là 123 thì cửa hàng đã bán 3.

### INPUT:

Dòng đầu tiên là số nguyên (1 ≤ N ≤ 5 × 10^4) là số lượng mã loại hàng được nhập.

N dòng tiếp theo, mỗi dòng là một mã của loại hàng được nhập, độ dài của mã có thể lên tới 100.

### OUTPUT:

Gồm nhiều dòng, mỗi dòng gồm 2 thành phần là mã số của một loại hàng và số lượng loại hàng đó. In kết quả theo thứ tự giảm dần theo số lượng từng loại hàng, nếu số lượng bằng nhau thì in theo mã số tăng dần.

Chú ý: So sánh 2 mã theo thứ tự số tự nhiên. Sử dụng '\n' để xuống dòng thay vì endl để tránh bị Time Limit Exceeded (TLE).

## HƯỚNG GIẢI

1. Sử dụng thuật toán QuickSort để sắp xếp mảng mã loại hàng.
2. Duyệt qua danh sách mã hàng để đếm số lần xuất hiện mỗi mã, lưu vào một vector các cặp (mã, số lần).
3. Tiếp tục sử dụng QuickSort để sắp xếp các cặp (mã, số lần) theo yêu cầu: giảm dần theo số lần bán, nếu bằng nhau thì tăng dần theo mã hàng.
4. In kết quả theo thứ tự đã sắp xếp.

## CODE

#include <bits/stdc++.h>
using namespace std;

struct Item {
    string index;
    int cnt;
};

bool compareStrings(const string& a, const string& b) {
    if (a.length() != b.length()) return a.length() < b.length();
    return a < b;
}

bool compareItems(const Item& item1, const Item& item2) {
    if (item1.cnt != item2.cnt) return item1.cnt > item2.cnt;
    return compareStrings(item1.index, item2.index);
}

int partition(vector<string>& item, int low, int high) {
    string pivot = item[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (item[j] < pivot) {
            i++;
            swap(item[i], item[j]);
        }
    }
    swap(item[i + 1], item[high]);
    return i + 1;
}

void quickSort(vector<string>& item, int low, int high) {
    if (low < high) {
        int pi = partition(item, low, high);
        quickSort(item, low, pi - 1);
        quickSort(item, pi + 1, high);
    }
}

int partitionItems(vector<Item>& item, int low, int high) {
    Item pivot = item[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (compareItems(item[j], pivot)) {
            i++;
            swap(item[i], item[j]);
        }
    }
    swap(item[i + 1], item[high]);
    return i + 1;
}

void quickSortItems(vector<Item>& item, int low, int high) {
    if (low < high) {
        int pi = partitionItems(item, low, high);
        quickSortItems(item, low, pi - 1);
        quickSortItems(item, pi + 1, high);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    quickSort(a, 0, n - 1); 

    vector<Item> items;
    int cnt = 1;
    
    for (int i = 1; i < n; i++) {
        if (a[i] == a[i - 1]) {
            cnt++;
        } else {
            items.push_back({a[i - 1], cnt});
            cnt = 1;
        }
    }
    
    items.push_back({a[n - 1], cnt}); 

    quickSortItems(items, 0, items.size() - 1); 

    for (Item& item : items) {
        cout << item.index << " " << item.cnt << "\n";
    }
}

# KHANGTD.XEPHANG2
## ĐỀ BÀI
Một lớp có n sinh viên. Các sinh viên có mã số sinh viên (mssv) theo thứ tự từ 1 đến n. Ban đầu các bạn sinh viên xếp hàng theo đúng thứ tự theo mã số sinh viên từ 1 đến n, nghĩa là sinh viên có mssv là 1 ở đầu, tiếp theo là sinh viên có mssv là 2,..., sinh viên có mssv là n ở đứng cuối cùng. Khi thầy giáo gọi một bạn nào đó, thì bạn đó lên đứng đầu hàng. Cứ mỗi lần gọi trong m lần gọi thì thầy giáo muốn biết sinh viên đứng cuối cùng là bạn nào?

### INPUT:

Dòng thứ nhất gồm hai số nguyên n, m cách nhau một khoảng trắng (1 ≤ n, m ≤ 10^5). n là số sinh viên và m là số lần thầy giáo gọi.

Dòng tiếp theo gồm m số nguyên a1, a2, ..., am mỗi số cách nhau một khoảng trắng 1 ≤ ai ≤ n. ai là mssv của sinh viên được gọi trong lần gọi thứ i.

### OUTPUT:

Kết quả là m số nguyên, mỗi số cách nhau một khoảng trắng, thể hiện là mssv của học sinh cuối cùng sau khi thầy gọi.

## HƯỚNG GIẢI

1. Duy trì một danh sách `line` các sinh viên theo thứ tự mã số sinh viên từ 1 đến n.
2. Sử dụng `unordered_map` để lưu vị trí của từng sinh viên trong danh sách để tiện thao tác nhanh chóng.
3. Mỗi lần thầy gọi một sinh viên, xóa sinh viên đó khỏi vị trí hiện tại và đưa lên đầu danh sách.
4. Sau mỗi lần gọi, in ra mã số sinh viên cuối cùng trong danh sách.

## CODE

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,m; cin>>n>>m;
    list<int> line;
    for(int i=1;i<=n;i++) line.push_back(i);
    unordered_map<int, list<int>::iterator> pos;
    auto it = line.begin();
    for(int i=1;i<=n;i++) pos[i]=it++;
    vector<int> res;
    while(m--){
        int cal; cin>>cal;
        line.erase(pos[cal]);
        line.push_front(cal);
        pos[cal]=line.begin();
        res.push_back(line.back());
    }
    for(int i=0;i<res.size();i++) cout<<res[i]<<" ";
}

# KHANGTD.XEPHANG
## ĐÈ BÀI
Một lớp có n sinh viên. Các sinh viên có mã số sinh viên (mssv) theo thứ tự từ 1 đến n. Ban đầu các bạn sinh viên xếp hàng theo đúng thứ tự theo mã số sinh viên từ 1 đến n, nghĩa là sinh viên có mssv là 1 ở đầu, tiếp theo là sinh viên có mssv là 2,..., sinh viên có mssv là n ở đứng cuối cùng. Khi thầy giáo gọi một bạn nào đó, thì bạn đó lên đứng đầu hàng. Hỏi sau m lần được gọi, thì thứ tự của các bạn sinh viên sẽ như thế nào?

### INPUT:

Dòng thứ nhất gồm hai số nguyên n, m cách nhau một khoảng trắng (1 ≤ n, m ≤ 10^5), n là số sinh viên và m là số lần thầy giáo gọi.

Dòng tiếp theo gồm m số nguyên a1, a2, ..., am mỗi số cách nhau một khoảng trắng (1 ≤ ai ≤ n), ai là mssv của sinh viên được gọi trong lần gọi thứ i.

### OUTPUT:

Kết quả là m số nguyên, mỗi số cách nhau một khoảng trắng, là mssv của sinh viên từ đầu hàng đến cuối hàng.

## HƯỚNG GIẢI

1. Duy trì một danh sách `cal` để lưu trữ các mã số sinh viên được gọi theo thứ tự.
2. Duy trì một bộ nhớ đệm `check` để đánh dấu sinh viên đã được gọi lên đầu.
3. Lấy các sinh viên đã được gọi theo thứ tự từ cuối lên đầu, và thêm vào danh sách kết quả `res`.
4. Sau đó thêm các sinh viên chưa được gọi vào cuối danh sách kết quả `res`.
5. Cuối cùng, in ra thứ tự của các sinh viên trong danh sách kết quả.

## CODE

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,m; cin>>n>>m;
    vector<int> cal,res;
    unordered_map<int,bool> check;
    for(int i=0;i<m;i++){
        int temp; cin>>temp;
        cal.push_back(temp);
    }
    for(int i=m-1;i>=0;i--){
        if(!check[cal[i]]){
            res.push_back(cal[i]);
            check[cal[i]]=true;
        }
    }
    for(int i=1;i<=n;i++){
        if(!check[i]) res.push_back(i);
    }
    for(int i:res) cout<<i<<" ";
}