//Name:Md.Kamrul Hasan
//ID:201-15-13981

//1.phonebook
 #include <bits/stdc++.h>

using namespace std;


void kamrul_swap(string* a, string* b)
{
    string t = *a;
    *a = *b;
    *b = t;
}


int kamrul_partition (string arr[], int low, int high)
{
    string pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high- 1; j++)
    {

        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            kamrul_swap(&arr[i], &arr[j]);
        }
    }
    kamrul_swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}


void kamrul_quickSort(string arr[], int low, int high)
{
    if (low < high)
    {

        int pi = kamrul_partition(arr, low, high);


        kamrul_quickSort(arr, low, pi - 1);
        kamrul_quickSort(arr, pi + 1, high);
    }
}

int kamrul_binarySearch(string arr[], int l, int r, string x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;


        if (arr[mid] == x)
            return mid;


        if (arr[mid] > x)
            return kamrul_binarySearch(arr, l, mid - 1, x);

        return kamrul_binarySearch(arr, mid + 1, r, x);
    }

    return -1;
}

int main()
{
    int n, i;
    cout << "Number of your students: ";
    cin >> n;

    string kamrul_name[n], kamrul_phn[n], x;

    cout << "\n";
    for(i = 0; i < n; i++) {
        cin.ignore();
        cout << "Name : ";
        cin >> kamrul_name[i];
        cin.ignore();
        cout << "Phone : ";
        cin >>  kamrul_phn[i];
    }

    cout << "\nSearch Friend: ";
    cin >> x;

    kamrul_quickSort(kamrul_name, 0, n-1);

    cout << "Contact List\n";
    for(i = 0; i < n; i++) {
        cout << "Name : ";
        cout << kamrul_name[i] << endl;
        cout << "Phone : ";
        cout << kamrul_phn[i] << endl;
    }

    cout << "\n";
    int r = kamrul_binarySearch(kamrul_name, 0, n - 1, x);

    if(r == -1) {
        cout << "Contact Details not Found\n";
    }
    else {
        cout << "Contact Details Found\n";
        cout << "Name : ";
        cout << kamrul_name[r] << endl;
        cout << "Phone : ";
        cout <<  kamrul_phn[r] << endl;
    }

    return 0;
}



//2.knapsak
#include <bits/stdc++.h>

using namespace std;


struct Item
{
    int value, weight;

    Item(int value, int weight)
        : value(value), weight(weight){}
};

bool kamrul_cmp(struct Item a,struct Item b)
{
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 > r2;
}


double kamrul_Knapsack(struct Item kamrul_arr[],
                          int N, int size)
{

    sort(kamrul_arr, kamrul_arr + size, kamrul_cmp);


    int curWeight = 0;

    double finalvalue = 0.0;

    for (int i = 0; i < size; i++)
    {


        if (curWeight + kamrul_arr[i].weight <= N)
        {
            curWeight += kamrul_arr[i].weight;
            finalvalue += kamrul_arr[i].value;
        }


        else
        {
            int remain = N - curWeight;
            finalvalue += kamrul_arr[i].value
                          * ((double)remain
                             / kamrul_arr[i].weight);

            break;
        }
    }

    return finalvalue;
}


int main()
{

    int N = 15;


    Item kamrul_arr[] = { { 5, 10 },
        { 3, 4 },
        { 5, 3 },
        { 7, 6 },
        {6,2}
    };

    int size = sizeof(kamrul_arr) / sizeof(kamrul_arr[0]);


    cout << "Maximum profit earned = "
         << kamrul_Knapsack(kamrul_arr, N, size);
    return 0;
}