UVa : 11554 (HAPLESS HEDONISM)


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
Advertisements

One thought on “UVa : 11554 (HAPLESS HEDONISM)

  1. Critical Input : 
    10
    5
    6
    7
    8
    9
    100
    1000
    10000
    100000
    1000000
    
    Output : 
    3
    7
    13
    22
    34
    79625
    82958750
    83295837500
    83329583375000
    83332958333750000
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s