#include <stdio.h>
#include <string.h>

#define MAX 100

typedef struct {
    char ma[10];
    char hodem[30];
    char ten[20];
    char gt[5];
    int namsinh;
    float luong;
} NV;

void nhapDS(NV a[], int *n) {
    *n = 6;
    NV tmp[6] = {
        {"E1001","Trần Văn","Bình","Nam",1996,12},
        {"E1002","Trần Mai","Hương","Nữ",1995,13.5},
        {"E1003","Nguyễn Thành","Trung","Nam",1994,14},
        {"E1004","Lê Thanh","Hà","Nữ",1998,10},
        {"E1005","Phan Đức","Anh","Nam",1992,15.5},
        {"E1006","Dương Bình","Minh","Nam",2000,8.5}
    };
    for(int i=0;i<6;i++) a[i]=tmp[i];
}

void xuatDS(NV a[], int n) {
    printf("\n%-6s %-12s %-10s %-5s %-8s %-6s\n",
           "MS","Ho dem","Ten","GT","Nam","Luong");
    for(int i=0;i<n;i++)
        printf("%-6s %-12s %-10s %-5s %-8d %.1f\n",
               a[i].ma,a[i].hodem,a[i].ten,a[i].gt,a[i].namsinh,a[i].luong);
}

int timKiemTen(NV a[], int n, char ten[]) {
    int l=0, r=n-1;
    while(l<=r) {
        int mid=(l+r)/2;
        int cmp=strcmp(a[mid].ten,ten);
        if(cmp==0) return mid;
        if(cmp<0) l=mid+1; else r=mid-1;
    }
    return -1;
}

void chen(NV a[], int *n, NV x, int vt) {
    for(int i=*n; i>vt; i--) a[i]=a[i-1];
    a[vt]=x;
    (*n)++;
}

void sapXepChen(NV a[], int n) {
    for(int i=1;i<n;i++){
        NV key=a[i];
        int j=i-1;
        while(j>=0 && strcmp(a[j].ten,key.ten)>0){
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=key;
    }
}

void xoaLonTuoi_Luong(NV a[], int *n) {
    int namHienTai=2025;
    for(int i=0;i<*n;i++){
        int tuoi = namHienTai - a[i].namsinh;
        if(tuoi>30 && a[i].luong>15.5){
            for(int j=i;j<*n-1;j++) a[j]=a[j+1];
            (*n)--; i--;
        }
    }
}

int main() {
    NV a[MAX]; 
    int n;

    nhapDS(a,&n);
    printf("== Danh sach ban dau ==\n");
    xuatDS(a,n);

    // 1. Sắp xếp theo tên
    sapXepChen(a,n);
    printf("\n== Sau khi sap xep theo ten ==\n");
    xuatDS(a,n);

    // 2. Tìm người tên "Anh"
    int k = timKiemTen(a,n,"Anh");
    if(k!=-1) printf("\nTim thay ten Anh tai vi tri %d\n", k+1);
    else printf("\nKhong tim thay!\n");

    // 3. Thêm nhân viên vào vị trí 3
    NV moi = {"E1007","Đinh Thu","Hòa","Nữ",1998,11.6};
    chen(a,&n,moi,2);

    printf("\n== Sau khi chen nhan vien moi ==\n");
    xuatDS(a,n);

    // 4. Xóa nhân viên >30 tuổi và lương >15.5
    xoaLonTuoi_Luong(a,&n);
    printf("\n== Sau khi xoa ==\n");
    xuatDS(a,n);

    return 0;
}