[shkola] Re: pishtov

da, vqrno, trqbvashe da ti gi pratq. za revansh ti prashtam nqkolko resheniq 
(na stari zadachi, ot 2001 i 2003) v koito sym pisal dfs i dejkstra v 
poslednite dni dyrja da obeleja. shkolata naistina mi pokaza kakvo trqbva da 
doprocheta. kakto se kazva "some slight last-minute adjustments). mai veche i 
zagrqh ideqta, taka che se nadqvam da nqmam problem s neq. ednata e procedura 
za minimaxno tyrsene v zadachata ot minalata godina - A1. dinamichno 
optimirana. edna e za ocvetqvane na karta v 2 cvqta, obache q pisah s dfs! 
nadqvam se da vidq kak da pisha stek kratko, za da moga da izpolzvam bfs. vqrno 
e che izpolzvaneto na piramida shte poniji slojnostta na dejkstrata. ama ne sym 
siguren kak tochno da q napravq.

bono


 >
 >      Emi taka i ne poluchih nito edin ot 4-te graphski algorityma kakto se 
 > razbrahme na poslednata shkola, predi da vi pratq pishtova, ama kvo da se 
 > prai, myrzeli...
 >      DFS()-to i BFS()-to nqma da gi komentiram :) te sa za da se vidi kak se 
 > polzva dist[]
 >
 

-----------------------------------------------------------------
http://www.Elmaz.com - Запознанства
//B2

#include "iostream.h"
#include "math.h"

#define MAXSTACK 100

int N,M;
char T[1000000];
char P[100];
char psT[100];
char psP[100];

void push(char *ps, char c)
{
        ps[int(c)-32]++;
}
void clear(char *ps)
{
        for(int i=0;i<MAXSTACK;i++)
                ps[i]=0;
}
int pop(char *ps, char c)
{
        return (((ps[int(c)-32]--)<0)? -1 : ps[int(c)-32]);
}
int cmp(char *ps1, char *ps2)
{
        int r=0;
        for(int i=0;i<MAXSTACK;i++)
                r+=abs(ps1[i]-ps2[i]);
        return (r==0);
}

void main()
{
        int i,r=0;;
        cin>>N;
        cin>>M;
        cin>>P;
        cin>>T;
        clear(psT);
        clear(psP);
        for(i=0;i<N;i++)
                push(psP,P[i]);
        for(i=0;i<N;i++)
                push(psT,T[i]);
        
        for(i=N;i<M;i++)
        {
                if(cmp(psT,psP)) r++;
                push(psT, T[i]);
                pop(psT, T[i-N]);
        }
        cout<<r;
}
//A1

#include "iostream.h"

int inv(int a) {return -a;}

int field[500][500];

int minimax(int a, int b, int turn)
{
        if(field[a][b]!=0)
                return field[a][b];
        if(a==1&&b==1) 
                return -1;
        int i,j;
        int tres=0;
        for(i=1,j=1;j<a;i++,j=i*i)
                if(minimax(a-j,b,inv(turn))==-1)
                        tres=1;
        for(i=1,j=1;j<b;i++,j=i*i)
                if(minimax(a,b-j,inv(turn))==-1)
                        tres=1;
        if(tres==0)     //ako nqma pyt kym pobeda na tozi igrach...
                tres=-1;
        field[a][b]=tres;
        return tres;
}

void main()
{
        int i,j;
        for(i=0;i<500;i++)
                for(j=0;j<500;j++)
                        field[i][j]=0;
        int i1,j1,i2,j2;
        int r=0;
        cin>>i1>>j1>>i2>>j2;
        for(i=i1+1;i<i2;i++)
                for(j=j1+1;j<j2;j++)
                        if(minimax(i,j,1)==1)
                                r++;
        cout<<r;
}
//SEGS

#include "fstream.h"
#include "stdlib.h"

struct cpath
{
        int size;
        int path[500];
        cpath(){size=0;}
        void add(int n) {path[size]=n;size++;}
        void add(cpath t) {for(int i=0;i<t.size;i++) add(t.path[i]);}
        void clear() {size=0;}
};

int data[500][2];
int N;
int adj[500][500];
int cmp[500];
cpath maxpaths[500];
int isin(int a[2], int b[2])
{
        if(a[0]<b[0]&&a[1]>b[1]) return 1;
        else return 0;
}

