#include<stdio.h>
#include<windows.h>
#include <time.h>

int Pow(int TWO,int M)
{
		int Product=1,i;
		for(i=0;i<M;i++)
		{
		Product=Product * TWO;}

		return Product;

}
void insertSort(int a[], int length)
{
    int i, j, value;

    for (i = 1; i < length; ++i) {
        value = a[i];
        for (j = i - 1; j >= 0 && a[j] > value; --j) 
            a[j + 1] = a[j];  
        a[j + 1] = value;
    }
}
 int loga2(int x )
{
  int ans = 0 ;
  while( x>>=1 ) ans++;
  return ans ;
}
int enterData(int dest[])
{
    FILE *fr;
    int i=0;
    if((fr=fopen("wartosci.txt","r"))==NULL)printf("Blad odczytu.");
    while(!feof(fr)){
         fscanf(fr,"%d ",&dest[i]);
        i++;
    }
	fclose(fr);
	return i;
}
int sumuj(int arr[],int N)
{
	int i,suma=0;
	for(i=0;i<N;i++)
	{
		suma+=arr[i];
	}
	return suma;
}

void usun(int arr[], int arrCls[],int N)
{
	FILE *fw;
	int i,j=0;
	if((fw=fopen("wartosci.txt","w"))==NULL)printf("Blad zapisu.");
	
	for(i=0;i<N;i++){
		
		if(arr[i]==arrCls[j])
			j++;
		else	
			fprintf(fw,"%d ",arr[i]); 		
	}
	fclose(fw);
}
void wyswDop(int arr[],int arrCls[],int N)
{
	int i,j=0;
	for(i=0;i<N;i++){
		
		if(arr[i]==arrCls[j])
			j++;
		else	
			printf("%d ",arr[i]); 		
	}	
}

void mieszaj(int arr[], int N)
{
	int n=N/2;
	int i,los,los2,zast;
	srand(time(NULL));
	for(i=0;i<N;i++)
	{
		los=rand()%N;
		los2=rand()%N;
		zast=arr[los];
		arr[los]=arr[los2];
		arr[los2]=zast;
	}
}
void wezPierwsze(int arr[],int arrDest[],int N1)
{
	int i;
	for(i=0;i<N1;i++)
		arrDest[i]=arr[i];
}


int main()
{
	int i,j,N,nZ,k,suma=0,cena,min,n,m,suma1,p,n1,stab;
	float procent;
	int arr[50],wynik[24],tab2[50],mniejsza[24];
	int *wskMn,*wskArr, *wsk;
	char c;
	
	while(1){
		wskArr=arr;
		wskMn=mniejsza;
		wsk=arr;
		n=0;
		procent=0;
		printf("*Teraz mozesz edytowac dane.\n");
		getch();
		N=enterData(wskArr);
		nZ=N;
		
		if(N>23)
		{
			mieszaj(wskArr,N);
			wezPierwsze(wskArr,wskMn,23);
			insertSort(wskArr,N);
			insertSort(wskMn,23);
			wskArr=wskMn;
			stab=sumuj(wskArr,23);
			N=23;
		}
		else
		{
			insertSort(wskArr,N);
			stab=sumuj(wskArr,N); 
		}
		Sleep(100);
		min=5000;
		printf("Wczytano %d przedmiotow o wartosci %d.\n",N,stab);
		printf("Podaj cene: ");
		scanf("%d",&cena);
		
		for(j=Pow(2,N)-1;j>0;j--){
			//procent=100-(((float)j)/((float)Pow(2,N)-1))*100;
			//printf("%.0f%%%\r",procent);
			k=j;
			p=0;
			while(k>0){
				if(k%2==1) {
					suma+=wskArr[p];
					tab2[n]=wskArr[p];
					n++;
					}
				k=k/2;
				p++;
			}
			if(suma>=cena){
				if(suma<min){
					for(m=0;m<n;m++){
							wynik[m]=tab2[m];
							suma1=suma;
						}
						min=suma;
						n1=n;	
					}
				}
			suma=0;
			n=0;
			if(suma1 - cena <= 1) break;
		}
		printf("\n");
		
		printf("A : ");
		wynik[n1]=0;
		for(i=0;i<n1;i++)
			printf("%d ",wynik[i]);
		printf("\t->\t%d\n",suma1);
		
		
		wskArr=wsk;
		N=nZ;
		printf("\n");
		printf("Czy usunac %d wartosci?\n",n1);fflush(stdin);
		c=getchar();
		if(c!='n'){
			usun(wskArr,wynik,N);
			printf("*Usuwanie zakonczone.\n");
			Sleep(1000);
			system("cls");
		}
		else{
			system("cls");
			Sleep(100);
		} 
	}
}