053.cpp

Go to the documentation of this file.

#include <iostream>
using namespace std;

const int N = 100;

class ncr_million
{
  unsigned long x[N][N];                
public:
    ncr_million ();
  void reset();
  void printAll ();
  unsigned long count ();
};

void ncr_million::reset(){
unsigned long *begin = &(x[0][0]);
  for (unsigned long *p = begin; p-begin < N * N; p++)
    *p=0;
}

ncr_million::ncr_million ()
{
  reset();

  x[0][0] = x[0][1] = 1; 

  for (int i = 1; i < N; i++)
    {
      x[i][0] = 1;
      for (int j = 1; j <= i; j++)
        {
          unsigned long temp = x[i - 1][j - 1] + x[i - 1][j];
          if (temp > 1000000)
            x[i][j] = 1000001;
          else 
            x[i][j]=temp;
        }
      x[i][i+1] = 1;
    }
}

void
ncr_million::printAll ()
{
  for (int i = 0; i < N; i++)
    {
      for (int j = 0; j <= i+1; j++)
        cout << x[i][j];
cout << '\n';
    }
}

unsigned long
ncr_million::count ()
{
  unsigned long cnt = 0;
  unsigned long *begin = &(x[0][0]);
  for (unsigned long *p = begin; p-begin < N * N; p++)
    if (*p > 1000000)
      cnt++;
  return cnt;
}

int
main ()
{
  ncr_million ncr;
  //ncr.printAll();
  cout << ncr.count () << endl;
}