cpath findmax(int a)
{
        cpath result,t;
        if(!cmp[a]) 
        {
                for(int i=0;i<N;i++)
                        if(adj[a][i])
                        {
                                t=findmax(i);
                                if(result.size<t.size)
                                        result=t;
                        }
                if(maxpaths[a].size<result.size)
                        maxpaths[a]=result;
                cmp[a]=1;
        }
        t.clear();
        t.add(a);
        t.add(maxpaths[a]);
        return t;       
}


void main()
{
        int i=0,j=0;
        ifstream ifile;
        ofstream ofile;
        ifile.open("c:\\segs.inp");
        ofile.open("c:\\segs.out");
        ifile>>N;
        for(i=0;i<N;i++)
                for(j=0;j<N;j++)
                        adj[i][j]=0;
        for(i=0;i<N;i++)
        {
                ifile>> data[i][0]>>data[i][1];
        }
        
        //
/*      N=499;
        for(i=0;i<N;i++)
        {
                data[i][0]=rand();
                data[i][1]=rand();
        }//*/
        //
        for(i=0;i<N;i++)
                cmp[i]=0;
        for(i=0;i<N;i++)
                for(j=0;j<N;j++)
                        if(isin(data[i],data[j])&&i!=j)
                                adj[i][j]=1;
/*      for(i=0;i<N;i++)
        {
                for(int j=0;j<N;j++)
                        cout<<adj[j][i]<<' ';
                cout<<'\n';
        }*/
        //postroili sme grafa. sega s dfs tyrsim maksimalen pyt ot vseky vryh...
        //ndmax(
        for(i=0;i<N;i++)
                findmax(i);
        int cm=0;
        for(i=0;i<N;i++)
                if(maxpaths[i].size>maxpaths[cm].size)
                        cm=i;
        for(i=maxpaths[cm].size-1;i>=0;i--)
                ofile<<maxpaths[cm].path[i]+1<<' ';
        ofile<<cm+1;
        ifile.close();
        ofile.close();
}
//TWOC

#include "fstream.h"

int inv(int a)
{
        return (a==0?1:0);
}
                

int adj[100][100];
int Possible=1;
int result[100];
//int 
int N;

void dfs(int a, int color)
{
        if(result[a]==inv(color))
                Possible=0;
        if(result[a]==color)
                return;
        result[a]=color;
        for(int i=1;i<=N;i++)
        {
                if(!Possible)
                        return;
                if(adj[a][i])
                        dfs(i, inv(color));
        }       
}

void main()
{
        ifstream inp;
        ofstream out;
        int na;
        inp.open("c:\\twoc.inp");
        out.open("c:\\twoc.out");
        inp>>N;
        for(int j=1;j<=N;j++)
        {
                for(int k=1;k<=N;k++)
                        adj[j][k]=0;
                result[j]=-1;
        }
        
        for(int i=1;i<=N;i++)
        {
                while(1)
                {
                        inp>>na;
                        if(na==0) break;
                        else 
                                adj[i][na]=adj[na][i]=1;
                }
        }
//      result[1]=0;
        dfs(1,0);
        if (Possible)
                for(i=1;i<=N;i++)
                        out<<result[i];
        else
                out<<-1;

        inp.close();
        out.close();
}
//BLEK

#include "fstream.h"

ifstream ifile;
ofstream ofile;
long b[10000];
long N, K;

void computefib()
{
        int i;
        b[0]=b[1]=1;
        for(i=2;i<N+1;i++)                                      //izchislqvame 
chislata na fibonachi
                b[i]=b[i-1]+b[i-2];
}

void output(int n, int k)
{
        while(n>0)
        {
                if(k>b[n-1])
                {
                        ofile<<"10";
                        k-=b[n-1];
                        n-=2;
                }
                else
                {
                        ofile<<'0';
                        n--;
                }
        }

//      else cout<<"error trying to compute out(N,K) "<<n<<k;
}

void main()
{
        ifile.open("c:\\BLEX.inp");
        ofile.open("c:\\BLEX.out");
        ifile>>N>>K;
        computefib();   
        if(b[N]<K)              //ako broq na redicite ot N elementa e <K..
                ofile<<-1;
        else
        {
                output(N,K);
                ofile<<'\n';
        }
//              output(N+1,K);
//              ofile<<'\n';
//              output(N+2,K);
//              ofile<<'\n';
        ifile.close();
        ofile.close();
}

Other related posts: