Codeforces Round 432 (Div. 2, based on IndiaHacks Final Round 2017)

A. Arpa and a research in Mexican wave

代码如下：

#include <iostream>
using namespace std;
int main(void){
    int n,k,t;
    cin>>n>>k>>t;
    int d=t-k;
    cout<<min(t,n)-max(0,d);
}

B. Arpa and an exam about geometry

题目大意：给出a,b,c三个点，问是否存在一个点和一个角度，使得这三个点绕该点旋转这个角度后，满足a在b原先的位置，b在c原先的位置。

几何题

显然，若点存在则必然是由a,b,c这三个点确定的圆的圆心。因为$\widehat{aob}$ 和$\widehat{boc}$ 两个圆心角相等，故$|ab|$ 和$|bc|$ 这两条弦相等。最后只需要判断一下这三个点是否能确定圆（是否在同一条直线）即可。

代码如下：

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
ll ax,ay,bx,by,cx,cy;
int main(void){
    cin>>ax>>ay>>bx>>by>>cx>>cy;
    if((ax-bx)*(ax-bx)+(ay-by)*(ay-by)==(cx-bx)*(cx-bx)+(cy-by)*(cy-by)){
        if((ay-by)*(bx-cx)==(by-cy)*(ax-bx))cout<<"No";
        else cout<<"Yes";
        return 0;
    }
    cout<<"No";
}

C. Five Dimensional Points

题目大意：给出五维空间的$n$ 个点，问对于每个点$O$ 是否存在两个不同的点$A,B$ ，使得$\angle AOB <90^\circ$ 。

思维题

对于一个$k$ 维空间，最多有$2k$ 个点满足$\angle AOB \geqslant 90^\circ$ ，所以只需要暴力一下就好。

代码如下：

