A
#include <iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
using namespace std;
#define PI acos(-1.0)
typedef long long ll;
typedef pair<int,int> P;
const int maxn=1e5+,maxm=1e5+,inf=0x3f3f3f3f,mod=1e9+;
const ll INF=1e13+;
priority_queue<P,vector<P>,greater<P> >que;
struct edge
{
int from,to;
int cost;
};
int main()
{
int T;
int h1,h2,m1,m2,s1,s2;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d%d%d",&h1,&m1,&s1,&h2,&m2,&s2);
int sign=;
if(h1<h2) sign=;
else if(h1>h2) sign=;
else
{
if(m1<m2) sign=;
else if(m1>m2) sign=;
else
{
if(s1<s2) sign=;
else if(s1>s2) sign=;
}
}
if(sign==) cout<<"Player1"<<endl;
else if(sign==) cout<<"Player2"<<endl;
else cout<<"Tie"<<endl;
}
return ;
}
B
#include <iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
using namespace std;
#define PI acos(-1.0)
typedef long long ll;
typedef pair<int,int> P;
const int maxn=1e5+,maxm=1e5+,inf=0x3f3f3f3f,mod=1e9+;
const ll INF=1e13+;
priority_queue<P,vector<P>,greater<P> >que;
struct edge
{
int from,to;
int cost;
};
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
int ans=,cou=,sign=;
while(true)
{
if(sign>m) break;
cou=cou+sign;
ans++;
sign*=;
if(cou>=n) break;
}
////cout<<cou<<" "<<sign<<endl;
if(cou>=n) cout<<ans<<endl;
else
{
ans+=(n-cou)/m;
if((n-cou)%m) ans++;
cout<<ans<<endl;
}
}
return ;
}
C
#include <iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
using namespace std;
#define PI acos(-1.0)
typedef long long ll;
typedef pair<int,int> P;
const int maxn=1e5+,maxm=1e5+,inf=0x3f3f3f3f,mod=1e9+;
const ll INF=1e13+;
priority_queue<P,vector<P>,greater<P> >que;
struct edge
{
int from,to;
int cost;
};
char s[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,p;
scanf("%d%d",&n,&p);
getchar();
for(int i=; i<=n; i++) scanf("%c",&s[i]);
//cout<<s+1<<endl;
int ans=;
int l=inf,r=;
for(int i=; i<=n/; i++)
{
if(s[i]!=s[n+-i])
{
l=min(l,i);
r=max(r,i);
}
if(s[i]<=s[n+-i]) swap(s[i],s[n+-i]);
ans+=min(s[i]-s[n+-i],s[n+-i]+-s[i]);
}
if(p>n/) p=n+-p;
if(l>r) cout<<<<endl;
else
printf("%d\n",ans+r-l+min(abs(p-l),abs(p-r)));
}
return ;
}
D
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <sstream>
#include <vector> using namespace std; typedef long long ll;
/****************************************/
const int N = + ;
const int MOD = (int)1e9 + ;
int F[N], Finv[N], inv[N];//F是阶乘，Finv是逆元的阶乘
void init(){
inv[] = ;
for(int i = ; i < N; i ++){
inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
}
F[] = Finv[] = ;
for(int i = ; i < N; i ++){
F[i] = F[i-] * 1ll * i % MOD;
Finv[i] = Finv[i-] * 1ll * inv[i] % MOD;
}
}
int comb(int n, int m){//comb(n, m)就是C(n, m)
if(m < || m > n) return ;
return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;
}
int main(){
init();
int t,n,m,k,d;
scanf("%d",&t);
while(t--){
scanf("%d%d%d%d",&n,&m,&k,&d);
int ans=comb(n,m),x,da=,xiao=;
for(int i=;i<n;i++){
scanf("%d",&x);
if(x>=d)da++;
}
xiao=n-da;
for(int i=k-;i>=;i--){
ans=(ans+MOD-(comb(da,i)*1ll*comb(xiao,m-i))%MOD)%MOD;
}
printf("%d\n",ans);
}
}
E
#include <iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
using namespace std;
#define PI acos(-1.0)
typedef long long ll;
typedef pair<int,string> P;
const int maxn=1e5+,maxm=1e5+,inf=0x3f3f3f3f,mod=1e9+;
const ll INF=1e13+;
priority_queue<P,vector<P>,greater<P> >q;
struct edge
{
int from,to;
int cost;
};
int n,m,t;
int pa[];
int flag[][];
int sign[][];
int vis[];
int ans=;
void dfs(int x,int y,int cou)
{
//cout<<x<<" "<<y<<" "<<cou<<endl;
if(x>n)
{
if(cou==t) ans++;
return;
}
for(int k=; k<=t; k++)
{
if(k&&vis[k]) continue;
if(x->=&&flag[k][sign[x-][y]]) continue;
if(y->=&&flag[k][sign[x][y-]]) continue;
sign[x][y]=k;
vis[k]=;
dfs(y==m?x+:x,y==m?:y+,k==?cou:cou+);
sign[x][y]=;
vis[k]=;
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&t);
int p;
scanf("%d",&p);
for(int i=; i<=t; i++) pa[i]=i;
memset(flag,,sizeof(flag));
while(p--)
{
int a,b;
scanf("%d%d",&a,&b);
flag[a][b]=flag[b][a]=;
}
ans=;
memset(vis,,sizeof(vis));
memset(sign,,sizeof(sign));
dfs(,,);
if(ans==) cout<<"impossible"<<endl;
else cout<<ans<<endl;
}
return ;
}
F
#include <iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
using namespace std;
#define PI acos(-1.0)
typedef long long ll;
typedef pair<int,string> P;
const int maxn=1e5+,maxm=1e5+,inf=0x3f3f3f3f,mod=1e9+;
const ll INF=1e13+;
priority_queue<P,vector<P>,greater<P> >q;
struct edge
{
int from,to;
int cost;
};
map<string,map<string,int> >G;
map<string,int>dist;
struct node
{
string str;
int ss;
}N[];
bool cmp(struct node aa,struct node bb)
{
if(aa.ss!=bb.ss)
return aa.ss<bb.ss;
else
return aa.str<bb.str;
}
void dij(string s)
{
dist[s]=;
q.push(P(dist[s],s));
while(!q.empty())
{
P p=q.top();
q.pop();
string u=p.second;
map<string,int> ::iterator it;
for(it=G[u].begin(); it!=G[u].end(); it++)
{
if((*it).second==) continue;
//cout<<(*it).first<<" "<<(*it).second<<endl;
string v=(*it).first;
if(dist[v]>dist[u]+)
{
dist[v]=dist[u]+;
q.push(P(dist[v],v));
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
string s="Ahmad";
G.clear();
dist.clear();
int jishu=;
for(int i=; i<=n; i++)
{
string a,b,c;
cin>>a>>b>>c;
if(dist[a]==){
N[jishu++].str=a;
dist[a]=inf;
}
if(dist[b]==){
N[jishu++].str=b;
dist[b]=inf;
}
if(dist[c]==){
N[jishu++].str=c;
dist[c]=inf;
}
G[a][b]=G[b][a]=G[b][c]=G[c][b]=G[a][c]=G[c][a]=;
}
dij(s);
cout<<jishu<<endl;
for(int i=;i<jishu;i++)
N[i].ss=dist[N[i].str];
sort(N,N+jishu,cmp);
for(int i=;i<jishu;i++){
if(N[i].ss>=inf)
cout<<N[i].str<<" "<<"undefined"<<endl;
else
cout<<N[i].str<<" "<<N[i].ss<<endl;
}
}
return ;
}
G
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <sstream>
#include <vector>
#define PI acos(-1.0)
#define N 5e6+10
#define M 1000000007
#define inf 1e9
#define eps 1e-8
#define dazhi 2147483647
using namespace std; typedef long long ll; ll pow(ll a,ll b,ll p){ll sum=;for(a%=p;b;a=a*a%p,b>>=)if(b&)sum=sum*a%p;return sum;}
ll phi(ll n){ll i,re=n;for(i=;i*i<=n;i++)if(n%i==){re=re/i*(i-);while(n%i==)n/=i;}if(n>)re=re/n*(n-);return re%M;}
void exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=;y=;return;}exgcd(b,a%b,y,x);y-=x*(a/b);}
ll gcd(ll a,ll b){return b==?a:gcd(b,a%b);} /****************************************/
int main()
{ int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
if(n==)printf("Bob\n");
else printf("Alice\n");
}
}
H
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<bitset>
#include<set>
#define ll __int64
#define mod 100000000
#define N 5e6+10
#define M 1e
using namespace std;
ll a[]={ ,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
, ,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
};
int main()
{ int n;
while(scanf("%d",&n)!=EOF){
if(n==)
break;
printf("%I64d\n",a[n-]);
}
return ;
}
I
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <sstream>
#include <vector>
#define PI acos(-1.0)
#define N 111111
#define M 1000000007
#define inf 1e9
#define eps 1e-8
#define dazhi 2147483647
using namespace std; typedef unsigned long long ll; ll pow(ll a,ll b,ll p){ll sum=;for(a%=p;b;a=a*a%p,b>>=)if(b&)sum=sum*a%p;return sum;}
ll phi(ll n){ll i,re=n;for(i=;i*i<=n;i++)if(n%i==){re=re/i*(i-);while(n%i==)n/=i;}if(n>)re=re/n*(n-);return re%M;}
void exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=;y=;return;}exgcd(b,a%b,y,x);y-=x*(a/b);}
ll gcd(ll a,ll b){return b==?a:gcd(b,a%b);} /****************************************/ ll b[N];
int main()
{
//ll x,y,t=0;
int n,x,y,t=;
while(scanf("%d%d%d",&n,&x,&y)!=EOF){
t++;
if(n==&&x==&&y==)break;
for(int i=;i<=n;i++){
scanf("%lld",&b[i]);
}
for(int i=;i<n;i++)
scanf("%lld",&b[n+n-i]);
if(x==)y=*n-y+;
ll xiao=1e14,biao;
for(int i=y;i<=*n;i++){
//xiao=min(xiao,b[i]);
if(b[i]<xiao)xiao=b[i],biao=i;
}
for(int i=;i<y;i++){
if(b[i]<xiao)xiao=b[i],biao=i;
}
ll ans=;
if(biao<y){
for(int i=;i<=*n;i++)
b[i]-=xiao+,ans+=xiao+;
for(int i=biao;i<y;i++)
b[i]++,ans--;
}
else{
for(int i=;i<=*n;i++)
b[i]-=xiao,ans+=xiao;
for(int i=y;i<biao;i++)
b[i]--,ans++;
}
b[biao]=ans;
printf("Case %d:\n",t);
if(biao<=n){
printf("INVALID\n");
continue;
}
for(int i=;i<=n;i++){
printf("%lld ",b[i]);
}
cout<<endl;
for(int i=;i<n;i++)
{
printf("%lld ",b[n+n-i]);
}
cout<<endl;
}
}
J
#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <string>
#include <complex>
using namespace std;
typedef pair<int,int> Pii;
typedef long long LL;
typedef unsigned long long ULL;
typedef double DBL;
typedef long double LDBL;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define SQR(a) ((a)*(a))
#define PCUT puts("\n----------") const int maxn=+;
const DBL eps=1e-;
int sgn(DBL x){return x>eps? : (x<-eps? -: );}
struct Vector
{
DBL x,y;
Vector(DBL _x=, DBL _y=):x(_x),y(_y){}
Vector operator + (const Vector &rhs) const {return Vector(x+rhs.x, y+rhs.y);}
Vector operator - (const Vector &rhs) const {return Vector(x-rhs.x, y-rhs.y);}
Vector operator * (const DBL &rhs) const {return Vector(x*rhs, y*rhs);}
Vector operator / (const DBL &rhs) const {return Vector(x/rhs, y/rhs);}
DBL operator * (const Vector &rhs) const {return x*rhs.x + y*rhs.y;}
DBL operator ^ (const Vector &rhs) const {return x*rhs.y - rhs.x*y;}
int read(){return scanf("%lf%lf", &x, &y);}
};
typedef Vector Point; struct Line
{
Point u,v;
Line(){}
Line(Point _u,Point _v):u(_u),v(_v){}
};
int N,M;
Point A[maxn], B[maxn];
DBL Area(int,Point*);
DBL CPIA(Point*,Point*,int,int);
DBL SPIA(Point*,Point*,int,int); int main()
{
int t;
scanf("%d",&t);
for(int p=;p<=t;p++){
scanf("%d%d", &N, &M);
for(int i=; i<N; i++) A[i].read();;
for(int i=; i<M; i++) B[i].read();
printf("%.4f\n",SPIA(A,B,N,M));
}
return ;
} DBL Area(int siz, Point p[])
{
DBL res=;
for(int i=; i<siz; i++) res += (p[i-]^p[i]);
res += (p[siz-]^p[]);
return abs(res*0.5);
} Point GetLineIntSec(Line l1, Line l2)
{
DBL a = (l1.v-l1.u)^(l2.u-l1.u), b = (l1.u-l1.v)^(l2.v-l1.v);
if(sgn(a+b)==) return Point(1e9,1e9);
return Point((l2.u.x * b + l2.v.x * a) / (a + b), (l2.u.y * b + l2.v.y * a) / (a + b));
} DBL CPIA(Point a[], Point b[], int na, int nb)
{
Point p[], tmp[]; // na,nb <=20
int i, j, tn, sflag, eflag;
a[na] = a[], b[nb] = b[];
memcpy(p,b,sizeof(Point)*(nb + ));
for(i = ; i < na && nb > ; i++)
{
sflag = sgn((a[i+]-a[i])^(p[]-a[i]));
for(j = tn = ; j < nb; j++, sflag = eflag)
{
if(sflag>=) tmp[tn++] = p[j];
eflag = sgn( (a[i + ]-a[i])^(p[j + ]-a[i]));
if((sflag ^ eflag) == -)
tmp[tn++] = GetLineIntSec( Line(a[i], a[i + ]) , Line(p[j], p[j + ]));
}
memcpy(p, tmp, sizeof(Point) * tn);
nb = tn, p[nb] = p[];
}
if(nb < ) return 0.0;
return Area(nb, p);
} DBL SPIA(Point a[], Point b[], int na, int nb)
{
int i, j;
Point t1[], t2[];
double res = , num1, num2;
a[na] = t1[] = a[], b[nb] = t2[] = b[];
for(i = ; i < na; i++)
{
t1[] = a[i-], t1[] = a[i];
num1 = sgn( (t1[]-t1[])^(t1[]-t1[]));
if(num1 < ) swap(t1[], t1[]);
for(j = ; j < nb; j++)
{
t2[] = b[j - ], t2[] = b[j];
num2 = sgn((t2[]-t2[])^(t2[]-t2[]));
if(num2 < ) swap(t2[], t2[]);
res += CPIA(t1, t2, , ) * num1 * num2;
}
}
return res;
}