BitCell

by **cata45** » 11 Nov 2011, 20:57

Cu acceptul lui new_luca am propus urmatoarea tema pentru concurs. Spor!

Domnul Z, profesorul de limba română de la clasa a IX-a a stabilit cu cei N elevi ai săi temele individuale de documentare şi cercetare, care au fost numerotate cu numere de la 1 la N. După realizarea temelor, acestea vor fi grupate în una sau mai multe reviste care vor participa la concursul revistelor şcolare. Regulamentul concursului prevede ca revista să fie compusă din teme care au elemente comune sau care se „potrivesc”; dacă tema A are elemente comune cu tema B, iar tema B are elemente comune cu tema C, atunci tema A se „potriveşte” cu tema C, astfel cele trei teme pot face parte din aceeaşi revistă.
Cerinţă
Cunoscând n numărul de elevi (implicit numărul de teme), M numărul de perechi de teme care au elemente comune şi temele care au elemente comune să se determine numărul minim de reviste care vor participa la concurs.
Date de intrare
Fişierul de intrare bitcell19.in conţine pe prima linie numerele naturale N şi M separate prin câte un spaţiu. Pe următoarele M linii se află câte două numere naturale A B cu semnificaţia „tema A are elemente comune cu tema B”.
Date de iesire
Fişierul de ieşire bitcell19.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul minim de reviste care se vor realiza.
Restrictii si precizari
• 1 ≤ N ≤ 300
• 1 ≤ A, B ≤ N
• 0 ≤ M ≤ 32000
• Perechile A B din fişierul de intrare sunt distincte.
Exemple
bitcell19.in

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

bitcell19.out

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

2

Explicatii
Temele 1 şi 2 au elemente comune, la fel şi temele 2, 3 atunci 1 şi 3 se potrivesc , astfel temele 1, 2, 3 vor face parte din aceeaşi revistă.
temele 4 şi 5 au elemente comune, la fel şi temele 4, 6 atunci 5 şi 6 se potrivesc , astfel temele 4, 5, 6 vor face parte din aceeaşi revistă.
Numărul minim de reviste va fi 2.

Data inceput : 10/11/2011
Data finalizare: 20/11/2011
Desemnare castigator: 21/11/2011

by **cata45** » 14 Nov 2011, 21:16

Solutia mea - in atasament.

Avand in vedere ca particip si eu la concurs, sper ca are altcineva timp sa jurizeze.

by **new_luca** » 16 Nov 2011, 10:38

Particip si eu, sper sa fie functionala solutia : Download

Presupun ca fiecare elev/tema apare cel putin 1 data printre cele M perechi (adica are un element comun cu o alta tema).

by **cata45** » 16 Nov 2011, 14:14

NU e obligatoriu ca fiecare tema sa aiba elemente comune cu alta. Alt exemplu:

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

2
2
3

Tema 1 are elemte comune cu 2. Tema 2 are elemte comune cu 3. Deci temele 1 2 3 fac parte din primul grup.
Temele 4 5 6 sunt fiecare in grupul lor pentru ca nu au legaturi cu alte teme. In total vor fi 4 grupuri

primul grup : 1 2 3
al II-lea grup: 4
al III-lea grup: 5
al IV-lea grup: 6

by **new_luca** » 16 Nov 2011, 18:06

Mi-am revizuit rezolvarea : Download .

Nu imi dau seama daca am greseli, daca cineva gaseste vreo intrare pe care nu merge bine programul va rog sa ma anuntati.

Catalin pana la urma pe tine ramane povara jurizarii? Ca sa stiu cui ii trimit codul sursa.

by **cata45** » 16 Nov 2011, 19:29

da...il jurizez eu. Poti descarca solutia mea de mai sus si sa iti verifici sursa pe un set mai variat de teste.

by **Mihai** » 20 Nov 2011, 18:18

M-am înscris și eu în concurs, dar cum nu am acces la o mașină cu Windows nu cred că are rost să postez rezultatul aici - i-am trimis un mesaj privat lui Cătălin cu sursa, totuși.
Sper că-i ok rezolvarea, recunosc că n-am testat pe vreun alt exemplu în afară de cel dat de Cătălin în enunț :))

.

by **nomemory** » 20 Nov 2011, 18:27

Solutia mea e aici .
Sursa am trimis-o ca mesaj privat .

by **cata45** » 20 Nov 2011, 22:03

Am primit sursele tuturor. Le-am si evaluat. Voi posta rezultatele astazi dupa ora 20:30 deoarece maine nu am timp. Sper ca nu se supara nimeni. (Banuiesc ca nu a ramas nimeni cu implementarea pe ultima suta de metrii) %%-

L.E. (-- 20 Nov 2011, 22:03 --)

Am supus sursele pe un set de 10 teste. Iata rezultatele:

nomemory

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

TEST     |    TIMP       |  MESAJ EVALUATOR    |    PUNCTE
__________________________________________________
   1             0                     ok                            10
   2             0.04                ok                            10
   3             0.07                ok                            10
   4             0.23                ok                            10
   5             0                     ok                            10
   6             0                     ok                            10
   7             0                     ok                            10
   8             0                     ok                            10
   9             0                     ok                            10
   10           0                     ok                            10
TOTAL  EVALUARE                                                 100
 

new_luca

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

TEST     |    TIMP       |  MESAJ EVALUATOR    |    PUNCTE
__________________________________________________
   1             0                     ok                            10
   2             0                     wa                            0
   3             0.02                wa                            0
   4             0.05                wa                            0
   5             0                     ok                            10
   6             0                     wa                            0
   7             0                     wa                            0
   8             0                     wa                            0
   9             0                     wa                            0
   10           0                     wa                            0
TOTAL  EVALUARE                                             20
 

Mihai

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

TEST     |    TIMP       |  MESAJ EVALUATOR    |    PUNCTE
__________________________________________________
   1             0                     ok                            10
   2             0.05                ok                            10
   3             0.09                ok                            10
   4             0.17                ok                            10
   5             0                     ok                            10
   6             0                     ok                            10
   7             0                     ok                            10
   8             0                     ok                            10
   9             0.01                ok                            10
   10           0                     ok                            10
TOTAL  EVALUARE                                           100
Depunctat pentru eroare remediata. (line 21: syntax error before 'for' )  -10 p
TOTAL                                                                    90
 

cata45

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

TEST     |    TIMP       |  MESAJ EVALUATOR    |    PUNCTE
__________________________________________________
   1             0                     ok                            10
   2             0                     ok                            10
   3             0                     ok                            10
   4             0                     ok                            10
   5             0                     ok                            10
   6             0                     ok                            10
   7             0                     ok                            10
   8             0                     ok                            10
   9             0                     ok                            10
   10           0                     ok                            10
TOTAL  EVALUARE                                                 100
 

Surse:
nomemory

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

#include <cstdio>
#include <iostream>
#include <stack>
#include <vector>
 
#define N_MIN 1
#define N_MAX 301
#define M_MIN 0
#define M_MAX 32000
 
using namespace std;
 
const char * INPUT_FILE = "bitcell19.in";
const char * OUTPUT_FILE = "bitcell19.out";
 
bool read_input_file(const char *input_file, bool (*graph)[N_MAX], int &N)
{
    int M = 0, A = 0, B = 0;
   
    FILE *input = fopen(input_file, "r");
    if (!input) {
        fprintf(stderr, "Cannot read file: %s .\n", input_file);
        return false;
    }
   
    fscanf(input, "%d %d", &N, &M);
    if (N_MIN > N || N >= N_MAX) {
        fprintf(stderr, "Invalid N value: %d (%d <= N <= %d) .\n", N, N_MIN, N_MAX-1);
        return false;
    }
    if (M_MIN > M || M > M_MAX) {
        fprintf(stderr, "Invalid M value: %d (%d <= M <= %d) .\n", M, M_MIN, M_MAX);
        return false;
    }
   
    for(int i = 0; i < M; i++) {
        fscanf(input, "%d %d", &A, &B);
        if(N_MIN > A || A >= N_MAX || N_MIN > B || B >= N_MAX) {
            fprintf(stderr, "Invalid values for A (%d) or B(%d)", A, B);
        }
        graph[A][B] = true;
        graph[B][A] = true;
    }
 
    fclose(input);
   
    return true;
}
 
