[shkola] Re: pishtov
- From: Bono Nonchev <madcow@xxxxxx>
- To: shkola@xxxxxxxxxxxxx
- Date: Thu, 20 Nov 2003 11:24:48 +0200 (EET)
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:
