Making Triangle

Solution by TheRealFertos — 100 pts

Code / Notes

#include <bits/stdc++.h>
using namespace std;

int main() {
    int qtdlados;
    cin >> qtdlados;
    vector <int> lados;
    for(int i=0;i<qtdlados;i++) {
        int lado;
        cin >> lado;
        lados.push_back(lado);
    }
    int qtdtrian=0;
    sort (lados.begin(),lados.end());

// So isso resolve
/*
    for (int i = 0; i < qtdlados; i++) {
        for (int j = i+1; j < qtdlados; j++) {
            for (int k = j+1; k < qtdlados; k++) {
                if (lados[i] == lados[j] or lados[j] == lados[k]) continue;
                if (lados[k] < lados[i]+lados[j]) qtdtrian++;
            }
        }
    }
*/

    for(int i=0; i<qtdlados;i++) { // faltando i++
        for (int p=i+1;p<qtdlados-1;p++) {
            if (lados[i]==lados[p]) {
                continue;
            }
            int n=lados[i]+lados[p];
            int r=p+1;
            while (n>lados[r]) {                
                if (lados[r]==lados[p]) {
                    if (r<qtdlados-1) {
                        r++;
                    } else {
                        break;//sim
                    }
                    continue;
                }
                qtdtrian++;
                if (r<qtdlados-1) {
                    r++;
                }
                else {
                    break;
                }    // o r pode estar passando do qtdlados
                // faltou so checar se os tres lados sao diferentes
            } 
        }
    }
    cout << qtdtrian;
}
// 10^8
// for (1000) for(1000) for (50) -> 5e7

Last updated 3 weeks, 3 days ago

« Back to problem