void solution(const bool (*graph)[N_MAX], const int N, int &result)
{
    vector<bool> visited(N_MAX, false);
    int cidx = 0;
    for(int i = N_MIN; i <= N; ++i) {
        if(!visited[i]) {
            stack<int> idx;
            idx.push(i);
            while(!idx.empty()) {
                cidx = idx.top();
                idx.pop();
                visited[cidx] = true;
                for(int j = N_MIN; j <= N; ++j) {
                    if(graph[cidx][j] == 1 && visited[j]==false) {
                        idx.push(j);
                    }
                }
            }
            result++;
        }
    }
}
 
bool write_output_file(const char *output_file, const int result)
{
    FILE *output = fopen(output_file, "w");
   
    if(!output) {
        fprintf(stderr, "Cannot write file: %s .\n", output_file);
        return false;        
    }
   
    fprintf(output, "%d", result);
   
    fclose(output);
   
    return true;
}
 
int main(int argc, char *argv[])
{
    int N = 0, result = 0;
    bool graph[N_MAX][N_MAX];
   
    if(!read_input_file(INPUT_FILE, graph, N)) {
        return 1;
    }  
    solution(graph, N, result);
    if(!write_output_file(OUTPUT_FILE, result)) {
        return 1;
    }
   
    return 0;
}

Mihai

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

/*
   Problema 19 - Bitcell - Domnul Z
   Rezolvarea problemei consta in determinarea numarului de componente conexe ale unui graf cu N varfuri si M muchii
*/
 
#include <fstream>
#include <vector>
#include <bitset>
 
#define PROBLEMA "bitcell19"
#define NMAX 305
 
using namespace std;
ifstream in(PROBLEMA ".in");
ofstream out(PROBLEMA ".out");
 
bitset<NMAX> folositDFS;
void marcareConexe(vector<int> graf[], int tata)
{
  folositDFS[tata]=true
  for(vector<int>::iterator i=graf[tata].begin();i!=graf[tata].end();++i)
    if(!folositDFS[*i])
      marcareConexe(graf,*i);
}
 
int main()
{
  int N,M,contor=0;
  vector<int> graf[NMAX];
  bitset<NMAX> folosit[NMAX];
 
  //citim graful
  in>>N>>M;
  for(int i=1;i<=M;++i)
  {
    int s,d;
    in>>s>>d;
    if(!folosit[s][d])
    {
      folosit[d][s]=folosit[s][d]=true;
      graf[s].push_back(d);
      graf[d].push_back(s);
    }
  }
 
  //determinam numarul de componente conexe
  for(int i=1;i<=N;i++)
    if(!folositDFS[i])
      marcareConexe(graf,i),
      contor++;
 
  //afisam numarul de componente conexe
  out<<contor<<endl;
 
  in.close();
  out.close();
  return 0;
}

new_luca

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

#include <stdio.h>
 
int main(void)
{
    short v[301] = {0}, i, j;
    int n, indice = 1, a, b, indici_distrusi = 1;                                    
    long m;                                  
   
    freopen("bitcell19.in", "r", stdin);
    freopen("bitcell19.out", "w", stdout);
   
    scanf("%d %d", &n, &m);n++;
   
    for(i = 0;i < m;i++)
    {
        scanf("%d %d", &a, &b);
       
        if(!v[a] && !v[b])                    
        {
            v[a] = v[b] = indice;
            indice++;
        }
        else      
        {
            if(v[a])              
            {
                if(!v[b])v[b] = v[a];    
                else                      
                {
                    for(j = 1;j < n;j++)
                    {
                        if(v[j] == v[a])v[j] = v[b];
                    }
                    indici_distrusi++;
                }
            }
            else              
            {
                if(v[b])v[a] = v[b];
            }
        }
    }
   
    for(i = 1;i < n;i++)
    {
        if(v[i] == 0)indice++;
    }
   
    printf("%d", indice-indici_distrusi);
 
    return 0;
}

cata45

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

