Q21 Unibuc cu explicatii

#include <iostream>
#include <set>
using namespace std;
set<long long> S;
long long frecv[4], v[] = {3,4,5,8,10,12,14,32,57,64};
/** Codificare :
    0 - nu folosim,
    1 - face parte din latura a
    2 - face parte din latura b
    3 - face parte din latura c

    in frecv[i] vom retine suma tuturor numerelor
    ce adunate formeaza o latura din triunghi.
*/

/** Putem folosi baza 4 pentru a
    parcurge toate posibilitatile.
    0 0 0 0 0 0 0 0 0 0
    1 0 0 0 0 0 0 0 0 0
    2 0 0 0 0 0 0 0 0 0
    3 0 0 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0 0 0
    ...
    3 3 3 3 3 3 3 3 3 3

    Pentru fiecare element din v[]
    ii corespunde pozitia cifrei din
    reprezentarea in baza 4.
*/

/**

    Folosind 2 biti putem reprezenta o cifra din baza 4 :
    0 (4) -> 00 (2)
    1 (4) -> 01 (2)
    2 (4) -> 10 (2)
    3 (4) -> 11 (2)
*/


/**
    Pentru a obtine ultimii 2 biti putem folosi
    (n % 4) sau (n & 3) (sunt echivalente)

    Putem imparti la 2^n folosind (1 >> n)
    si implicit prin 4^n folosind (1 >> (2*n))

    Consideram ca cifrele din baza 4 sunt notate astfel :
    _ _ _ _ _ _ _ _ _ _
    0 1 2 3 4 5 6 7 8 9
    Asadar putem afla cifra x din reprezentarea in baza 4 a lui i astfel :
    (i >> (2 * x)) % 4 .
    Adica mai intai impartim i prin 4^x si apoi luam ultimii 2 biti.

    (La fel cum in baza 10 impartind prin 10^x taiem ultimele x cifre din baza 10,
    impartind prin 4^x taiem ultimele x cifre din baza 4).

*/
int main()
{
    for(int i = 0;i<(1<<20);i++)
    {
        /// i este numarul pe care il descompunem in baza 4.

        ///resetam valorile din frecv.
        for(int j = 0;j<4;j++)
            frecv[j] = 0;
        /// pe baza descompunerii in baza 4 adunam unde trebuie v[j].
        for(int j = 0;j<10;j++)
        {
            int nrelem = ((i >> (2*j)) % 4);
            frecv[nrelem] += v[j];
        }
        /**
        Conditia (1) :
        Intr-un triunghi se respecta mereu relatia
        a < b + c (unde a,b,c sunt lungimile laturilor.)


        Acum verificam daca aria este
        valida folosind formula lui Heron.
        Aria = sqrt(p*(p-a)*(p-b)*(p-c)) , unde p = (a+b+c)/2

        Scapam de radical, ridicand la puterea a doua.
        Aria^2 = p*(p-a)*(p-b)*(p-c).


        p poate avea virgula (.5) deci trebuie sa facem o modificare a formulei
        si sa transformam p in 2*p in fiecare factor.
        Aria^2 * ceva = 2 * p * 2 ( p - a ) * 2 * (p - b) * 2 * (p - c)
        Evident acest "ceva" va fi 2 * 2 * 2 * 2 = 16
        Aria^2 * 16 = 2p *(2p - 2a) * (2p - 2b) * (2p - 2c).

        ... Am scapat astfel de problema virgulei.

        Conditia (2) :
        Trebuie sa ne asiguram ca factorii ( 2p - 2a) , (2p - 2b), (2p - 2c) sunt toti pozitivi
        (In cod 2p va fi P = a + b + c.)
        */

        long long P = frecv[1] + frecv[2] + frecv[3];
        bool valid = true;
        /// Verificam pe rand cele doua conditii.
        // metoda 1  : if-uri
        /*
        if(frecv[1] >= frecv[2] + frecv[3]) valid = false;
        if(frecv[2] >= frecv[1] + frecv[3]) valid = false;
        if(frecv[3] >= frecv[1] + frecv[2]) valid = false;
        if(P - 2*frecv[1] <= 0) valid = false;
        if(P - 2*frecv[2] <= 0) valid = false;
        if(P - 2*frecv[3] <= 0) valid = false;
        */

        // metoda 2 : for - cu termeni generali
        /*
             n % 3 = {0,1,2}.
             n % 3 + 1 = {1,2,3}.
             si atunci in loc de (n) putem inlocui cu (n+1) si (n+2)
             pentru a obtine ceilalti doi termeni din multimea {1,2,3}.

             Spre exemplu, daca avem j = 2 :
             (2 % 3) + 1 = 3 (n)
             ((2+1) % 3) + 1 = 1 (n+1)
             ((2+2) % 3) + 1 = 2  (n+2)

        */
        for(int j = 0; j < 3 && valid; j++)
        {
            /// Conditia 1 :
            if(frecv[j % 3 + 1] >= frecv[(j+1) % 3 + 1] + frecv[(j+2) % 3 + 1])
               valid = false;
            /// Conditia 2 :
            if(P - 2 * frecv[j + 1] <= 0) /// (j + 1) - > {1, 2, 3}
               valid = false;
        }
        /// Daca avem o arie valida o calculam si o punem in set.
        if(valid)
        {
           /// Acum de fapt calculam (aria^2 * 16) .. dupa cele explicate mai sus.
           long long aria = P * (P - 2*frecv[1]) * (P - 2*frecv[2]) * (P - 2*frecv[3]);
           S.insert(aria);

        }

    }
    cout << S.size() << '\n';
    return 0;
}