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

A. Arpa and a research in Mexican wave

B. Arpa and an exam about geometry

C. Five Dimensional Points

D. Arpa and a list of numbers

E. Arpa and a game with Mojtaba

A. Arpa and a research in Mexican wave

代码如下:

1
2
3
4
5
6
7
8
#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|$ 这两条弦相等。最后只需要判断一下这三个点是否能确定圆(是否在同一条直线)即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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$ ,所以只需要暴力一下就好。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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)$ 。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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函数值,异或下即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#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");
}