#include<fstream>
using namespace std;
#define IN "bitcell19.in"
#define OUT "bitcell19.out"
FILE *f, *g;
int x, y, i, n, m, a[305][305], cmp, v[305];
void BFS(int v[305], int cmp, int s)
{
    int coada[305], i, p, u;
    for(i=1; i<=n; i++)
        coada[i]=0;
    p=1; u=1;
    coada[p]=s;
    v[s]=cmp;
    while(p<=u)
    {
        for(i=1; i<=n; i++)
        {
            if(a[i][coada[p]]==1 && v[i]==0)
            {
                u++;
                coada[u]=i;
                v[i]=cmp;
            }
        }
        p++;
    }
}
int valid(int v[305])
{
    int i;
    for(i=1; i<=n; i++)
        if(v[i]==0)
            return i;
    return -1;
}
int main()
{
    f=fopen(IN, "r");
    g=fopen(OUT, "w");
    fscanf(f, "%d %d", &n, &m);
    for(i=1; i<=m; i++)
    {
        fscanf(f, "%d %d", &x, &y);
        a[x][y]=1;
        a[y][x]=1;
    }
    cmp=1;
    BFS(v,cmp, 1);
 
    x=valid(v);
    while(x!=-1)
    {
        cmp++;
        BFS(v,cmp,x);
        x=valid(v);
    }
    fprintf(g, "%d\n", cmp);
    fclose(f);
    fclose(g);
    return 0;
 
}

Castigatorul este :
Offtopic
Felicitari! Te asteptam cu noua tema de concurs!

by **new_luca** » 20 Nov 2011, 22:24

Brava baieti

@cata45, mai ai idee care erau intrarile pentru teste

sunt curios ce am gresit la ideea mea, sa incerc o remediez, ar fi pacat la cat mi-am stors creierul :))

sa nu ii dau de cap.

Iar in legatura cu celelalte coduri :))

DAMN! stiu ca inca nu am inteles nici unul, dar inca incerc.

Peace :)>-

by **cata45** » 20 Nov 2011, 22:49

Testele au fost generate random si nu le mai am. Defapt nici nu le-am stiut. Ideea era sa faci un graf si sa pui muchii intre temele cu elemente in comun. In acest graf se formau niste componente. Si tot ce trebuia sa faci era sa determini numarul de componente conexe.

L.E. (-- 20 Nov 2011, 22:49 --)

Plus ca intrarile pe care au fost testate solutiile erau huge. Nu cred ca ai fi avut rabdare sa iti testezi solutia pe un test cu cateva zeci de mii de numere.

by **new_luca** » 20 Nov 2011, 23:21

Ce nasol e ca nu stiu nici chestii d-astea de baza "Grafuri" :))

, nu stiu prea bine ce sunt, trebuie sa le studiez...

Eu am facut o rezolvare "artificiala" din capul meu, dar se pare ca ceva a mers gresit

, eu mai facusem cu executabilul tau teste dar nu am avut noroc sa gasesc bube

- vector cu 300 componente pentru fiecare copil/tema posibila initializat cu 0
- un indice initializat cu 1 si care ar creste cu 1 de fiecare data cand intalneste o tema noua( ambele pozitii din vector = 0)
- citesc cele m perechi pe rand si daca vectorii corespunzatori sunt egali cu 0 amandoi, cresc indicele si il tin minte pe cele 2 pozitii din vector
- daca pozitiile din vector sunt diferite de 0, daca e doar una e bine, in cea = 0 pun indicele diferit de 0, iar daca ambele sunt diferite de 0, distrug unul din indici peste tot in vector si il pun pe celalalt
- tin minte de cate ori am distrus indici
- si raspunsul ar trebui sa fie valoarea maxima a indicelui fara numarul de indici distrusi

Daca a inteles cineva ce am spus aici :))

sunt bucuros, poate are si logica...la mine in cap cel putin ar avea, poate e gresit dar nu imi dau seama inca.

Imi pare rau ca sunt asa obositor

, dar asta sunt :-bd

by **nomemory** » 21 Nov 2011, 00:30

^^^Multumesc
:">

Me => Happy

Ma puteti pasui pana maine sau cel mai tarziu Marti cu noua tema de concurs ?

BitCell

[19] Concurs - Domnul Z

[19] Concurs - Domnul Z

Re: [19] Concurs - Domnul Z

Re: [19] Concurs - Domnul Z

Re: [19] Concurs - Domnul Z

Re: [19] Concurs - Domnul Z

Re: [19] Concurs - Domnul Z

Re: [19] Concurs - Domnul Z

Re: [19] Concurs - Domnul Z

Re: [19] Concurs - Domnul Z

Re: [19] Concurs - Domnul Z

Re: [19] Concurs - Domnul Z

Re: [19] Concurs - Domnul Z

Re: [19] Concurs - Domnul Z

Who is online