spoj 1167 <MINCOUNT>
http://www.spoj.com/problems/MINCOUNT/
一个高度为h的正立三角形，由硬币拼成，现在把这个三角形通过一动硬币位置变成倒立等大的三角形，求最少移动硬币数。
其实也就是求正立与倒立两个三角形最小不重叠部分，列几个例子我发现，重叠部分最大是三分之二，即不重叠的就是三分之一。高度为h的三角形共由[h*(h+1)]/2个硬币组成，它的三分之一=[h*(h+1)]/6.但是数据较大，会溢出。我们使h=2a+b，h+1=3c+d。
答案就是变成了[(2a+b)*(3c+d)]/2=ac+(2ad+3bc+bd)/6.
代码：
1 /* 2 Author: traveller_c 3 PROG: spoj1167 4 DATE:2015.3.5 5 */ 6 7 #include<iostream> 8 #include<stdio.h> 9 10 using namespace std; 11 12 unsigned long long h,ans,a,b,c,d; 13 14 void solve() 15 { 16 scanf("%lld",&h); 17 a=h/2;b=h%2;h++;c=h/3;d=h%3; 18 ans=a*c+(3*b*c+2*a*d+b*d)/6; 19 printf("%lld\n",ans); 20 } 21 22 int main() 23 { 24 int t;cin>>t; 25 while(t--) 26 { 27 solve(); 28 } 29 //system("pause"); 30 return 0; 31 }
原文：http://www.cnblogs.com/travelling-oi/p/4317792.html