Coin

NOIP2015年普及组第一题。

问题描述

国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续 N 天每天收到 N 枚金币后，骑士会在之后的连续 N+1 天里，每天收到 N+1 枚金币。

请计算在前 K 天里，骑士一共获得了多少金币。

输入格式

• 输入文件名为 coin.in。
• 输入文件只有 1 行，包含一个正整数 K，表示发放金币的天数。

输出格式

• 输出文件名为 coin.out。
• 输出文件只有 1 行，包含一个正整数，即骑士收到的金币数。

输入输出样例1

输入	输出
6	14

骑士第一天收到一枚金币；第二天和第三天，每天收到两枚金币；第四、五、六天，每天收到三枚金币。因此一共收到 1+2+2+3+3+3=14 枚金币。

输入输出样例2

输入	输出
1000	29820

数据说明

对于100%的数据，1 ≤ K ≤ 10,000。

参考代码

1. 模拟for循环[+]

   #include <iostream>
   using namespace std;
   
   int main(){
   	int d,i,m=0;
   	
   	cin >> d;
   	for(i=1;i<d;i++){
   		m = m + i*i;
   		d = d - i;
   	}
   	m = m + i * d;
   	
   	cout << m << endl;
   	
   	return 0;
   }
   

2. 模拟while循环[+]

   #include <iostream>
   using namespace std;
   
   int main(){
       int d,i=1,m=0;
       
       cin >> d;
       while(i<d){
       	m = m + i*i;
       	d = d - i;
       	i++;
   	}
       m = m + i * d;
       
       cout << m << endl;
       
       return 0;
   }
   

3. 直接公式法[+]

   #include <iostream>
   #include <cmath>
   using namespace std;
   
   int main(){
       double d;
       int z=0,m=0;
       
       cin >> d;
       z = (sqrt(1+8*d)-1)/2;
       m = z*(z+1)*(2*z+1)/6;
       m = m + (d-(z+z*z)/2) * (z+1);
       
       cout << m << endl;
       
       return 0;
   }
   

4. 公式判断法[+]

   #include <iostream>
   using namespace std;
   
   int main(){
       int d,m=0,z=0,i=0;
       
       cin >> d;
       do{
       	i++;
       	z = (1+i)*i/2;
       	m = m + i*i;
   	}while(z<d);
       m = m + (d-z) * i;
       
       cout << m << endl;
       
       return 0;
   }
   

5. 暴力求解法[+]

   #include <iostream>
   using namespace std;
   
   int main(){
       int d,m=0,z=0,i=0;
       
       cin >> d;
   	for(i=1;i<d;i++){
   		z = (1+i)*i/2;
   		m = m + i*i;
   		if(z>=d) break;
   	}
   	m = m + (d-z) * i;    
       cout << m << endl;
       
       return 0;
   }
   

6. 二分优化法[+]

   #include <iostream>
   using namespace std;
   
   int main(){
       int d,z,left=1,right,mid,m;
       cin >> d;
   
       right = d;
       while(left<=right){
       	mid = (left+right)/2;
       	z = (mid+1)*mid/2;
       	if(z<d) left = mid+1;
       	else right = mid-1;
   	}
   	z = (1+left) * left /2;
   	m = left * (left+1)*(2*left+1)/6 +(d-z) * left;
   	
       cout << m << endl;
   	   
       return 0;
   }
   

辽师张大为@https://daweizh.github.io/csp/