|
|
 #include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
class MountainRoad
   {
 public:
double findDistance(vector <int> start, vector <int> finish)
  {
sort(start.begin(),start.end());
sort(finish.begin(),finish.end());
return sqrt(2.0)*(finish.back()-start.front());
 }
 };
#include <iostream>
using namespace std;
class OddDivisors
{
public:
long long findSum(int n)
{
long long sum=0LL;
for(;n;n/=2)
{
long long k=(n+1)/2;
sum+=k*k;
}
return sum;
}
};
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
struct point
{
int x,y;
point(int a,int b)
{
x=a;
y=b;
}
};
vector<point>A,B;
vector<point> find(int a)
{
vector<point>v;
int x,y;
for(x=0;x*x<=a;x++)
{
y=int( sqrt((1.0*a-x*x)) );
if( (x*x+y*y)==a )
{
v.push_back( point(x,y) );
v.push_back( point(x,-y) );
}
}
return v;
}
class MaxTriangle
{
public:
double calculateArea(int a,int b)
{
A=find(a);
B=find(b);
int i,j;
double res=-1;
for(i=0;i<A.size();i++)
for(j=0;j<B.size();j++)
{
double area=abs((A[i].x*B[j].y-A[i].y*B[j].x))/2.0;
if(area&&res<area)
res=area;
}
return res;
}
};
#include <iostream>
using namespace std;
const int size=1000005;
bool ok[size];
int ph[size];
int prime[size];
__int64 sum[size];
int pn;
int n;
void getph()
{
int i,j;
pn=0;
for(i=2;i<size;i++)
{
if(!ok[i])
{
prime[pn++]=i;
ph[i]=i-1;
}
for(j=0;(j<pn)&&(i*prime[j]<size);j++)
{
ok[i*prime[j]]=1;
if((i%prime[j])==0)
{
ph[i*prime[j]]=ph[i]*prime[j];
break;
}
else
ph[i*prime[j]]=ph[i]*(prime[j]-1);
}
}
}
int main()
{
ph[1]=1;
getph();
for(int i=2;i<size;i++)
sum[i]=sum[i-1]+ph[i];
while(scanf("%d",&n)!=EOF&&(n!=0))
printf("%I64d\n",sum[n]);
return 0;
}
#include <iostream>
using namespace std;
const int maxn=1005;
const int M=28;
int map[M][M];
int chu[M],ru[M];
bool vis[M];
int n;
int sum;
void dfs(int s)
{
vis[s]=true;
sum++;
int i;
for(i=0;i<26;i++)
if(map[s][i]&&!vis[i])
dfs(i);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(map,0,sizeof(map));
memset(chu,0,sizeof(chu));
memset(ru,0,sizeof(ru));
memset(vis,0,sizeof(vis));
scanf("%d",&n);
int i;
for(i=0;i<n;i++)
{
char word[maxn];
scanf("%s",&word);
int len=strlen(word);
map[word[0]-'a'][word[len-1]-'a']=1;
chu[word[0]-'a']++;
ru[word[len-1]-'a']++;
}
int n0=0,n1=0,n2=0,n3=0;
int s=-1,e=-1;
for(i=0;i<26;i++)
{
if(chu[i]==0&&ru[i]==0)
continue;
n0++;
if((ru[i]-chu[i])==1)
n2++;
if((chu[i]-ru[i])==0)
n3++;
if((chu[i]-ru[i])==1)
{
s=i;
n1++;
}
e=i;
}
sum=0;
if(s!=-1)
dfs(s);
else
dfs(e);
if(sum!=n0)
{
printf("The door cannot be opened.\n");
continue;
}
if( (n1==1&&n2==1&&n3==(n0-2)) || (n0==n3) )
printf("Ordering is possible.\n");
else
printf("The door cannot be opened.\n");
}
return 0;
}
#include <iostream>
using namespace std;
int main()
{
int ball[100001],n;
while(scanf("%d",&n)!=EOF&&n)
{
memset(ball,0,sizeof(ball));
int i;
for(i=0;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
ball[a]++;
ball[b+1]--;
}
int sum=0;
for(i=1;i<n;i++)
{
sum+=ball[i];
printf("%d ",sum);
}
printf("%d\n",sum+ball[i]);
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
const int maxn=1000;
struct group
{
int h,m,t;
};
group team[maxn];
int main()
{
int n2,n4,n6;
while(scanf("%d%d%d",&n2,&n4,&n6)!=EOF)
{
if(n2==0&&n4==0&&n6==0)
break;
char time[6];
int cnt=0;
while(scanf("%s",&time)!=EOF)
{
if(strcmp(time,"#")==0)
break;
int t;
scanf("%d",&t);
team[cnt].t=t;
team[cnt].h=(time[0]-'0')*10+(time[1]-'0');
team[cnt].m=(time[3]-'0')*10+(time[4]-'0');
cnt++;
}
int i,j;
vector<group> team12,team34,team56;
__int64 sum=0;
for(i=0;i<cnt;i++)
{
int len;
group tmp;
if(team[i].t==1||team[i].t==2)
{
len=team12.size();
if(len<n2)
{
team12.push_back(team[i]);
sum+=team[i].t;
continue;
}
tmp=team12.front();
int usetime=(team[i].h-tmp.h)*60+(team[i].m-tmp.m);
group fuck;
fuck=team12.back();
if(((team[i].h-fuck.h)*60+(team[i].m-fuck.m))<=0)
continue;
if(usetime<0)
continue;
if(usetime<30)
{
team[i].h=tmp.h+(tmp.m+30)/60;
team[i].m=(tmp.m+30)%60;
}
team12.erase(team12.begin());
team12.push_back(team[i]);
sum+=team[i].t;
}
if(team[i].t==3||team[i].t==4)
{
len=team34.size();
if(len<n4)
{
team34.push_back(team[i]);
sum+=team[i].t;
continue;
}
tmp=team34.front();
int usetime=(team[i].h-tmp.h)*60+(team[i].m-tmp.m);
group fuck;
fuck=team12.back();
if(((team[i].h-fuck.h)*60+(team[i].m-fuck.m))<=0)
continue;
if(usetime<0)
continue;
if(usetime<30)
{
team[i].h=tmp.h+(tmp.m+30)/60;
team[i].m=(tmp.m+30)%60;
}
team34.erase(team34.begin());
team34.push_back(team[i]);
sum+=team[i].t;
}
if(team[i].t==5||team[i].t==6)
{
len=team56.size();
if(len<n6)
{
team56.push_back(team[i]);
sum+=team[i].t;
continue;
}
tmp=team56.front();
int usetime=(team[i].h-tmp.h)*60+(team[i].m-tmp.m);
group fuck;
fuck=team12.back();
if(((team[i].h-fuck.h)*60+(team[i].m-fuck.m))<=0)
continue;
if(usetime<0)
continue;
if(usetime<30)
{
team[i].h=tmp.h+(tmp.m+30)/60;
team[i].m=(tmp.m+30)%60;
}
team56.erase(team56.begin());
team56.push_back(team[i]);
sum+=team[i].t;
}
}
printf("%I64d\n",sum);
}
return 0;
}
#include <iostream>
using namespace std;
const int maxn=32;
int n,k,m;
struct matrix
{
int m[maxn][maxn];
};
matrix mat;
matrix operator*(const matrix &a,const matrix &b)
{
matrix res;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
res.m[i][j]=0;
for(k=1;k<=n;k++)
{
res.m[i][j]+=a.m[i][k]*b.m[k][j];
res.m[i][j]%=m;
}
}
return res;
}
matrix operator+(const matrix &a,const matrix &b)
{
matrix res;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
res.m[i][j]=(a.m[i][j]+b.m[i][j])%m;
return res;
}
matrix power(int k)
{
matrix temp,res;
if(k==1)
return mat;
else
{
temp=power(k/2);
res=temp*temp;
if(k%2==1)
res=res*mat;
return res;
}
}
matrix solve(int k)
{
matrix temp,res;
if(k==1)
return mat;
else
{
res=solve(k/2);
if(k%2==1)
{
temp=power(k/2+1);
res=temp*res+res+temp;
}
else
{
res=power(k/2)*res+res;
}
return res;
}
}
void printf(const matrix & m)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<n;j++)
printf("%d ",m.m[i][j]);
printf("%d\n",m.m[i][j]);
}
}
int main()
{
scanf("%d%d%d",&n,&k,&m);
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&mat.m[i][j]);
matrix temp=solve(k);
printf(temp);
return 0;
}
#include <iostream>
using namespace std;
const int M=20000+5;
const int Maxn=100000+5;
int skill[M];
int tree[Maxn];
int lmax[M],lmin[M];
int rmax[M],rmin[M];
int lowbit(int t){return t&(-t);}
void add(int i)
{
while(i<Maxn)
{
tree[i]++;
i+=lowbit(i);
}
}
int sum(int i)
{
int tot=0;
while(i>0)
{
tot+=tree[i];
i-=lowbit(i);
}
return tot;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&skill[i]);
memset(tree,0,sizeof(tree));
for(i=1;i<=n;i++)
{
lmin[i]=sum(skill[i]);
lmax[i]=i-lmin[i]-1;
add(skill[i]);
}
memset(tree,0,sizeof(tree));
for(i=n;i>=1;i--)
{
rmin[i]=sum(skill[i]);
rmax[i]=sum(Maxn)-rmin[i];
add(skill[i]);
}
__int64 ans=0;
for(i=1;i<=n;i++)
ans+=lmax[i]*rmin[i]+lmin[i]*rmax[i];
printf("%I64d\n",ans);
}
return 0;
}
#include <iostream>
using namespace std;
const int maxn=205;
int qun[maxn];
char res[maxn];
char str[maxn];
int t[maxn];
int n;
void getT()
{
int i,j;
for(i=1;i<=n;i++)
{
if(t[i]==0)
{
int cnt=1;
int top=-1;
int same[maxn];
int pos=qun[i];
while(pos!=i)
{
same[++top]=pos;
pos=qun[pos];
cnt++;
}
t[i]=cnt;
for(j=0;j<=top;j++)
t[same[j]]=cnt;
}
}
}
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
int i,j;
for(i=1;i<=n;i++)
scanf("%d",&qun[i]);
memset(t,0,sizeof(t));
getT();
int k;
while(scanf("%d",&k)!=EOF&&k)
{
memset(res,'\0',sizeof(res));
memset(str,'\0',sizeof(str));
gets(str);
for(i=1;i<=n;i++)
{
int tmp=i;
for(j=0;j<k%t[i];j++)
tmp=qun[tmp];
if(str[i]=='\0') res[tmp]=' ';
else res[tmp]=str[i];
}
printf("%s\n",res+1);
}
printf("\n");
}
return 0;
}
#include <iostream>
using namespace std;
#define min(a,b)(a<b?a:b)
#define max(a,b)(a>b?a:b)
const int maxn=15;
struct point{int x,y;};
struct line{point a,b;};
line straw[maxn];
bool link[maxn][maxn];
int n;
int multi(point p1,point p2,point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
bool across(line u,line v)
{
if( max(u.a.x,u.b.x)>=min(v.a.x,v.b.x)&&
max(v.a.x,v.b.x)>=min(u.a.x,u.b.x)&&
max(u.a.y,u.b.y)>=min(v.a.y,v.b.y)&&
max(v.a.y,v.b.y)>=min(u.a.y,u.b.y)&&
(multi(v.a,u.b,u.a)*multi(u.b,v.b,u.a)>=0)&&
(multi(u.a,v.b,v.a)*multi(v.b,u.b,v.a)>=0) )
return 1;
else return 0;
}
void check()
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
if(link[i][k])
for(j=1;j<=n;j++)
if(link[k][j]) link[i][j]=true;
}
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
int i,j;
for(i=1;i<=n;i++)
{
int sx,sy,ex,ey;
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
straw[i].a.x=sx;straw[i].a.y=sy;
straw[i].b.x=ex;straw[i].b.y=ey;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
link[i][j]=link[j][i]=across(straw[i],straw[j]);
check();
int cx,cy;
while(scanf("%d%d",&cx,&cy)!=EOF&&cx!=0&&cy!=0)
if(link[cx][cy])
printf("CONNECTED\n");
else printf("NOT CONNECTED\n");
}
return 0;
}
#include <iostream>
using namespace std;
int r[301][301];
int c[301][301];
int a[301][301];
int b[301][301];
int rr,cc;
bool check(int i,int j,int k)
{
if(r[i][j+k-1]-r[i][j-1]==k)
if(r[i+k-1][j+k-1]-r[i+k-1][j-1]==k)
if(c[i+k-1][j]-c[i-1][j]==k)
if(c[i+k-1][j+k-1]-c[i-1][j+k-1]==k)
return 1;
return 0;
}
void slove()
{
int i,j,k;
int cnt=0;
for(i=1;i<=rr;i++)
for(j=1;j<=cc;j++)
{
for(k=2;k<=rr&&k<=cc;k++)
{
if(check(i,j,k))
{
int sum=b[i+k-1][j+k-1]-b[i-1][j+k-1]-b[i+k-1][j-1]+b[i-1][j-1];
int cnt_1=sum-(k-1)*4;
int cnt_0=(k-2)*(k-2)-cnt_1;
if(abs(cnt_1-cnt_0)<=1)
cnt++;
}
}
}
printf("%d\n",cnt);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&rr,&cc);
int i,j;
for(i=1;i<=rr;i++)
for(j=1;j<=cc;j++)
{
scanf("%d",&a[i][j]);
b[i][j]=b[i-1][j]+b[i][j-1]+a[i][j]-b[i-1][j-1];//0 0->i j
r[i][j]=r[i][j-1]+a[i][j];//r
c[i][j]=c[i-1][j]+a[i][j];//c
}
slove();
}
return 0;
}
|