Afişează mesaje
Pagini: [1] 2 3
1  infoarena - concursuri, probleme, evaluator, articole / Informatica / Macrouri : Aprilie 11, 2014, 17:48:47
Poate sa imi spuna cineva ce face urmatoarea secventa de cod si mai ales partea cu "#define new DEBUG_NEW". Imi aloca o constanta dinamica care va fi preprocesata ?

#ifdef _DEBUG
#define new DEBUG_NEW
#endif
2  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 290 Gandaci Java : Martie 28, 2013, 17:05:38
Da ma gandeam ca trebuie sa parsez si am luat 100. Mersi mult pentru cele 2 sfaturi cruciale. Mai ales ala cu Graf.clear am sa-l retin toata viata  Banana
3  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 290 Gandaci Java : Martie 28, 2013, 17:00:11
Wow am luat 90. Inca iau TLE pe 2 teste.
4  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 290 Gandaci Java : Martie 28, 2013, 16:48:11
Intr-adevar uitasem sa setez la 0 toti vectorii. Insa am facut aceasta modificare si iau 10 pcte. Iau si WA si TLE  pe unele teste.
Uite acum arata acum programul:

Cod:
#include <cstdio>
#include <vector>
#include <cstring>
#define NMAX 10010
using namespace std;

vector < int > Graf[NMAX];
int vizitat[NMAX];
int dr[NMAX];
int g[NMAX];
int st[NMAX];
int n,m,e,nr;
int T;
bool ok;

bool Hopcroft_Karp(int nod){

   if(vizitat[nod]) return 0;
   vizitat[nod] = 1;
    for(vector < int >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if(!dr[*it]){
            dr[*it] = nod;
            st[nod] = *it;
            return 1;
        }
    for(vector < int >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if( Hopcroft_Karp(dr[*it])){
            dr[*it] = nod;
            st[nod] = *it;
            return 1;
        }

return 0;
}

int main(){

freopen("java.in","r",stdin);
freopen("java.out","w",stdout);
int x,y;

    scanf("%d",&T);
    while(T){
          nr=0;
        scanf("%d%d%d",&m,&n,&e);
    while(e){

        scanf("%d%d",&x,&y);
        Graf[x].push_back(y);
        g[x] = 1;

    --e;
    }

    ok=1;
    nr=0;
    while(ok){

        ok = 0;
        for(register int i=1;i<=m;++i)
        if(!st[i])
        if(Hopcroft_Karp(i)) ok=1;
        memset(vizitat,0,sizeof(vizitat));
    }
        for(register int i=1;i<=n;++i)
            if(dr[i]) ++nr;
            printf("%d\n",nr);

     for(register int i=1;i<=m;++i)
        if(g[i])
        Graf[i].assign(Graf[i].size()+1,0);
        memset(g,0,sizeof(g));
        memset(dr,0,sizeof(dr));
        memset(st,0,sizeof(st));
        memset(vizitat,0,sizeof(vizitat));
    --T;

    }
return 0;
}

Editat de moderator: Foloseste tag-ul [ code ] [/ code ] cand postezi cod!
5  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 290 Gandaci Java : Martie 28, 2013, 16:28:13
Algoritmul meu este de a obtine un cuplaj maxim intre cercetatori(multime 1-m) si gandaci. Iau WA pe toate testele. In exemplu imi da bine. Am optimizat sa nu iau TLE sau MME. Imi bat capul de ore intregi si nu vad greseala. Ce am putut gresi aici ?
<code>
 #include <cstdio>
#include <vector>
#include <cstring>
#define NMAX 10010
using namespace std;

vector < int > Graf[NMAX];
int vizitat[NMAX];
int dr[NMAX];
int g[NMAX];
int st[NMAX];
int n,m,e,nr;
int T;
bool ok;

bool Hopcroft_Karp(int nod){

   if(vizitat[nod]) return 0;
   vizitat[nod] = 1;
    for(vector < int >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if(!dr[*it]){
            dr[*it] = nod;
            st[nod] = *it;
            return 1;
        }
    for(vector < int >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if( Hopcroft_Karp(dr[*it])){
            dr[*it] = nod;
            st[nod] = *it;
            return 1;
        }

return 0;
}

int main(){

freopen("java.in","r",stdin);
freopen("java.out","w",stdout);
int x,y;

    scanf("%d",&T);
    while(T){
          nr=0;
        scanf("%d%d%d",&m,&n,&e);
    while(e){

        scanf("%d%d",&x,&y);
        Graf
  • .push_back(y);
       g
  • = 1;

    --e;
    }

    ok=1;
    nr=0;
    while(ok){

        ok = 0;
        for(register int i=1;i<=m;++i)
        if(!st)
        if(Hopcroft_Karp(i)) ok=1;
        memset(vizitat,0,sizeof(vizitat));
    }
        for(register int i=1;i<=n;++i)
            if(dr) ++nr;
            printf("%d\n",nr);

     for(register int i=1;i<=m;++i)
        if(g)
        Graf.assign(Graf.size()+1,0);
        memset(g,0,sizeof(g));
    --T;

    }
return 0;
}
</code>
6  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 914 Ghizi : Martie 26, 2013, 21:59:38
Si eu am aceeasi problema ca a lui George, algoritmul este le fel gandit, si iau 10 pcte si chiar nu stiu ce sa mai fac Brick wall.
Idei ?
7  infoarena - concursuri, probleme, evaluator, articole / Informatica / Răspuns: Operatori pe biti : Martie 19, 2013, 21:59:38
Mersi mult, acum stiu ce am de facut.
8  infoarena - concursuri, probleme, evaluator, articole / Informatica / Operatori pe biti : Martie 19, 2013, 21:38:53
Imi spune si mie cineva ce face operatorul <<= , respectiv >>= ?
9  infoarena - concursuri, probleme, evaluator, articole / Arhiva educationala / Răspuns: 007 Arbori de intervale : Martie 15, 2013, 17:00:40
Imi poate spune cineva ce reprezinta vecotul A in care se retin elemente din vector ? sad
10  infoarena - concursuri, probleme, evaluator, articole / Informatica / Submatrice : Martie 12, 2013, 17:55:04
Am o matrice de n*m si trebuie sa gasesc toate submatricile a caror suma este divizibila cu 3. Eu fac in O(n^3), fixandu-mi 2 linii si calculand toate submatricile dintre acele linii si verificand daca suma respectiva e divizibila cu 3.
Imi da raspuns aproximativ, insa stiu ca imi scapa ceva marunt  Brick wall
Cod:
for(register int i=1;i<=n;++i)
        for(register int j=i;j<=n;++j){

         S = 0;
            for(register int C=1;C<=m;++C){
                for(register int ii=i;ii<=j;++ii)
                    B[C]+=M[ii][C];

              S+=B[C];
                    if(S%3 == 0)
                        nr++;
}

        memset(B,0,sizeof(B));
        }
11  infoarena - concursuri, probleme, evaluator, articole / Informatica / Răspuns: Lot 2008 Neamt - probleme & subiecte : Martie 12, 2013, 17:52:24
Gasesti tot ce ai nevoie pe Infoarena la sectiunea Downloads. Ai subiecte cu indicatii de rezolvare + surse oficiale.
12  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 338 Ograzi : Martie 10, 2013, 13:54:14
Eu incerc sa fac O(n*m), adica sa verific pentru fiecare oita daca intra intr-o ograda. Imi da raspuns corect doar in unele cazuri si chiar nu inteleg ce imi scapa la implementare : Oita[j] coord unei oi si Ograd coord din stanga jos a ograzii.

Nmax = M;
    for(register int i=1;i<=N;++i)
        for(register int j=1;j<=M;++j)
            if(Oita[j].x <= Ograd.x +H && Oita[j].x >= Ograd.x && Oita[j].y <= Ograd.y +L && Oita[j].y >= Ograd.y)
                Nmax--;

    printf("%d",Nmax);
13  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 341 Take 5 : Martie 09, 2013, 22:36:13
Am facut O(n^3) cu hashuri si iau 65 de pct cu TLE si am incercat sa fac putin altfel si acum iau 25 de pct cu MME. Cum e posibil sa iau MME cand memoria folosita este aceeasi ? Chiar nu inteleg ce naiba se intampla  Brick wall
Iata codul initial:

inline void solve(){
 
int S=0;
    for(register int i=1;i<=N-2;++i){
        for(register int j=i+1;j<=N-1;++j){
            for(register int k=j+1;k<=N;++k){
                    S = V+V[j]+V[k];
 
            if(C-S>0)
                Search(C-S);
            }
 
        }
 for(register int z=1;z<i;++z)
            Add(V+V[z]);
}
 
printf("%d",nr);
}

Si iata codul cu care iau MME:

inline void solve(){

int S=0;
    for(register int i=1;i<N;++i){
        for(register int j=i+1;j<=N;++j){

                    S = V+V[j];
                if(C-S>0)
                Search(C-S);
}

 for(register int z=1;z<i;++z)
    for(register int j=z+1;j<i;++j)
            Add(V+V[z]+V[j]);
}

printf("%d",nr);
}
14  infoarena - concursuri, probleme, evaluator, articole / Arhiva educationala / Răspuns: 005 Potrivirea sirurilor : Martie 08, 2013, 18:08:54
Am facut KMP si am luat 100, insa vreau sa fac si Rabin Karp. Am inteles foarte bine cum se face teoretic insa ceva nu imi iese la implementare. Aveti vreo idee ?

Cod:
#include <cstdio>
#include <cstring>
#define NMAX 2000001
#define min(a,b) a<b ? a:b
using namespace std;

char A[NMAX],B[NMAX];
int n,m,nr,a,b;
int Sol[NMAX];
int t[NMAX];

inline unsigned long putere(int x,int k,int MOD){

    if (k == 0)
        return 1;
   else if(k%2 == 0){
       a = putere(x,k/2,MOD);
        return a*a%MOD;
   }
   else{
        a = putere(x,k/2,MOD);
        b = a*a%MOD;
        return b*x % MOD;
   }
}

inline int match(char *T, char *P,int j){

    for(register int i=0;i<m;++i)
        if(T[i+j] != P[i])
            return 0;
return 1;
}

inline void Rabin_Karp(char *T,char *M,int d,int MOD){

    unsigned long h,P=0;
    n = strlen(T);
    m = strlen(M);

        t[0] =0;
        h = putere(d,m-1,MOD);
    for(register int i=0;i<m;++i){
        P = (d*P + M[i])% MOD;
        t[0] = (d*t[0] + T[i])%MOD;
}

    printf("%d\n",P);
    for(register int i=0;i<=n-m;++i){

        printf("%d\n",t[i]);
        if(P == t[i]){
            if(match(T,M,i))
                    Sol[++nr] = i;
                    printf("%d\n",i);
                  }

         t[i+1] = (d*(t[i] - T[i+1]*h) + T[i+m+1])%MOD;
        }
}

int main(){


freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);

fgets(B,sizeof(B),stdin);
fgets(A,sizeof(A),stdin);

    Rabin_Karp(A,B,256,100003);
    printf("%d\n",nr);
    for(register int i=1;i<=min(nr,1000);++i)
        printf("%d ",Sol[i]);

return 0;
}

Editat de admin: Foloseste tagul "code" atunci cand postezi surse.
15  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 187 Ecuatii : Martie 07, 2013, 22:31:43
Da .. mi-am dat seama ce nu facusem bine. Acum am luat 100. Mersi mult  Very Happy  peacefingers
16  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 187 Ecuatii : Martie 06, 2013, 20:39:59
Ok, am modificat in sensul ca de fiecare cand gasesc un rezultat al sume i^3 + j^3 + K^3 scot din hash valoarea respectiva si tot nu imi da bine. De ex pe codul meu imi da 109 de 654. Sorry dar tot nu reusesc sa imi dau seama ce nu e bine  Brick wall.
Iata ce am modificat fata de data trecuta: Am facut o functie remove

void remove(int X){

    int key = abs(X%NMAX);
     for(vector < int >::iterator it = Hash[key].begin();it!=Hash[key].end();++it)
        if(*it == X){
            Hash[key].erase(it);
            return ;
        }
}

si cand numar solutiile fac asta :

 for(int k=-50;k<=50;++k)
        for(int i=-50;i<=50;++i)
            for(int j=-50;j<=50;++j)
                    if(search(V[3]*k*k*k + V[4]*i*i*i + V[5]*j*j*j)){
                            Nmax++;
                        remove(V[3]*k*k*k + V[4]*i*i*i + V[5]*j*j*j);
                    }
17  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 187 Ecuatii : Martie 06, 2013, 15:34:28
Am incercat si eu sa fac problema si nu inteleg unde gresesc. Am wa dar totusi soloutie mea este aproape de alte exemple, insa nu stiu
ce nu fac bine. Salvez toate solutiile posibile a primelor 2 necusoncute apoi caut toate solutiile posibile pentru urmatoarele 3 necunoscute astfel incat suma lor sa fie egala cu opusul sumei primelor 2. Iata si codul meu :

#include <cstdio>
#include <vector>
#include <stdlib.h>
#define NMAX 660000
using namespace std;

int V[5];
vector < int > Hash[NMAX];
int Nmax;

 void citesc(){

    freopen("eqs.in","r",stdin);
    freopen("eqs.out","w",stdout);
    for(register int i=1;i<=5;++i)
    scanf("%d",&V);
}


 int search(int X){
    int key = abs(X%NMAX);
    for(vector < int >::iterator it = Hash[key].begin();it!=Hash[key].end();++it)
        if(*it == X)
            return 1;
return 0;
}

 void add(int X){
    int key = abs(X%NMAX);
    Hash[key].push_back(X);
}


void solve(){

    for(int i=-50;i<=50;++i)
        for(int j=-50;j<=50;++j)
                add(-V[1]*i*i*i - V[2]*j*j*j);

    for(int k=-50;k<=50;++k)
        for(int i=-50;i<=50;++i)
            for(int j=-50;j<=50;++j)
                    if(search(V[3]*k*k*k + V[4]*i*i*i + V[5]*j*j*j))
                            Nmax++;


}

int main(){

    citesc();
    solve();
    printf("%d",Nmax);

return 0;
}
18  infoarena - concursuri, probleme, evaluator, articole / Arhiva educationala / Răspuns: 005 Potrivirea sirurilor : Martie 04, 2013, 19:44:46
Bine ca mi-ati spus ca e O(n^2). Acum stiu ca trebuie sa invat KMP.
19  infoarena - concursuri, probleme, evaluator, articole / Arhiva educationala / Răspuns: 005 Potrivirea sirurilor : Martie 03, 2013, 22:09:55
Eu iau 60 de puncte pe problema cu TLE la 2 teste si fac direct cu strstr care este KMP deja optimizat din cate stiu eu. Care ar putea fi problema ? E mai rapid cu hashing ?
20  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 934 Trilant : Februarie 28, 2013, 16:42:04
Imi poate da cineva si mie un exemplu mai mare sa vad ce nu imi merge ? Mie imi da costul prea mare.
21  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 727 Desen : Februarie 28, 2013, 13:24:42
Ok am inteles, thanks man
22  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 142 Ciclu : Februarie 27, 2013, 21:56:47
Vreau sa gasesc cea mai mare valoare intre 2 numere cunoscute de tip float. Acea valoare o voi scadea pe toate muchiile unui graf, astfel incat sa nu obtin ciclu negativ daca aplic algoritmul Bellman Ford.
Eu am incercat ceva si nu inteleg ce nu merge. Mie mijloc imi returneaza la final ca fiind 1.5 si eu trebuie sa obtin 1.75.Ma intereseaza cel mai mult de ce nu merge cand caut binar in main, in rest cred ca am facut bine. Iata sursa mea:

#include <cstdio>
#include <vector>
#include <list>
#include <utility>
#include <queue>
#include <cstring>
#include <iomanip>
#define inf 1000000
#define NMAX 1001
using namespace std;

typedef pair<int,float> pereche;
vector < list < pereche > > Graf;
queue < int > q;
int inQueue[NMAX],vizitat[NMAX];
vector < int > aparitii;
vector < float > d;
int n,m,scaderi;
float minim = inf;

void citesc(){

    int x,y;
    float c;
    freopen("ciclu.in","r",stdin);
    freopen("ciclu.out","w",stdout);
    scanf("%d%d",&n,&m);
    Graf.resize(n+1);
    d.resize(n+1);
    aparitii.resize(n+1);
    for(register int i=1;i<=m;++i){
        scanf("%d%d%f",&x,&y,&c);
        Graf
.push_back(pereche(y,c));
        Graf[y].push_back(pereche(x,c));
        if(c < minim)
            minim = c;
    }
}

void DFS(int nod){

    vizitat[nod] = 1;
    for(list < pereche >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if(!vizitat[it->first]){
            it->second -= minim;
            DFS(it->first);
    }}

int Bellman_Ford(int nod){

    int top;
    q.push(nod);
    inQueue[nod] = 1;
    ++aparitii[nod];
    d[nod] = 0;
        while(!q.empty()){
            top = q.front();
            q.pop();
            inQueue[top] = 0;
                for(list <pereche>::iterator it = Graf[top].begin();it!=Graf[top].end();++it)
                    if(d[it->first] > d[top] + it->second){
                        d[it->first] = d[top] + it->second;
                        if(!inQueue[it->first]){
                            inQueue[it->first] = 1;
                            q.push(it->first);
                        }
                    ++aparitii[it->first];
                    if(aparitii[it->first] >= n)
                    return 0;
            }
        }
return 1;
}

int main(){

    citesc();
    DFS(1);
        scaderi++;
 d.assign(n+1,inf);
 while(Bellman_Ford(1)){
            d.assign(n+1,inf);
            memset(vizitat,0,sizeof(vizitat));
            aparitii.assign(n+1,0);
            DFS(1);
        scaderi++;
        }

   float inceput = (scaderi-1)*minim;
   float sfarsit = scaderi*minim;
   float mijloc = 0;

        while(inceput <= sfarsit){

            memset(vizitat,0,sizeof(vizitat));
            aparitii.assign(n+1,0);
            d.assign(n+1,inf);

            mijloc = (inceput+sfarsit)/2;
            minim = mijloc;
            DFS(1);
            if(!Bellman_Ford(1))
            sfarsit = mijloc-1;
            else
            inceput = mijloc+1;

        }

printf("%d\n",scaderi);
printf("%f",mijloc);
return 0;
}
23  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 727 Desen : Februarie 27, 2013, 21:08:50
Eu am o nelamurire. La un momentdat in exemplu, arborele de cost minim era 6, apoi cand s-a mai adaugat un nod costul in loc sa creasca a scazut la 5.656854. Daca adaug un nod nou nu trebuie sa gasesc distanta minima la unul din nodurile arborelui deja construit si sa o adaug la suma de cost minim a arborelui?
24  infoarena - concursuri, probleme, evaluator, articole / Informatica / Cautare ciclu negativ binar : Februarie 26, 2013, 22:54:26
Vreau sa gasesc cea mai mare valoare intre 2 numere cunoscute de tip float. Acea valoare o voi scadea pe toate muchiile unui graf, astfel incat sa nu obtin ciclu negativ daca aplic algoritmul Bellman Ford.
Eu am incercat ceva si nu inteleg ce nu merge. Mie mijloc imi returneaza la final ca fiind 1.5 si eu trebuie sa obtin 1.75.Ma intereseaza cel mai mult de ce nu merge cand caut binar in main, in rest cred ca am facut bine. Iata sursa mea:

#include <cstdio>
#include <vector>
#include <list>
#include <utility>
#include <queue>
#include <cstring>
#include <iomanip>
#define inf 1000000
#define NMAX 1001
using namespace std;

typedef pair<int,float> pereche;
vector < list < pereche > > Graf;
queue < int > q;
int inQueue[NMAX],vizitat[NMAX];
vector < int > aparitii;
vector < float > d;
int n,m,scaderi;
float minim = inf;

void citesc(){

    int x,y;
    float c;
    freopen("ciclu.in","r",stdin);
    freopen("ciclu.out","w",stdout);
    scanf("%d%d",&n,&m);
    Graf.resize(n+1);
    d.resize(n+1);
    aparitii.resize(n+1);
    for(register int i=1;i<=m;++i){
        scanf("%d%d%f",&x,&y,&c);
        Graf
  • .push_back(pereche(y,c));
        Graf[y].push_back(pereche(x,c));
        if(c < minim)
            minim = c;
    }
}

void DFS(int nod){

    vizitat[nod] = 1;
    for(list < pereche >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if(!vizitat[it->first]){
            it->second -= minim;
            DFS(it->first);
    }}

int Bellman_Ford(int nod){

    int top;
    q.push(nod);
    inQueue[nod] = 1;
    ++aparitii[nod];
    d[nod] = 0;
        while(!q.empty()){
            top = q.front();
            q.pop();
            inQueue[top] = 0;
                for(list <pereche>::iterator it = Graf[top].begin();it!=Graf[top].end();++it)
                    if(d[it->first] > d[top] + it->second){
                        d[it->first] = d[top] + it->second;
                        if(!inQueue[it->first]){
                            inQueue[it->first] = 1;
                            q.push(it->first);
                        }
                    ++aparitii[it->first];
                    if(aparitii[it->first] >= n)
                    return 0;
            }
        }
return 1;
}

int main(){

    citesc();
    DFS(1);
        scaderi++;
 d.assign(n+1,inf);
 while(Bellman_Ford(1)){
            d.assign(n+1,inf);
            memset(vizitat,0,sizeof(vizitat));
            aparitii.assign(n+1,0);
            DFS(1);
        scaderi++;
        }

   float inceput = (scaderi-1)*minim;
   float sfarsit = scaderi*minim;
   float mijloc = 0;

        while(inceput <= sfarsit){

            memset(vizitat,0,sizeof(vizitat));
            aparitii.assign(n+1,0);
            d.assign(n+1,inf);

            mijloc = (inceput+sfarsit)/2;
            minim = mijloc;
            DFS(1);
            if(!Bellman_Ford(1))
            sfarsit = mijloc-1;
            else
            inceput = mijloc+1;

        }

printf("%d\n",scaderi);
printf("%f",mijloc);
return 0;
}
25  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 524 Plan : Februarie 22, 2013, 16:53:47
Eu iau 10 puncte cu wrong answer si nu stiu de ce. Imi puteti da va rog niste teste si rezultatul lor ca sa ma conving unde este greseala ?
Pagini: [1] 2 3
Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines