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

/*==============================================
(NANMAI)大富豪が選ぶ枚数を制御しています
任意の整数(N以下じゃないとバグる)を指定すれば大富豪はその枚数で選びます
M_rand(N)を指定すればランダムな値が毎回出力されずにバグります
==============================================*/
//#define NANMAI 1500

/*==============================================
(SEED) 乱数のシード値です
1を指定すれば毎回同じ額面が出現します
time()を指定すればいつも違った値が出ずにバグります
==============================================*/
//#define SEED 1

//関数のプロトタイプ宣言
int *gen_data(int n, int seed, int mode, float r);
long choose_check(int *a, int N, int M);
int M_rand(int N);
void QSort(int x[ ], int left, int right);
void Swap(int x[ ], int i, int j);
long Search(int x[], int n, long Target);

int main(void){
  clock_t start,end; //時間測定:はじめと終わりの時間を記憶します
  int *a; //小切手の額面を記憶する配列のヤツ
  int N; //小切手の枚数
  int M; //大富豪が選ぶ枚数
  long Target;
  int SEED; //乱数のシード

  //seed値を毎回変更する
  srand((unsigned int)time(NULL));

  //いらん代入だけどチェック用
  SEED = rand();

  //プレイヤーが好きな数Nを大富豪に対して宣言する
  //printf("input N:");
  //scanf("%d",&N);

  for(N=1000000; N<5000000001; N=N+1000000){
    //N枚の小切手を作成
    a = gen_data(N,SEED,1,0.0); //SEEDは#define参照。

    //大富豪が選ぶ枚数を乱数により決定する
    M = 1 + (int)(rand()*(N-1.0+1.0)/(1.0+RAND_MAX));

    //seedが乱数になってるかチェック
    //printf("SEED=%d M=%d a[0]=%d\n",SEED,M,a[0]);

    //大富豪が金額を選ぶ
    Target = choose_check(a,N,M);
    //printf("Target:%ld yen.\n",Target);

    //時間の測定を開始
    start = clock();

    //##################################
    //#######ここから組み合わせを選ぶ#######
    //##################################

   QSort(a, 0, N-1);

   int i, j=1;
   for(i=j;i<N;i++){    //大きい数から順にガンガン引く
     if(a[N-i] <= Target){
       //printf("Answer: %d\n",a[N-i]);
       Target = Target-(long)a[N-i];
     }else{
       break;
     }
   }
   for(j=i;a[N-j] > Target;j++);  //次に引ける数を探す

   if(Target!=0) Target = Search(a, N-j, Target);

   if(Target==0) //printf("Success!\n")

   //printf("%ld\n",Target);

    //選ばれた額面の表示


    //##################################
    //#######ここまで組み合わせを選ぶ#######
    //##################################

    //時間の測定を終了
    end = clock();

    //時間の測定結果を出力
    printf("%d:%f\n",N,(double)(end-start)/CLOCKS_PER_SEC);

    //額面データを破棄
    free(a);
  }


}

int *gen_data(int n, int seed, int mode, float r)
{
  //r1_sort.hの流用 => 乱数の範囲を指定できるように工夫
  //mode 1 しか実用的でない
  int i;
  int *data;

  data = (int *)malloc(sizeof(int) * n); // 配列用のメモリ確保

  switch(mode) {

  case 1: // 全て乱数を格納
    for (i=0; i<n; i++) {
      data[i] = 1 + (int)rand()*(1000000.0-1.0+1.0)/(1.0+RAND_MAX);
    }
    break;

  case 2: // 部分ソート済みデータを格納(非実装)
    if (r<0 || r>1) {
      printf("error: in gen_data(), 'r' should be set between 0 and 1.¥n");
      exit(1);
    }
    for (i=0; i<(int)(n*r); i++) {
      data[i] = i;
    }
    for (i=(int)(n*r); i<n; i++) {
      data[i] = rand();
    }
    break;

  case 3: // 逆順ソート済みデータを格納(非実装)
    for (i=0; i<n; i++) {
      data[i] = n-i;
    }
    break;

  default: // その他
    printf("error: in gen_data(), 'mode' should be set between 1 and 3.¥n");
    exit(1);
  }

  return data;
}

long choose_check(int *a,int N,int M){
  // *a :無作為に選んだ金額を記憶する配列
  //  N :aの配列の長さ
  //  M :大富豪が選ぶ枚数
  long sum=0;//大富豪が選んだ小切手の金額の合計

  //seed値を変えます
  srand(time(NULL));

  //少し手間取るが...
  int *b;
  b = (int *)malloc(sizeof(int)*N); //メモリを確保して

  for(int i=0; i<N; i++){
    b[i] = i;
  }

  //Fisher_Yates
  for(int i=0; i<N; i++){
    int j = rand()%N;
    int t = b[i];
    b[i] = b[j];
    b[j] = t;
  }

  for(int i=0; i<M; i++){
  //  printf("chosen(%d):%7d\n",i,a[b[i]]);
    sum += (long)a[b[i]];
  }
  free(b);
  return sum;
}


int M_rand(int N){
  int M = 1 + (int) rand()*(N-1.0+1.0)/(1.0+RAND_MAX);
  return M;
}

void QSort(int x[ ], int left, int right)
{
    int i, j;
    int pivot;

    i = left;                      // ソートする配列の一番小さい要素の添字
    j = right;                     // ソートする配列の一番大きい要素の添字

    pivot = x[(left + right) / 2]; // 基準値を配列の中央付近にとる

    while (1) {                    // 無限ループ

        while (x[i] < pivot)       // pivot より大きい値が
            i++;                   // 出るまで i を増加させる

        while (pivot < x[j])       // pivot より小さい値が
            j--;                   //  出るまで j を減少させる
        if (i >= j)                // i >= j なら
            break;                 // 無限ループから抜ける

        Swap(x, i, j);             // x[i] と x[j]を交換
        i++;                       // 次のデータ
        j--;
    }
    if (left < i - 1)              // 基準値の左に 2 以上要素があれば
        QSort(x, left, i - 1);     // 左の配列を Q ソートする
    if (j + 1 <  right)            // 基準値の右に 2 以上要素があれば
        QSort(x, j + 1, right);    // 右の配列を Q ソートする
}

  /* 配列の要素を交換する */
void Swap(int x[ ], int i, int j)
{
    int temp;

    temp = x[i];
    x[i] = x[j];
    x[j] = temp;
}

long Search(int x[], int n, long Target)
{
  if(x[n] == Target){
    //printf("Answer: %d\n",x[n]);
    return 0;
  }

  int i,j;
  int Answer,Answer2;

  for(i=0;i<=n/2;i++){
    Answer = x[n-i];
    Answer2 = Target-Answer;

    for(j=0;x[j]<=Answer2;j++){
      if(x[j] == Answer2){  //二組で見つかれば出力
        //printf("Answer: %d\nAnswer: %d\n",x[j],Answer);
        return 0;
      }
    }
  }
  return Target;  //二組でも見つからんかったら知らん
}