招新笔试题系列——买包子
Time Limit: 2000/1000ms (Java/Others)
Problem Description:
小华刚到大学,一天早上她替她室友买早餐,一共要N个包子。阿姨跟小华说,饭堂里面有肉包,菜包和叉烧包3种包子。你能帮小华算算这N个包子一共有多少种搭配方式吗?(每种包子都至少有一个)
Input:
输入包含多组数据,每组数据是一个n (5<=n<=500)
Output:
对于每组输入,输出结果
Sample Input:
86
Sample Output:
2110 解题思路:找规律,水题!!!因为每种包子至少有一个,所以先减去3,这对结果没什么影响。结合样例,再列举一种情况,当n=5(最小取5)时,此时需再买2个包子,共有C(3,1)(即同一种包子买2个)+C(3,2)(即从3中包子中选2个)=(2+1)*(2+2)/2=3*4/2=6种方案。再结合样例,当n=6时即需再购买3个包子,有(3+1)*(3+2)/2=4*5/2=10种选择方案;当n=8时即需再购买5个包子,有(5+1)*(5+2)/2=6*7/2=21种选择方案。综上,公式为n-=3,(n+1)*(n+2)/2,水过。 AC代码:
1 #include2 using namespace std; 3 int main() 4 { 5 int n; 6 while(cin>>n){ 7 n-=3; 8 cout<<((n+1)*(n+2)/2)<