Follows 10049.c (Total 35 lines):

/* @JUDGE_ID:4461XX 10049 C "DP+bsearch" */
/* A */
#include<stdio.h>
#define MAX 673366 /* f(2,000,000,000) = 673365 */

int data[MAX] , target ;
int b_search( int from , int tail )
{
	while( 1 ){
		if( data[(from+tail)/2]>=target &&
	    	data[(from+tail)/2-1]<target ) return (from+tail)/2 ;	
		if( data[(from+tail)/2]<target ) from = (from+tail)/2+1 ;
		else tail = (from+tail)/2 ;
	}
}
int main( void )
{
	int n , poi ;

	data[1] = 1 ; /* make data table */
	data[2] = 3 ;
	poi = 2 ;
	for( n=3 ; n<MAX ; n++ ){
		while( n>data[poi] ) poi++ ;
		data[n] = data[n-1] + poi ;
	}

	while( scanf( "%d" , &target )==1 ){
		if( !target ) break ;
		printf( "%d\n" , b_search( 1 , MAX-1 ) ) ;
	}
	
	return 0 ;
}
/* @END_OF_SOURCE_CODE */

Back to statistics
Ya-Lin Huang (C)
huangyl@gmail.com