Problem Statement:
You have N wooden sticks, which are labeled from 1 to N. The i-th stick has a length of Li . Your friend has challenged you to a simple game: you will
pick three sticks at random, and if your friend can form a triangle
with them (degenerate triangles included), he wins; otherwise, you win.
You are not sure if your friend is trying to trick you, so you would
like to determine your chances of winning by computing the number of
ways you could choose three sticks (regardless of order) such that it is
impossible to form a triangle with them.
Input:
The input file consists of multiple test cases. Each test case starts with the single integer N, followed by a line with the integers L1, ..., LN. The input is terminated with N = 0, which should not be processed.Output:
For each test case, output a single line containing the number of triples.Example:
Input: 3 4 2 10 3 1 2 3 4 5 2 9 6 0 Output: 1 0 2For the first test case, 4 + 2 < 10, so you will win with the one available triple. For the second case, 1 + 2 is equal to 3; since degenerate triangles are allowed, the answer is 0.
Solution:
#include<iostream>
using namespace std;
void noways(unsigned int *a,unsigned int l);
int main()
{
unsigned int p[10][10],len[10],k=0,i;
cout<<"Enter the inputs:\n";
while(1)
{
cin>>len[k];
if(len[k]==0)
break;
for(i=0;i<len[k];i++)
cin>>p[k][i];
k++;
}
for(i=0;i<k;i++)
noways(*(p+i),len[i]);
return(0);
}
void noways(unsigned int * a,unsigned int l)
{
unsigned int i,j,k,n=0;
for(i=0;i<l;i++)
for(j=0;(j<l)&&(j!=i);j++)
for(k=0;(k<l)&&(k!=j)&&(k!=i);k++)
{
if(*(a+i) + *(a+j) < *(a+k))
n++;
if(*(a+k) + *(a+j) < *(a+i))
n++;
if(*(a+i) + *(a+k) < *(a+j))
n++;
}
cout<<"All possible ways:"<<n<<endl;
}
No comments:
Post a Comment