Uva-11401-Triangle Counting（数学的導出）
831 ワード
1からnまでの整数の中から3つの数を選んで三角形を作ります。いくつかのグループ法があります。
テーマリンク:http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&page=show_problem&category=469&problem=2396
——>>x＋y＞zを設定し、
x>z-y;
だからz-yyを列挙して、xを見ていくつかの選択法があります。
二等辺三角形を除いて、計算の半分を減らします。
午後、先輩の指導のもとで、OKです。Uvaで64桁の整数を使うなら、%I 64 dではなく%lldを使うべきです。
テーマリンク:http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&page=show_problem&category=469&problem=2396
——>>x＋y＞zを設定し、
x>z-y;
だからz-y
二等辺三角形を除いて、計算の半分を減らします。
#include <iostream>
using namespace std;
const int maxn = 1000000 + 10;
long long f[maxn];
int main()
{
int n;
f[3] = 0;
for(long long i = 4; i < maxn; i++)
f[i] = f[i-1] + ((i-1)*(i-2)/2 - (i-1-i/2))/2;
while(cin>>n)
{
if(n < 3) return 0;
cout<<f[n]<<endl;
}
return 0;
}
午後、先輩の指導のもとで、OKです。Uvaで64桁の整数を使うなら、%I 64 dではなく%lldを使うべきです。