UVa11401

Problem G Triangle Counting

Input: Standard Input

Output: Standard Output

You are given n rods of length 1, 2…, n. You have to pick any 3 of them & build a triangle. How many distinct triangles can you make? Note that, two triangles will be considered different if they have at least 1 pair of arms with different length.

Input

The input for each case will have only a single positive integer n (3<=n<=1000000). The end of input will be indicated by a case with n<3. This case should not be processed.

Output

For each test case, print the number of distinct triangles you can make.

Sample Input Output for Sample Input

Problemsetter: Mohammad Mahmudur Rahman

  1 法一！！
  2 /*
  3 先打表！！！后推公式！！！
  4 
  5 i     3   4    5    6     7      8      9      10     11    12     13     14     15     16     17     18
  6  
  7 f[i]  0   1    3    7     13     22     34     50     70    95     125    161    203    252    308    372
  8 
  9 做差    1    2    4    6      9      12      16     20    25    30      36     42     49     56     64
 10 
 11 再做差    1    2    2     3      3       4       4      5     5     6        6      7      7     8
 12 
 13 在奇数项做差和偶数项做差即可！！！     
 14 */
 15 
 16 
 17 /*//一开始TLE！！后来就把它用来打表了，推出了通项公式！！！
 18 
 19 记得一道做过fft的题，打这个表轻轻松松！！！
 20 #include<stdio.h>
 21 #include<string.h>
 22 #include<algorithm>
 23 #include<math.h>
 24 #include<queue>
 25 #include<set>
 26 #include<vector>
 27 #include<bitset>
 28 using namespace std;
 29 typedef long long ll;
 30 
 31 const int M=1000010;
 32 ll s[M],f[M];
 33 int get(){
 34     char c;
 35     int res=0;
 36     while(c=getchar(),!isdigit(c));
 37     do{
 38         res=(res<<3)+(res<<1)+(c-'0');
 39     }while(c=getchar(),isdigit(c));
 40     return res;
 41 }
 42 
 43 */
 44 
 45 
 46 int main()
 47 {
 48     ll i,ans1,ans2,ans3,ans,n,m;
 49     while(~scanf("%lld",&n))
 50     {
 51         if(n<3)break;
 52         ll k=0;f[n+1]=n;
 53         while((++k)<=n)f[n+1-k]=f[n+1+k]=n-k;
 54         f[1]=f[0]=0;
 55         //for(i=0;i<=2*n;i++)printf("%lld**",f[i]);
 56         for(i=1;i<=n;i++)f[i*2]--;
 57         for(i=1;i<=2*n;i++)f[i]/=2;
 58         //for(i=0;i<=2*n;i++)printf("%lld**",f[i]);
 59         s[1]=0;
 60         ll ans=0;
 61         for(i=2;i<=2*n;i++)s[i]=s[i-1]+f[i];
 62         for(i=1;i<=n;i++)
 63         {
 64             ans+=s[2*n]-s[i];
 65             ans-=(i-1)*(n-i);
 66             ans-=(n-1);
 67             ans-=(n-i)*(n-i-1)/2;
 68         }
 69         printf("%lld**
",ans);
 70     }
 71     return 0;
 72 }
 73 
 74 
 75 
 76 
 77 
 78 
 79 #include<stdio.h>
 80 #include<string.h>
 81 #include<algorithm>
 82 #include<math.h>
 83 #include<queue>
 84 #include<set>
 85 #include<vector>
 86 #include<bitset>
 87 using namespace std;
 88 typedef long long ll;
 89 
 90 int main()
 91 {
 92     ll ans,k,n;
 93     while(1)
 94     {
 95         n=get();
 96         if(n<3)break;
 97         if(n%2==0){k=n/2-1;ans=k*(4*k*k+3*k-1)/6;printf("%lld
",ans);continue;}
 98         k=(n-1)/2-1;ans=k*(4*k*k+3*k-1)/6+(n/2-1)*(n/2);
 99         printf("%lld
",ans);
100     }
101     return 0;
102 }
103 
104 
105 
106 
107 
108 法2！！
109 
110 
111 
112 
113 
114 /*
115 递推：
116 设最大边为x的三角形有c[x]个，y+z>x；
117 
118 y的值  z的个数 
119 1       0
120 2       1
121 3       3
122 。。。。。
123 x-1     x-2
124 
125 
126 除去y=z的情况有（x-1）/2种！！
127 
128 剩下的再除以2即可！！
129 
130 C[x]= ((x-1)*(x-2)/2-(x-1)/2)/2;
131 
132 */ 
133 #include<stdio.h>
134 #include<string.h>
135 #include<algorithm>
136 #include<math.h>
137 #include<queue>
138 #include<set>
139 #include<vector>
140 #include<bitset>
141 using namespace std;
142 typedef long long ll;
143 
144 const int M=1000010;
145 ll f[M];
146 
147 int get(){
148     char c;
149     int res=0;
150     while(c=getchar(),!isdigit(c));
151     do{
152         res=(res<<3)+(res<<1)+(c-'0');
153     }while(c=getchar(),isdigit(c));
154     return res;
155 }
156 
157 
158 int main()
159 {
160     ll i;
161     int n;
162     f[3]=0;
163     for(i=4;i<M;i++)f[i]=f[i-1]+((i-1)*(i-2)/2-(i-1)/2)/2;
164     while(1)
165     {
166         n=get();
167         if(n<3)break;
168         printf("%lld
",f[n]);
169     }
170     return 0;
171 }

View Code