BitCell

by **Teal** » 09 Nov 2011, 15:08

Line number On/Off | Expand/Contract | Select all

#include <stdio.h>
#include <stdlib.h>
int *iSegments = NULL, iSolution[3];
long int liCount, liIndex;
int isTriangle(int a, int b, int c)
{
        if(a + b > c && a + c > b && b + c > a) return 1;
        return 0;
}
int main()
{
        freopen("bitcell.in", "r", stdin);
        freopen("bitcell.out", "w", stdout);
        int iValue, iSuma = 0;
        long int a, b, c;
        while(scanf("%d", &iValue) != EOF)
        {
                liCount++;
                iSegments = (int *) realloc(iSegments, liCount * sizeof(int));
                iSegments[liCount - 1] = iValue;
        }
        for(a = 0; a < liCount - 2; a++)
                for(b = a + 1; b < liCount - 1; b++)
                        for(c = b + 1; c < liCount; c++)
                                iSuma += isTriangle(iSegments[a], iSegments[b], iSegments[c]);
        printf("%d", iSuma);
        return 0;
}

Poftim cod C.

by **new_luca** » 09 Nov 2011, 15:33

Dap, pe asta il inteleg

, este exact cum am facut si eu prima solutie, metoda "Brute Force", doar ca e alocat dinamic vectorul, ce e nasol la solutia asta e ca pe masura ce cresc numerele din fisierul de intrare sta "zeci de ani" sa calculeze, banuiesc ca nu e chiar implementarea din C++ de mai devreme pentru ca nu e nici un Backtracking, nu ca l-as intelege prea bine dar nu vad nimic de genul.

Ia uite-te la solutia scrisa de Payne si cea in C scrisa de mine, calculeaza relativ instant rezultatul si pentru un milion de numere.
Banuiesc ca si metodei backtracking ii ia mai mult timp sa calculeze, nu ?

by **cata45** » 09 Nov 2011, 15:47

@new_luca Daca foloseste back la problema asta nu e vorba de "rezultat afisat instant" sau in cateva secunde ci de minute intregi (As putea spune ca poate dura si o jumatate de ora pe un test - in functie de cat de optimizat e back-ul si de testul bagat) Poate la urmatorul concurs imi bag si eu nasul daca am timp... Cine propune urmatorul concurs? (si cand?)

by **Mihai** » 10 Nov 2011, 00:33

Teal wrote:De ce va complicati unii din voi?

Trebuia sa generati toate combinatiile posibile de N luate cate 3 si sa testati folosind teorema ca suma a oricare doua laturi ale unui triunghi sunt mai mare decat a treia.

Bagă în fișierul de intrare 1000000 de numere egale intre ele și spune-mi și mie în cât timp ți se va termina execuția. Motivul pentru care lumea "se complică" este faptul că soluția banală este total ineficientă; mai mult decât atât, soluția ta este chiar mai proastă decât soluția banală - pentru că folosești recursivitatea, soluția ta se va mișca mai greu decât una iterativă cum este cea implementată de Luca.

Ca și sfat pentru viitor, aveți grijă cum alegeți tipurile de date! În cazul de față, numărul de combinări putea fi unul foarte mare!

by **Teal** » 12 Nov 2011, 17:14

Line number On/Off | Expand/Contract | Select all

#include <fstream>
typedef unsigned long u;
typedef int i;
u s[101] = { 0 }, n = 0, r;
i a, b, c, j;
u e(u a) { return s[a]; }
i t(i a, i b, i c) { return (a + b > c && a + c > b && b + c > a) ? 1 : 0; }
u f(i n, i s) { r = 1; for(j = s; j <= n; j++) r *= j; return r; }
u cc(i n, i p) { r = f(n, n - p + 1) / f(p, 2); return r; }
u d() {
    for(a = 1; a <= 100; a++) {
        if(e(a)) {
             for(b = a + 1; b <= 100; b++)
                if(e(b)) for(c = b + 1; c <= 100 && c < a + b; c++)
                    if(e(c)) n += t(a, b, c) * e(a) * e(b) * e(c);
            if(e(a) > 1) {
                for(b = 1; b < 2 * a && b <= 100; b++)
                    if(e(b) && a != b) n += t(a, a, b) * cc(e(a), 2) * e(b);
                if(e(a) > 2) n+= cc(e(a), 3);
            }
        }
    }
    std::ofstream f("bitcell18.out");
    f<<n;
    f.close();
}
i main() {
    std::ifstream f("bitcell18.in");
    while(f>>j) s[j]++;
    f.close();
    d();
}

by **Mihai** » 13 Nov 2011, 00:00

$S^{i^{\ ^ {e ^u \ } p} o} t s^{a^{\ ^ {s ^c r} i} u} \ t^{o^{a ^ {t ^e \ } m} e} s a^{j^{e ^ {l ^e \ } a} s} a.$ N-am s-o fac totuși pentru că mi se pare o lipsă de respect față de oricine se chinuie să citească ceea ce am vrut să spun și deci postul o să zboare; același lucru care se va întâmpla și cu postul tău dacă nu modifici codul cu unul mai puțin obfuscat (: .

by **Teal** » 13 Nov 2011, 02:20

Where is the love?

Line number On/Off | Expand/Contract | Select all

#include <fstream>
unsigned long s[101] = { 0 }, n = 0, r;
int a, b, c, j;
// zice de cate ori E segmentul respectiv in lista
unsigned long e(unsigned long a) { return s[a]; }
// zice daca e un Triunghi
int t(int a, int b, int c) { return (a + b > c && a + c > b && b + c > a) ? 1 : 0; }
// calculeaza un fel de Factorial pornind de la s si nu de la 2
unsigned long f(int n, int s) { r = 1; for(j = s; j <= n; j++) r *= j; return r; }
// Calculeaza numarul de Combinatii
unsigned long cc(int n, int p) { r = f(n, n - p + 1) / f(p, 2); return r; }
// calculeaza numarul de triunghiuri (Do)
unsigned long d() {
    for(a = 1; a <= 100; a++) {
        if(e(a)) {
             for(b = a + 1; b <= 100; b++)
                if(e(b)) for(c = b + 1; c <= 100 && c < a + b; c++)
                    if(e(c)) n += t(a, b, c) * e(a) * e(b) * e(c);
            if(e(a) > 1) {
                for(b = 1; b < 2 * a && b <= 100; b++)
                    if(e(b) && a != b) n += t(a, a, b) * cc(e(a), 2) * e(b);
                if(e(a) > 2) n+= cc(e(a), 3);
            }
        }
    }
    std::ofstream f("bitcell18.out");
    f<<n;
    f.close();
}
int main() {
    std::ifstream f("bitcell18.in");
    while(f>>j) s[j]++;
    f.close();
    d();
}

Literele scrise capitalizat din comentarii arata de ce functiile au fost denumite asa.

BitCell

[18] Concurs - Triunghiuri

Re: [18] Concurs - Triunghiuri

Re: [18] Concurs - Triunghiuri

Re: [18] Concurs - Triunghiuri

Re: [18] Concurs - Triunghiuri

Re: [18] Concurs - Triunghiuri

Re: [18] Concurs - Triunghiuri

Re: [18] Concurs - Triunghiuri

Who is online