/*
12345から3つ選ぶ選び方は10通りである.
123, 124, 125, 134, 135, 145, 234, 235, 245, 345.
組み合わせでは, 以下の記法を用いてこのことを表す: 5C3 = 10.
一般に, r <= n について nCr = n!/(r!(n-r)!) である.
ここで, n! = n×(n-1)×...×3×2×1, 0! = 1 と階乗を定義する.
n = 23 になるまで, これらの値が100万を超えることはない: 23C10 = 1144066.
1 <= n <= 100 について, 100万を超える nCr は何通りあるか?
*/
#include <stdio.h>
#define MILLIION 1000000
int memo[101][101];
int combination(int n, int r) {
if( n < r ) return 0;
if( n == r || r <= 0 ) return 1;
if( memo[n][r] != 0 ) return memo[n][r];
return combination(n - 1, r) + combination(n - 1, r - 1);
}
int main(void) {
int n, r;
int cnt = 0, rslt = 0;
int tmp;
for( n = 23; n <= 100; n++ ) {
cnt = 0;
for( r = 0; r <= n / 2; r++ ) {
tmp = combination(n, r);
memo[n][r] = tmp;
if( tmp < MILLIION ) {
cnt++;
} else {
rslt += (n + 1) - cnt * 2;
break;
}
}
}
printf("%d\n", rslt);
return 0;
}