BitCell

by **Mihai** » 26 Oct 2011, 23:56

Triunghiuri

Se citesc din fișierul bitcell18.in N numere naturale (1<=N<=1000000) cuprinse între 1 și 100 reprezentând lungimile a N segmente. Câte triunghiuri pot fi formate folosind doar segmente cu lungimile date? Răspunsul se va afișa în bitcell18.out.

Exemplu

bitcell18.in

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

2 4 3 3 28

bitcell18.out:

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

4

Explicație: pot fi formate următoarele 4 triunghiuri: (2,4,3), (2,4,3), (2,3,3), (4,3,3).

Perioada de desfășurare:

27 Octombrie - 5 Noiembrie - înscrierea în concurs
6 Noiembrie - desemnarea câștigătorului

by **cata45** » 27 Oct 2011, 15:00

Daca (spre exemplu) latura a=3 , latura b=2 si latura c=5 se considera ca formeaza un triunghi de arie 0?

L.E. (-- 27 Oct 2011, 15:00 --)

Nu se precizeaza in fisierul de intrare cate segmente se dau?
Si daca lungimile segmentelor sunt mai mici de 100 la exemplu de ce este si 128?

by **nomemory** » 27 Oct 2011, 18:07

O solutie: aici . Programul e compilat pe Linux 32 (nu am avut Windows la indemana) .

Am adaugat eu manual dimensiunea listei de numere, astfel fisierul bitcell18.in ar trebui sa arate asa:

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

 
5
1 2 4 3 3

Codul nu am avut pe ce sa-l testez, daca nu functioneaza corect, se pot adauga cateva teste noi (mai ales pentru numere mari) .

Sursa am trimis-o ca mesaj privat lui Mihai .

by **Mihai** » 27 Oct 2011, 20:03

Precizări:

în fişier nu se va găsi N ci doar o listă a celor N numere; altfel spus, N se determină ca fiind numărul de numere din fişier
pentru exemplul dat, numărul 128 nu avea într-adevăr ce să caute acolo - trebuia să fie 28; am modificat în enunţ testul
nu există triunghiuri cu unghiuri nule

by **Payne** » 29 Oct 2011, 12:18

Salut, am facut si eu o aplicatie, dar as dori o ultima verificare inainte sa o postez.
Am urmatorul fisier de intrare:

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

2 3 2 2 3 2 3 99 99 100 99 100 99

Daca esti amabil Mihai, mi-ai putea da rezultatul correct?

by **new_luca** » 29 Oct 2011, 15:01

Payne, e cumva rezultatul 160 ?

Am facut si eu ceva si imi da 160, doar ca nu stiu cum s-ar comporta programul 1 milion de mumere :))

, probabil as mai imbatrani cu un an pana sa aflu rezultatul.

Cine imi spune si mie cum sa incep cu algoritmii , ca sunt || ..m-am chinuit sa invat Backtracking dar tot nu am inteles, Programarea dinamica....nu prea le inteleg, nu pot sa implementez deloc ...tot ce fac e Brute Force

doar cum ma duce pe mine capul cum s-ar spune, imi fac proprii algoritmi care suck mereu ca eficienta.

by **Payne** » 30 Oct 2011, 12:06

Eu am reusit sa rezolv problema cu numarul foarte mare de laturi, dar imi dificulteaza calcularea numarului de triunghiuri posibile.

L.E. (-- 29 Oct 2011, 15:59 --)

Dupa multe batai de cap am reusit

.

Varianta mea aici.

L.E. (-- 30 Oct 2011, 11:06 --)

Am gasit un mic bug in programul anterior. Pun aici versiunea a 2a.

by **morpheus** » 30 Oct 2011, 17:30

new_luca wrote:m-am chinuit sa invat Backtracking dar tot nu am inteles, Programarea dinamica....nu prea le inteleg, nu pot sa implementez deloc

Deschide topic-uri separate si intreaba acolo, ca de aia avem forum.

by **new_luca** » 31 Oct 2011, 23:02

Varianta mea care pe masura datele de intrare cresc ca numar, timpul de executie creste exponential iar pentru un milion de numere....

Download

by **Mihai** » 05 Nov 2011, 18:10

Payne: Îmi cer scuze dacă este (mult) prea târziu dar am fost foarte ocupat. Pe testul de mai sus, răspunsul era într-adevăr 160 (așa cum a observat și Luca).

by **Payne** » 05 Nov 2011, 23:25

No problem, am facut un brute force pentru rezultatul acela.

by **Mihai** » 07 Nov 2011, 17:33

Payne, trimite-mi te rog ultima sursă a ta pentru a putea desemna câştigătorul.

by **Payne** » 07 Nov 2011, 17:41

Ti-am trimis-o dupa a pune versiunea a 2a. Deci e ultima sursa.

by **new_luca** » 07 Nov 2011, 19:12

Vreau sa imi explice si mie cineva cum se rezolva problema eficient.

Nu citi acest offtopic daca nu cumva vrei sa pierzi timpul si/sau sa ai "nervi" ...sau orice alte simptome neplacute.
Offtopic

by **cata45** » 07 Nov 2011, 20:16

In primul rand trebuie sa stochezi in memorie cele N segmente. (1<=N<=1000000). Aici este cheia problemei. In enunt se specifica faptul ca lungimea unui segment nu este mai mare de 100. Deci in loc sa ai un vector cu N componente ai unul cu 100 de componente si in a[i] numeri de cate ori apare segmentul de lungime i. Parcurgand acest vector determini cate triunghiuri poti forma. (Trei segmente de lungime a,b, respectiv c sunt laturile unui triunghi daca: a+b>c; b+c>a; a+c>b); Trebuie sa gasesti o formula de determinare a numarului de triunghiuri stiind ca ai x laturi de lungime a, y laturi de lungime b si z laturi de lungime c.

Banuiesc ca nelamurirea ta (si timpul de executie al programului tau) provine de la faptul ca aveai un vector de 1000000 pe care faceai operatiile.
Sper ca ai inteles. Din cate stiu trebuie postate sursele participante. Te poti uita si pe ele. %%-

by **Mihai** » 08 Nov 2011, 21:16

Am primit 3 surse:

nomemory:

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

#include <algorithm>
#include <cstdio>
#include <vector>
 
#define MAX_NUM_ELEM 1000000
#define FILE_IN "bitcell18.in"
#define FILE_OUT "bitcell18.out"
 
#define INVALID_READ 1
#define INVALID_WRITE 2
#define SUCCESS 0
 
using namespace std;
 
// Read input file, stores results in numbers vector
bool read_input(const char * file_in_name, vector<short> &numbers)
{
    int size = 0;
    short int tmp = 0;
    FILE *file_in = fopen(file_in_name, "r");
   
    if (NULL == file_in) {
        return (false);
    }
   
    fscanf(file_in, "%d", &size);
    numbers.reserve(size);
   
    for(int i = 0; i < size ; ++i) {
        fscanf(file_in, "%hd", &tmp);
        numbers.push_back(tmp);
    }
   
    fclose(file_in);
   
    return true;
}
 
// Takes number vector write solution
bool write_output(const char * file_out_name, vector<short> numbers)
{
    short sum = 0, diff = 0;
    FILE *file_out = fopen(file_out_name, "w");
    vector<short>::iterator up;
    int triangles = 0;
   
    if(NULL == file_out) {
        return (false);
    }
   
    if (numbers.size() < 3) {
        fprintf(file_out, "%hd", triangles);
        fclose(file_out);
        return (true);
    }
   
    sort(numbers.begin(), numbers.end());
   
    for(vector<short>::iterator i = numbers.begin(); i != numbers.end(); ++i) {
        for(vector<short>::iterator j = i + 1; j != numbers.end(); ++j) {
            sum = (*i) + (*j);
            diff = (*j) - (*i);
            up = lower_bound(i, numbers.end(), sum);
            #ifdef DEBUG
            // Define DEBUG to additionaly print possible triangles
            for(vector<short>::iterator k = j + 1; k != up; k++) {
                printf("%hd %hd %hd\n", *i, *j, *k);
            }
            #endif
            triangles += int(up - j - 1);
        }
    }
   
    fprintf(file_out, "%hd", triangles);
    fclose(file_out);
   
    return (true);
}
 
int main(int argc, char * argv[])
{
    vector<short> numbers;
   
    if (!read_input(FILE_IN, numbers)) {
        fprintf(stderr, "Cannot read file: %s .\n", FILE_IN);
        return (INVALID_READ);
    }
   
    if (!write_output(FILE_OUT, numbers)) {
        fprintf(stderr, "Cannot write solution to file: %s .\n", FILE_OUT);
        return (INVALID_WRITE);
    }
   
    return (SUCCESS);
}

payne:

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

 
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
using namespace std;
long long count = 0LL;
bool ValidTriangle(const char &a,const char &b,const char &c){
    if((a+b) > c && (a+c) > b && (b+c) > a)
        return true;
    return false;
}
bool isNumeric(const string &s){
    bool isnumeric = true;
    for(unsigned int x=0;x<s.length();x++){
        if(s[x] < 48 || s[x] > 57)
        {
            isnumeric = false;
            break;
        }
    }
    return isnumeric;
}
void CalcTriangleOne(const char &a,const long long &ac){
    if(ac > 2LL)
    {
        count += ((ac-1LL)*(ac-2LL)*ac)/6LL;
    }
}
void CalcTriangleTwo(const char &a,const long long &ac, const char &b, const long long &bc){
    if(ac+bc > 2LL && ac > 0LL && bc > 0LL){
        if(ValidTriangle(a,a,b))
        {
            count += (ac*(ac-1LL))/2LL*bc;
        }
        if(ValidTriangle(b,b,a))
        {
            count += (bc*(bc-1LL))/2LL*ac;
        }
    }
}
void CalcTriangleThree(const char &a, const long long &ac, const char &b, const long long &bc,const char &c,const long long &cc){
    if(ac > 0LL && bc > 0LL && cc > 0LL && (ac+bc+cc) > 2LL){
        if(ValidTriangle(a,b,c)){
            count += ac*bc*cc;
        }
    }
}
int main()
{
    fstream in("bitcell18.in",fstream::in);
    fstream out("bitcell18.out",fstream::out);
    int numbers[101];
    fill(numbers,numbers+101,0);
    if(in.is_open()){
        if(out.is_open() && out.good())
        {
            string number;
            int i = 0;
            while(in.good()){
                in >> number;
                if(isNumeric(number)){
                    int val = atoi(number.c_str());
                    if(val > 0 && val <= 100){
                        numbers[val]++;
                        i++;
                        if (i >= 1000000)
                            break;
                    }
                }
            }
            if(i >= 3){
                for(unsigned int x = 0;x<101-2;x++)
                {
                    for(unsigned int y = x+1;y<101-1;y++)
                    {
                        for(unsigned int z = y+1;z<101;z++)
                        {
                            CalcTriangleThree(x,numbers[x],y,numbers[y],z,numbers[z]);
                        }
                    }
                }
                for(unsigned int x =0;x<101-1;x++)
                {
                    for(unsigned int y=x+1;y<101;y++)
                    {
                        CalcTriangleTwo(x,numbers[x],y,numbers[y]);
                    }
                }
                for(unsigned int x=0;x<101;x++)
                {
                    CalcTriangleOne(x,numbers[x]);
                }
            }
            out << count;
            out.close();
        }
        else
            cout << "Nu se poate crea sau deschide fisierul bitcell18.out";
        in.close();
    }
    else
        cout << "Nu exista sau nu se poate citi fisierul bitcell18.in";
    return 0;
}

new_luca:

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

#include <stdio.h>
 
int triunghi(int a,int b,int c)
{
    if(a+b > c && a+c > b && b+c > a)
    {
        return 1;
    }
    return 0;
}
 
