当前位置:编程学习 > C/C++ >>

UVA 11401 - Triangle Counting

2013-10-28 13:33 95人阅读 评论(0) 收藏 举报
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 易做图. How many distinct 易做图s can you make? Note that, two 易做图s 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 易做图s you can make.
 
Sample Input                                                  Output for Sample Input
5
8
0
3
22
 
Problemsetter: Mohammad Mahmudur Rahman
 
解题思路,分段法,f [n] 记录最长的那条边不超过n的放法数, 假设c[n] 为最长边为n的放法数  f [n] = f [n-1] + c[n] 。
 
假设最长边为z,其它为 x,y;
则   z-x < y < z
当  x=1 时, z-1<y<z  0 种方案,
当  x=2 时, z-2<y<z  1 种方案,
......................................................
当  x=z-1时, 1<y<z  z-2种方案
所以总计 (z-1)*(z-2)/2 种方案
但是其中包含了x与y想等的情况,因为 x取值为 [ z/2+1 , z-1 ] 区间内可能 x,y相等,共 (z-1)- (z/2+1)+1=z/2-1 种方案
而且x,y与 y,x认为为两个,重复计算了,所以除以2
所以 c[n]= [ (z-1)*(z-2)/2 -(z/2-1) ] / 2
 
 
#include <iostream>  
using namespace std;  
  
const int maxn=1000000;  
unsigned long long f[maxn+10];  
int n;  
  
void ini(){  
    f[3]=0;  
    for(long long z=4;z<=maxn;z++){  
        f[z]=f[z-1] + ( (z-1)*(z-2)/2 - (z/2 -1) )/2;  
    }  
}  
  
int main(){  
    ini();  
    while(cin>>n && n>=3){  
        cout<<f[n]<<endl;  
    }  
    return 0;  
}  

 

 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,