Solution UVA: 11401 - Triangle Counting

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss11401 - Triangle Counting	Accepted	C++11	0.000	0.000	798	28 secs ago

Suggest:

- Let's denote F[n] as the number of triangles formed from n sides. I've observed that the number of triangles formed from n sides will include F[n-1] + add(n).

- Here, add(n) represents the number of triangles that contain side n.

* For example, with n=6, we will have the following triangles:

- Triangles with n=5 (not containing side 6):

    

    According to the test, we have 3 triangles.

- Triangles containing side 6:

    2 5 6    

        => 1

    3 4 6

    3 5 6

        => 2

    4 5 6

        => 1

Therefore, the result of F[6] = 3 + (1+2+1) = 7.

* Note that add(n) will differ between even and odd n values. I will provide further examples to help you visualize the cases:

F[3] = 0

F[4] = 1

F[5] = 1 + (1+1) = 3

F[6] = 3 + (1+2+1) = 7

F[7] = 7 + (1+2+2+1) = 13

F[8] = 13 + (1+2+3+2+1) = 22

F[9] = 22 + (1+2+3+3+2+1) = 34

=> We can readily observe a pattern quite similar to Pascal's Triangle.

 

#include<bits/stdc++.h>

#define int long long

using namespace std;

int F[1000111];

int add(int n){

        int r= n/2-1, l=1;

        int p= r-l+1;

        int s= (l+r)*(1.0*p/2);

        if (n%2) return s*2;

        return s*2-r;

}

int32_t main(){

        F[3]=0, F[4]=1;

        for(int i=5; i<=1000000; i++)

                F[i] = F[i-1] + add(i);

        ios::sync_with_stdio(0); cin.tie(0);

        int n;

        while(cin >> n && n>=3){

                cout<<F[n]<<"\n";

        }

       

}