int main(void)
{
    unsigned short v[1000000] = {0}, a, b, c;
    int n, suma = 0;
   
    freopen("bitcell18.in", "r", stdin);
    freopen("bitcell18.out", "w", stdout);
                                                    //          2 4 3 3 28
    for(n = 0; scanf("%d", &v[n]) != EOF; n++);     //4 triunghiuri: (2,4,3), (2,4,3), (2,3,3), (4,3,3).
   
    for(a = 0;a < n-2;a++)
    {
        for(b = a+1;b < n-1;b++)
        {
            for(c = b+1;c < n;c++)
            {
                suma += triunghi(v[a],v[b],v[c]);
            }
        }
    }
   
    printf("%d", suma);
   
    return 0;
}

Sfat pentru viitor: când puteţi implementa brut (şi aveţi timp destul la dispoziţie), este o idee foarte bună să o faceţi. Astfel, puteţi verifica mai apoi dacă soluţia mai eficientă este corectă (folosiţi brutul şi un generator de teste scris tot de voi, desigur) şi în caz că apar probleme vă puteţi da seama mai repede unde anume.

Acestea fiind spuse, câştigătorul concursului este new_luca: deşi algoritmul este ineficient, fiind implementarea brută, se descurcă bine pe mai multe teste decât celelalte soluţii.
Luca, te aşteptăm cu propunerea pentru noul concurs!

by **new_luca** » 08 Nov 2011, 22:25

Final de concurs total neasteptat, cel putin pentru mine.

Mihai te rog frumos, cu toate ca stiu ca esti foarte ocupat si nu prea ai timp sa propui tot tu o problema, sau altcineva daca aveti vreo problema interesanta nu ezitati, apreciez timpul pe care il dedicati.

Sunt curios ce au celelalte coduri de de dau erori pe anumite teste, asta banuiesc ca s-a intamplat.

M-am uitat peste ele si nu prea pot sa le citesc in totalitate si sa le si inteleg, oricum am incercat inca de dinaintea finalizarii concursului sa folosesc un vector cu 100 de pozitii si sa tin minte pe fiecare pozitie numarul aparitiilor segmentului de acea lungime cum mi-a sugerat cata45, problema pe care o gasesc este formula de determinare a triunghiurilor posibile apoi.

Eu m-am gandit sa generez toate combinatiie de cele 100 posibile lungimi de segmente, luate cate 3 si apoi sa inmultesc numarul aparitiilor acelor 3 segmente intre ele daca ele exista si pot forma un triunghi ca mai apoi sa adun triunghiurile. Cred ca imi lipseste ceva, si nu imi dau seama ce cu toate ca poate raspunsul este in fata mea, in codurile lui Payne sau nomemory.

Este logica mea gresita oare, pentru ca rezultatele codului sunt eronate, nu cu mult, dar e o eroare constanta care tot apare, am incercat multe teste ^:)^

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

 
 #include <stdio.h>
 
int triunghi(int a,int b,int c)
{
    if(a+b > c && a+c > b && b+c > a)               
    {                                              
        return 1;
    }
    return 0;
}
 
int main(void)
{
    unsigned short v[101] = {0}, a, b, c, i;        
    int n, x, suma = 0;                        
 
    freopen("bitcell18.in", "r", stdin);
    freopen("bitcell18.out", "w", stdout);
    
    for(n = 0; scanf("%d", &x) != EOF; n++)v[x]++;  //scanez cele n numere din fisierul de intrare si le stochez in V
    
    for(a = 1;a < 99;a++)
    {
        for(b = a+1;b < 100;b++)
        {
            for(c = b+1;c < 101;c++)
            {
                suma += v[a]*v[b]*v[c]*triunghi(a,b,c);     //Ce anume uit, sau e gresit?
            }                                              
        }
    }
    printf("%d", suma);
    return 0;
}
 
 

by **Payne** » 08 Nov 2011, 22:43

Acea inmultire calculeaza triunghiurile posibile cu toate 3 numerele, dar lipseste de exemplu posibilitatile folosind doar doua dintre ele si folosind doar una. Vezi functiile CalcTriangleTwo si CalcTriangleOne.

by **Teal** » 09 Nov 2011, 13:12

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.

