Codeforces Round #412 Div 2 题解

比赛链接:http://codeforces.com/contest/807

A Is it rated?

题意

给定多个比赛参与者比赛前后的积分,判断这场比赛有没有rated,对rated的定义:至少一个选手的积分发生变化,unrated定义:积分没有变化但是排名发生变化;maybe定义:分数没有变化,排名没变(非递增)

题解

首先判断积分是否发生变化,然后判断是否非递减

代码

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
void solve()
{
int a[maxn],b[maxn];
int t;
while(cin>>t)
{
bool flag=1;
for(int i=0;i<t;i++)
cin>>a[i]>>b[i];
for(int i=0;i<t;i++)
{
if(a[i]!=b[i])
{
cout<<"rated"<<endl;
flag=0;
break;
}
}
if(!flag)
continue;
for(int i=0;i<t;i++)
{
if(i>0&&a[i]>a[i-1])
{
cout<<"unrated"<<endl;
flag=0;
break;
}
}
if(flag)
cout<<"maybe"<<endl;
}
}

B T-Shirt Hunt

题意

给出一个选手这场比赛的排名和当前成绩和这场比赛可能的最差成绩,同时给出一个程序:
i := (s div 50) mod 475
repeat 25 times:
i := (i * 96 + 42) mod 475
print (26 + i)
程序输入一个积分,有25个输出每个输入表示可能的排名,问经过hacks以后达到能够输出当前排名的积分所需要进行成功的hacks次数是多少?

题解

读懂题目这道题非常水,只要以50为单位不断在原来的基础进行加减直到达到符合要求的值,最后输出需要成功的hacks次数就行了

代码

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
bool fun(int s,int p)
{
int i=(s/50)%475;
for(int j=0;j<25;j++)
{
i=(i*96+42)%475;
if(26+i==p)
return true;
}
return false;
}
void solve()
{
int p,x,y;
while(cin>>p>>x>>y)
{
if(fun(x,p))
{
//cout<<x<<endl;
cout<<"0"<<endl;
continue;
}
bool flag=1;
int tmp=x-50;
while(tmp>=y)
{
if(fun(tmp,p))
{
//cout<<tmp<<endl;
cout<<"0"<<endl;
flag=0;
break;
}
tmp-=50;
}
if(!flag)
continue;
tmp=x+50;
while(tmp)
{
if(fun(tmp,p))
{
//cout<<tmp<<endl;
int ans=(tmp-x)/100;
if((tmp-x)%100!=0) ans++;
cout<<ans<<endl;
break;
}
tmp+=50;
}
}
}

C Success Rate

题意

给出两个分数:x/y p/q,定义两种操作:分子分母同时加上1;分母加上1。问要将前面的分数变成后面的分数要进行的操作数

题解

前面的分数操作到后面的分数y是一定会变成q的倍数的,这样就相当于选择最小的倍数,写一个判断当前倍数是否符合条件的函数,然后再用二分法跑一边就行了,注意特判!

代码

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
bool judg(ll x,ll y,ll p,ll q,ll rate)
{
if(rate*p>=x && rate*q-y>=rate*p-x)
return true;
else
return false;
}
int fun(ll x,ll y,ll p,ll q,ll l,ll r)
{
if(l==r) return r;
if(r==l+1)
{
if(judg(x,y,p,q,l)) return l;
else if(judg(x,y,p,q,r)) return r;
else return -1;
}
//cout<<l<<" "<<r<<endl;
ll rate=y/q;
ll m=(l+r)>>1;
if(judg(x,y,p,q,m)) return fun(x,y,p,q,l,m);
else return fun(x,y,p,q,m,r);
}
void solve()
{
int t;
while(cin>>t)
{
ll x,y,p,q;
for(int id=0;id<t;id++)
{
cin>>x>>y>>p>>q;
if(x*q==p*y)
{
cout<<"0"<<endl;
continue;
}
if(p==q || (p==0 && x!=0))
{
cout<<"-1"<<endl;
continue;
}
ll rate=fun(x,y,p,q,y/q,1e18/q);
if(rate==-1)
{
cout<<"-1"<<endl;
continue;
}
cout<<rate*q-y<<endl;
}
}
}