#include <cstdio>
using namespace std;
const int N=1005;
int a[N],b[N],c[N],d[N],e[N];
int ans[N],tot,n;
namespace IO {
    const int MX = 1e7;
    char buf[MX]; int c, sz;
    void begin() {
        c = 0;
        sz = fread(buf, 1, MX, stdin);
    }
    inline bool read(int &t) {
        while(c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++;
        if(c >= sz) return false;
        bool flag = 0; if(buf[c] == '-') flag = 1, c++;
        for(t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0';
        if(flag) t = -t;
        return true;
    }
}
int main(void){
    IO::begin();
    IO::read(n);
    for(int i=0;i<n;++i)
        IO::read(a[i]),IO::read(b[i]),IO::read(c[i]),IO::read(d[i]),IO::read(e[i]);
    for(int i=0;i<n;++i){
        bool flag=1;
        int temp=a[i]*a[i]+b[i]*b[i]+c[i]*c[i]+d[i]*d[i]+e[i]*e[i];
        for(int j=0;j<n;++j)if(i-j){
            for(int k=j+1;k<n;++k)if(i-k&&j-k){
                if(a[j]*a[k]+b[j]*b[k]+c[j]*c[k]+d[j]*d[k]+e[j]*e[k]+temp
                   -a[i]*(a[j]+a[k])-b[i]*(b[j]+b[k])-c[i]*(c[j]+c[k])
                   -d[i]*(d[j]+d[k])-e[i]*(e[j]+e[k])>0){
                    flag=0;
                    break;
                }
            }
            if(!flag)break;
        }
        if(flag)ans[tot++]=i+1;
    }
    printf("%d\n",tot);
    for(int i=0;i<tot;++i)
        printf("%d ",ans[i]);
}

D. Arpa and a list of numbers

题目大意：给定$n$ 个数，问进行下面两种操作后，最少花费多少能使这$n$ 个数的最大公约数不为$1$ 。

选择一个数删除，花费$x$

选择一个数加$1$ ，花费$y$

调和级数

枚举操作完后的最大公约数$d$ ，显然$[kd+1,(k+1)d-1]$ 的数$a$ 只有两种操作情况：

删除，花费$x$
加至$(k+1)d$ ，花费$[(k+1)d-a]y$

因此，我们可以枚举$k$ ，一段一段地考虑。

而当$a \geqslant (k+1)d- \lfloor \frac{x}{y} \rfloor $ 时，将$a$ 加至$(k+1)d$ 比删除$a$ 花费的代价小。

于是我们维护每个区间数的个数，以及每个区间数的和，就可以以$O(1)$ 的复杂度处理每一段的代价。

复杂度$O(nlogn)$ 。

这里其实可以继续优化，显然对于最大公约数我们只需要枚举所有质数，预处理质数后，复杂度为$O(nloglogn)$ 。

代码如下：

#include <cstdio>
using namespace std;
typedef long long ll;
const int N=500000+5;
const int M=2000000+5;
ll n,x,y,t,cnt[M],sum[M];
ll Max(ll a,ll b){return a>b?a:b;}
int main(void){
    scanf("%I64d%I64d%I64d",&n,&x,&y);
    for(int i=0;i<n;++i){
        scanf("%I64d",&t);
        cnt[t]++;
        sum[t]+=t;
    }
    for(int i=1;i<M;++i){
        cnt[i]+=cnt[i-1];
        sum[i]+=sum[i-1];
    }
    ll ans=1e17;
    for(ll i=2;i<=1000000;++i){
        ll temp=0,k=x/y;
        for(ll j=0;j<=1000000;j+=i){
            temp+=((cnt[j+i-1]-cnt[Max(j,j+i-k-1)])*(j+i)-(sum[j+i-1]-sum[Max(j,j+i-k-1)]))*y+(cnt[Max(j,j+i-k-1)]-cnt[j])*x;
        }
        if(ans>temp)ans=temp;
    }
    printf("%I64d\n",ans);
}

E. Arpa and a game with Mojtaba

题目大意：给定$n$ 个数，两人轮流从中改数。每轮选定一个素数$p$ 和正整数$k$ ，将所有能被$p^k$ 整除的数除$p^k$ 。当无法操作时为输。

博弈

显然不同的素数间是互相独立的，故只需要暴力求出对于单个素数的SG函数值，异或下即可。

代码如下：

#include <cstdio>
#include <map>
using namespace std;
typedef long long ll;
const int N=100+5;
ll p[100005],vis[100005],k;
ll n,a[N],maxn,ans;
map<ll,ll>mp;
void init(ll n){
    for(ll i=2;i<n;++i){
        if(!vis[i])p[k++]=i;
        for(ll j=0;j<k&&p[j]*i<n;++j){
            vis[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
}
ll Max(ll a,ll b){
    return a>b?a:b;
}
ll solve(ll s){
    if(s==1)return 0;
    if(mp.count(s))return mp[s];
    ll tmp=0,sg=0;
    for(int i=0;i<30;++i){
        tmp|=((s>>i)&1)<<i;
        if((s>>(i+1))==0)break;
        sg|=(1LL<<solve(tmp|(s>>(i+1))));
    }
    ll ans=0;
    for(;ans<30;++ans)
        if(((sg>>ans)&1)==0)
            break;
    return mp[s]=ans;
}
int main(void){
    init(100005);
    scanf("%I64d",&n);
    for(int i=0;i<n;++i){
        scanf("%I64d",&a[i]);
        maxn=Max(maxn,a[i]);
    }
    for(int i=0;i<k&&p[i]*p[i]<=maxn;++i){
        ll s=0;
        for(int j=0;j<n;++j){
            ll cnt=0;
            while(a[j]%p[i]==0){
                a[j]/=p[i];
                cnt++;
            }
            s|=(1LL<<cnt);
        }
        ans^=solve(s);
    }
    for(int i=0;i<n;++i)if(a[i]!=1){
        for(int j=i+1;j<n;++j)if(a[j]==a[i])a[j]=1;
        a[i]=1;
        ans^=solve(2);
    }
    if(ans)printf("Mojtaba\n");
    else printf("Arpa\n");
}