Am zis sa va fac si eu un cod ca sa intelegeti.

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

#include <fstream>
#include <vector>
using namespace std;
int iNumberOfTriangles = 0, iSolution[3], iNumberOfSegments, iSegment;
vector<int> vSegments;
bool isTriangle(int a, int b, int c) {
        if(a + b > c && a + c > b && b + c > a) return true;
        return false;
}
void generateTriangles(int iPos = 0) {
        if(iPos == 3)
                iNumberOfTriangles += isTriangle(vSegments[iSolution[0]], vSegments[iSolution[1]], vSegments[iSolution[2]]) ? 1 : 0;
        else
                for(int index = (iPos == 0) ? 0 : iSolution[iPos - 1] + 1; index < iNumberOfSegments; index++) {
                        iSolution[iPos] = index;
                        generateTriangles(iPos + 1);
                }
}
int main() {
        fstream file("bitcell.in", ios::in);
        while(file>>iSegment) vSegments.push_back(iSegment);
        iNumberOfSegments = vSegments.size();
        file.close();
        generateTriangles();
        file.open("bitcell.out", ios::out);
        file<<iNumberOfTriangles;
        file.close();
        return 0;
}

Citesti toate valorile segmentelor intr-un vector.
Generezi toate posibilitatile prin backtracking.
Testezi fiecare solutie generate sa vezi daca poate crea un triunghi.
Numeri solutiile corecte.
Si gata.

by **new_luca** » 09 Nov 2011, 14:09

Multumesc Payne, acum am inteles ce uitam, si am inteles si formulele, combinatorica asta...

Ultimul tau executabil pentru fisierul cu 1 milion de numere da alt rezultat fata de ce da codul meu de mai jos, dar pentru teste mai mici da acelasi rezultat, asa ca nu stiu exact la care dintre noi este buba in cod, cel brut sta sigur milenii deci nu pot verifica

.

@Teal, eu nu stiu Backtracking si nici C++, dar codul tau l-am compilat si nu prea scrie nimic in fisierul de iesire si nici nu stiu cum sa il modific sa scrie, dar sunt curios cum functioneaza solutia ta.

Codul si executabilul scris de mine dupa ce cata45 si Payne mi-au aratat calea cea buna, sper sa nu fie gresita :
Download

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

#include <stdio.h>
 
short triunghi(short a,short b,short c)
{
    if(a+b > c && a+c > b && b+c > a)                
    {                                               
        return 1;
    }
    return 0;
}
 
int main(void)
{
    unsigned short v[101] = {0}, a, b, c, x;
    unsigned int n;                         
    unsigned long long suma = 0;
                                                    
    freopen("bitcell18.in", "r", stdin);
    freopen("bitcell18.out", "w", stdout);
    
    for(n = 0; scanf("%d", &x) != EOF; n++)v[x]++; 
    
/*3*/for(a = 1;a < 99;a++)                                           
    {
        for(b = a+1;b < 100;b++)
        {
            for(c = b+1;c < 101;c++)
            {
                if(triunghi(a,b,c))suma += v[a]*v[b]*v[c];
            }                                              
        }
    }
/*2*/for(a = 1;a < 100;a++)                                        
    {   
        for(b = a+1;b < 101;b++)
        {
            if(v[a]+v[b] > 2)
            {
                if(triunghi(a,a,b))suma += ((v[a]-1)*v[a])/2*v[b];   
                if(triunghi(b,b,a))suma += ((v[b]-1)*v[b])/2*v[a];
            }
        }
    }
/*1*/for(a = 1;a < 101;a++)                                       
    {
        if(v[a] > 2)suma += ((v[a]-1)*(v[a]-2)*v[a])/6;
    }
    
    printf("%llu", suma);
    return 0;
}
 

BitCell

[18] Concurs - Triunghiuri

[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

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

Re: [18] Concurs - Triunghiuri

Re: [18] Concurs - Triunghiuri

Re: [18] Concurs - Triunghiuri

Re: [18] Concurs - Triunghiuri

Re: [18] Concurs - Triunghiuri

Who is online