Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Description
You are given N sticks having distinct lengths; you have to form some triangles using the sticks. A triangle is valid if its area is positive. Your task is to find the number of ways you can form a valid triangle using the sticks.
Input
Input starts with an integer T (≤ 10), denoting the number of test cases.
Each case starts with a line containing an integer N (3 ≤ N ≤ 2000). The next line contains N integers denoting the lengths of the sticks. You can assume that the lengths are distinct and each length lies in the range [1, 109].
Output
For each case, print the case number and the total number of ways a valid triangle can be formed.
Sample Input
3
5
3 12 5 4 9
6
1 2 3 4 5 6
4
100 211 212 121
Sample Output
Case 1: 3
Case 2: 7
Case 3: 4
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h> using namespace std;
typedef long long LL;
LL a[+];
int n; int Binary_search(int x)
{
int l = ,r = n-;
while(l<=r)
{
int mid = (l+r)/;
if(a[mid] == x)
return mid;
else if(a[mid] > x)
r= mid-;
else
l = mid +;
}
return l; } int main()
{
int T;
cin>>T;
int flag = ;
while(T--)
{ cin>>n;
for(int i = ; i < n; i++)
scanf("%lld",&a[i]);
sort(a,a+n);
int ans = ;
for(int i = ; i < n-; i++)
for(int j = i+; j < n; j++)
{
LL sum = a[i] + a[j];
LL cha = abs(a[j] - a[i]); int up = Binary_search(sum)-;
if(up <= j)
continue;
int low = Binary_search(cha);
if(low < j)
low = j;
ans += (up-low); } cout<<"Case "<<++flag<<": "<<ans<<endl; }
return ;
}
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h> using namespace std;
typedef long long LL;
LL a[+];
int n; int Binary_search(int x)
{
int l = ,r = n;
while(l<r)
{
int mid = (l+r)/;
if(a[mid] == x)
return mid;
else if(a[mid] > x)
r= mid;
else
l = mid +;
}
return l; } int main()
{
int T;
cin>>T;
int flag = ;
while(T--)
{ cin>>n;
for(int i = ; i < n; i++)
scanf("%lld",&a[i]);
sort(a,a+n);
int ans = ;
for(int i = ; i < n-; i++)
for(int j = i+; j < n; j++)
{
LL sum = a[i] + a[j];
LL cha = abs(a[j] - a[i]); int up = Binary_search(sum)-;
if(up <= j)
continue;
int low = Binary_search(cha);
if(low < j)
low = j;
ans += (up-low); } cout<<"Case "<<++flag<<": "<<ans<<endl; }
return ;
}
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h> using namespace std;
typedef long long LL;
LL a[+];
int n; int main()
{
int T;
cin>>T;
int flag = ;
while(T--)
{ cin>>n;
for(int i = ; i < n; i++)
scanf("%lld",&a[i]);
sort(a,a+n);
int ans = ;
for(int i = ; i < n-; i++)
for(int j = i+; j < n; j++)
{
LL sum = a[i] + a[j];
LL cha = abs(a[j] - a[i]); int up = upper_bound(a+j+,a+n,sum)-a; int low = lower_bound(a+j+,a+n,cha)-a; ans += (up-low); } cout<<"Case "<<++flag<<": "<<ans<<endl; }
return ;
}