We know, summation of any two sides of a triangle is greater than third side. Here, we have 1 to n sticks. How many different triangles we can make?

Suppose, n = 10

that is, we have 10 sticks, numbered from 1 to 10

here, stick1 = stick of length 1

stick2 = stick of length 2 and so on

If we take stick1 and stick2, then the third stick must have length greater than or equals to 4

So, 1 + 2 = 3 [3rd stick can be, 4 to 10; i.e. a total of 7 different triangles]

1 + 3 = 4 [3rd stick can be, 5 to 10; i.e. a total of 6 different triangles]

1 + 4 = 5 [3rd stick can be, 6 to 10; i.e. a total of 5 different triangles]

1 + 5 = 6 [3rd stick can be, 7 to 10; i.e. a total of 4 different triangles]

1 + 6 = 7 [3rd stick can be, 8 to 10; i.e. a total of 3 different triangles]

1 + 7 = 8 [3rd stick can be, 9 to 10; i.e. a total of 2 different triangles]

1 + 8 = 9 [3rd stick can be, 10 to 10; i.e. a total of 1 different triangles]

1 + 9 = 10 [we don’t have any stick greater than 10]

I think it should be clear that, if our first stick is length 1 and we have 10 sticks, then we can make (1 + 2 + 3 + 4 + 5 + 6 + 7) triangles

be careful about data overflow!

//============================================================================
// Name : Cprog.cpp
// Author : Shahab
// Link : http://uva.onlinejudge.org/external/115/11554.html
// Runtime : 1.648s
// Description : Hello World in C++, Ansi-style
//============================================================================
// @BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;
int main ()
{
int testCase;
scanf ("%d", &testCase);
while ( testCase-- ) {
int n;
scanf ("%d", &n);
LL ans = 0;
for ( int i = 1; i <= n; i++ ) {
double p = n - (i + i + 1);
if ( p > 0 )
ans += (LL) (p * (p + 1)) / 2;
}
cout << ans << endl;
}
return 0;
}
// @END_OF_SOURCE_CODE

### Like this:

Like Loading...

*Related*

## Published by Shahab

Completed B.Sc in CSE, @United International University, Dhaka.
Currently working as Development Engineer, Android and iOS Application.
View all posts by Shahab

## One thought on “UVa : 11554 (HAPLESS HEDONISM)”