#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;
    FILE *fl;
     typedef struct
	 {
        char fio[30];
        unsigned int salary;
        unsigned int tariff;
		unsigned int hours;
	 } TPeople;
              TPeople stud[30]; 
                char name[20]; 
                int nst=0; 
                int menu();
                void nnf(); 
                void newf();
                void spisok(); 
				int f_line( TPeople[], int );
				int f_inter( TPeople[], int);
				void opf(); 
                void resc(); 
                void resf(); 
				void s_qs();
				void s_ch();
    int main()
	{
         while (true)
		 {
            switch (menu())
			{
                case 1: nnf(); break;
                case 2: newf(); break;
                case 3: spisok(); break;
                case 4: opf(); break;
                case 5: resc(); break;
                case 6: resf(); break;
				case 7: s_qs(); break;
				case 8: s_ch(); break;
				case 9: cout << f_line(stud, nst) + 1 << endl; break;
				case 10: cout << f_inter(stud, nst) + 1 << endl; break;
				case 11: return 0;
                default: "Error. Repeat please.";
			}
              puts("Press any key to continue");
              getch(); system("cls");
		 }
	}
             int menu() 
			 {
                  cout << "Choose:" << endl;
                  cout << "1. Input file name" << endl;
                  cout << "2. New file" << endl;
                  cout << "3. Input list" << endl;
                  cout << "4. Open file" << endl;
                  cout << "5. Output result" << endl;
                  cout << "6. Output into fail" << endl;
		  cout << "7. Quicksort" << endl;
		  cout << "8. Sort of choisening" << endl;
		  cout << "9. Find by line search" << endl;
				  cout << "10. Find by interpol" << endl;
		          cout << "11. Exit" << endl;
     int i;
     cin >> i;
     return i;
			 }
            void nnf() 
			{ 
               cout << "Input file name" << endl;
               cin >> name;
			}
                    void newf() 
					{
                       if ((fl = fopen(name,"wb"))==NULL)
					   {
                          cout << "Creating error"<<endl;
                          exit(1);
					   }
         
					   cout << "OK" << endl;
                       fclose(fl);
					}

					
					      void spisok() 
						  {
                            if ((fl = fopen(name,"rb+"))==NULL)
							{
                               cout << "Creating error"<<endl;
                               exit(1);
							}
                                 cout << "Input number of people " << endl;
                                 cin >> nst;
                               for (int i=0; i<nst; i++)
							   {
                                   cout << "Input name: ";
                                   cin >> stud[i].fio;
                                   cout << "Input hours of work: ";
                                   cin >> stud[i].hours;
                                   cout << "Input tariff: ";
                                   cin >> stud[i].tariff;
								   fwrite( &stud[i], sizeof(TPeople), 1, fl );
							   }
                                       fclose(fl);
						  }
      void opf() 
	  {
        if ((fl = fopen(name,"rb"))==NULL)
		{
          cout << "Opening error"<<endl;
          exit(1);
		}
               nst=0; TPeople std;
           while(true)
		   {
             int nwrt = fread( &std, sizeof(TPeople), 1, fl );
             if (nwrt!=1) break;
             stud[nst]=std;
             cout << stud[nst].fio << " " << stud[nst].hours<< " " << stud[nst].tariff << endl;
             nst++;
		   }
              fclose(fl);
	  }
                  void resc() 
				  {
                     for ( int i=0; i<nst; i++ ){
						 	if( stud[i].hours > 144 ) stud[i].salary = 0.88 * 144 * stud[i].tariff + 
								0.88 * ( stud[i].hours - 144 ) * stud[i].tariff * 2;
							else stud[i].salary = 0.88 * stud[i].hours * stud[i].tariff;
						 cout << stud[i].fio<<"   " << stud[i].salary << endl;
						 }
				  }
                     void resf() 
					 {
                        char namet[30];
                        FILE *ft;
                        cout << "INput file name" << endl;
                        cin >> namet;
                        if ((ft = fopen(namet,"w"))==NULL)
						{
                            cout << "Creating error "<<endl;
                            exit(1);
						}
                            char s[80];
                            for (int i=0; i<nst; i++)
                        	{
								itoa( stud[i].salary, s, 10);
                                strcat(s, "\n"); 
                                fputs(s, ft);
							}
                                fclose(ft);
					 }
void s_ch()
{
	int imin, i, j, t;

	for( i = 0; i < nst-1; i++)
	{
		imin = i;
	for( j = i+1; j < nst; j++)
		if( stud[imin].hours > stud[j].hours ) imin = j;
		if( imin != i)
		{
			t = stud[imin].hours;
			stud[imin].hours = stud[i].hours;
			stud[i].hours = t;
		}
	}
	for( i = 0; i < nst; i++ ){
		cout << stud[i].fio << " " << stud[i].hours<< " " << stud[i].tariff << endl;
	}
}
void s_qs(){

	struct
	{
		int l;
		int r;
	} stack[20];
int i, j, left, right, x, s = 0;
TPeople t;

	stack[s].l = 0; stack[s].r = nst-1;

while( s != -1 )
{
	left = stack[s].l; right = stack[s].r;
	s--;
	while( left < right )
	{
		i = left; 
		j = right; 
		x = stud[(left+right)/2].hours;
		while( i <= j )
		{
			while( stud[i].hours < x ) i++;
			while( stud[j].hours > x ) j--;
			if(i <= j )
			{
				t = stud[i]; stud[i] = stud[j]; stud[j] = t;
				i++; j--;
			}
		}
		if(( j - left) < ( right - i ))
		{
			if( i < right ){
				s++;
				stack[s].l = i; 
				stack[s].r = right;
			}
			right = j;
		}
		else{
			if( left < j ){
				s++;
				stack[s].l = left; stack[s].r = j;
			}
		}
	}
}
for( i = 0; i < nst; i++ ){
		cout << stud[i].fio << " " << stud[i].hours<< " " << stud[i].tariff << endl;
	}
}

int f_line( TPeople stud[], int nst )
{
	int check;
	cout << "Input check: " << endl;
	cin >> check;
	for( int i = 0; i < nst; i++ )
		if( stud[i].hours == check ) return i;
	return -2;
}

int f_inter( TPeople stud[], int nst )
{
	int i = 0, j = nst-1, m, check;
	cout << "Input check: " << endl;
	cin >> check;
	while(i < j)
	{
		if( stud[i].hours == stud[j].hours )
			if( stud[i].hours == check ) return i;
			else return -2;

	m = i + (j-i)*(check-stud[i].hours)/(stud[j].hours-stud[i].hours);
	if(stud[m].hours == check) return m;
	else
		if(check > stud[m].hours) i = m+1; else j = m-1;
	}
	return -2;
}