@[toc]
补题链接：https://codeforces.com/gym/102992
https://ac.nowcoder.com/acm/contest/10272
K. Co-prime Permutation
K. K Co-prime Permutation
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Kotori is very good at math (really?) and she loves playing with permutations and primes.
One day, she thinks of a special kind of permutation named k co-prime permutation. A permutation p1,p2,⋯,pn of n is called a k co-prime permutation of n if there exists exactly k integers i such that 1≤i≤n and gcd(pi,i)=1, where gcd(x,y) indicates the greatest common divisor of x and y.
Given n and k, please help Kotori construct a k co-prime permutation of n or just report that there is no such permutation.
Recall that a permutation of n is a sequence of length n containing all integers from 1 to n.
Input
There is only one test case in each test file.
The first and only line contains two integers n and k (1≤n≤106, 0≤k≤n).
Output
Output one line containing n integers p1,p2,⋯,pn separated by one space, indicating the permutation satisfying the given constraints. If no such permutation exists output "-1" (without quotes) instead. If there are multiple valid answers you can print any of them.
Please, DO NOT output extra spaces at the end of each line, otherwise your answer may be considered incorrect!
Examples
inputCopy
5 3
outputCopy
1 4 5 2 3
inputCopy
1 0
outputCopy
-1
题意：
- 给出n和k，求n的一个排列P，满足其中有k个gcd(i,Pi)==1.
思路：
- 已知gcd(x,x+1)=1，gcd(1,x)=1, gcd(x,x)=x，，所以直接初始排列移动一下前面k个即可。
#include<bits/stdc++.h>
using namespace std;
vector<int>a(1000005);
int main(){
int n, k; cin>>n>>k;
if(k==0)cout<<"-1";
else{
for(int i = 1; i <= n; i++)a[i]=i;
a.erase(a.begin()+k);
a.insert(a.begin()+1,k);
for(int i = 1; i <= n; i++)
cout<<a[i]<<" ";
}
return 0;
}
L. Let‘s Play Curling
L. Let's Play Curling
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Curling is a sport in which players slide stones on a sheet of ice toward a target area. The team with the nearest stone to the center of the target area wins the game.
Two teams, Red and Blue, are competing on the number axis. After the game there are (n+m) stones remaining on the axis, n of them for the Red team and the other m of them for the Blue. The i-th stone of the Red team is positioned at ai and the i-th stone of the Blue team is positioned at bi.
Let c be the position of the center of the target area. From the description above we know that if there exists some i such that 1≤i≤n and for all 1≤j≤m we have |c−ai|<|c−bj| then Red wins the game. What's more, Red is declared to win p points if the number of i satisfying the constraint is exactly p.
Given the positions of the stones for team Red and Blue, your task is to determine the position c of the center of the target area so that Red wins the game and scores as much as possible. Note that c can be any real number, not necessarily an integer.
Input
There are multiple test cases. The first line of the input contains an integer T indicating the number of test cases. For each test case:
The first line contains two integers n and m (1≤n,m≤105) indicating the number of stones for Red and the number of stones for Blue.
The second line contains n integers a1,a2,⋯,an (1≤ai≤109) indicating the positions of the stones for Red.
The third line contains m integers b1,b2,⋯,bm (1≤bi≤109) indicating the positions of the stones for Blue.
It's guaranteed that neither the sum of n nor the sum of m will exceed 5×105.
Output
For each test case output one line. If there exists some c so that Red wins and scores as much as possible, output one integer indicating the maximum possible score of Red (NOT c). Otherwise output "Impossible" (without quotes) instead.
Example
inputCopy
3
2 2
2 3
1 4
6 5
2 5 3 7 1 7
3 4 3 1 10
1 1
7
7
outputCopy
2
3
Impossible
Note
For the first sample test case we can assign c=2.5 so that the stones at position 2 and 3 for Red will score.
For the second sample test case we can assign c=7 so that the stones at position 5 and 7 for Red will score.
题意：
- 给出n个红石头ai，m个蓝石头bi的所在位置，求确定一个位置C使得存在ai对于所有的bi都满足|c-ai|<|c-bi|，并且让ai数量尽可能多，输出最多的ai数量。
思路：
- 实际上就是求两个蓝石头之间最多有几个红石头。
- 先排个序，枚举蓝石头，每次找到第一个比b[i-1]大的和最后一个比b[i]小的红石头的位置，减一下就是中间的红石头个数，开个ans维护答案。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 200005;
int a[maxn], b[maxn];
int main(){
ios::sync_with_stdio(false);
int T; cin>>T;
while(T--){
int n, m; cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>b[i];
sort(a+1,a+n+1);
sort(b+1,b+m+1);
b[0]=-1e9; b[m+1] = 2e9;
LL ans = -1;
for(int i=1;i<=m+1;i++){
int l=upper_bound(a+1,a+n+1,b[i-1])-a;
int r=lower_bound(a+1,a+n+1,b[i])-a-1;
ans = max(ans,LL(r-l+1));
}
if(ans<=0)cout<<"Impossible\n";
else cout<<ans<<"\n";
}
return 0;
}
E. Evil Coordinate
E. Evil Coordinate
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
A robot is standing on an infinite 2-dimensional plane. Programmed with a string s1s2⋯sn of length n, where si∈{'U','D','L','R'}, the robot will start moving from (0,0) and will follow the instructions represented by the characters in the string.
More formally, let (x,y) be the current coordinate of the robot. Starting from (0,0), the robot repeats the following procedure n times. During the i-th time:
If si='U' the robot moves from (x,y) to (x,y+1);
If si='D' the robot moves from (x,y) to (x,y−1);
If si='L' the robot moves from (x,y) to (x−1,y);
If si='R' the robot moves from (x,y) to (x+1,y).
However, there is a mine buried under the coordinate (mx,my). If the robot steps onto (mx,my) during its movement, it will be blown up into pieces. Poor robot!
Your task is to rearrange the characters in the string in any order, so that the robot will not step onto (mx,my).
Input
There are multiple test cases. The first line of the input contains an integer T indicating the number of test cases. For each test case:
The first line contains two integers mx and my (−109≤mx,my≤109) indicating the coordinate of the mine.
The second line contains a string s1s2⋯sn of length n (1≤n≤105, si∈{'U','D','L','R'}) indicating the string programmed into the robot.
It's guaranteed that the sum of n of all test cases will not exceed 106.
Output
For each test case output one line. If a valid answer exists print the rearranged string, otherwise print "Impossible" (without quotes) instead. If there are multiple valid answers you can print any of them.
Example
inputCopy
5
1 1
RURULLD
0 5
UUU
0 3
UUU
0 2
UUU
0 0
UUU
outputCopy
LDLRUUR
UUU
Impossible
Impossible
Impossible
题意：
- 给出一个字符串，UDLR分别表示向上下左右移动。默认在坐标原点(0,0)，求更改字符顺序，让其移动不经过题目地雷点(mx,my)。
思路：
- 可以证明存在一种答案，使得相同的方向是连续排在一起的，即枚举UDLR的24种排列即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const char a[]="UDLR";//用0123对应ULDR，a是字符，c是数量，q是排列。
const int dx[]={
0,0,-1,1},dy[]={
1,-1,0,0};
int main(){
//ios::sync_with_stdio(false); WA
int T; cin>>T;
while(T--){
int mx, my; cin>>mx>>my;
string s; cin>>s;
int c[4] = {
};
for(int i=0;i<s.size();i++){
if(s[i]=='U')c[0]++;
if(s[i]=='D')c[1]++;
if(s[i]=='L')c[2]++;
if(s[i]=='R')c[3]++;
}
//for(int i =0; i<4;i++)cout<<c[i]<<"\n";
//起点或终点重合
int tx=c[3]-c[2],ty=c[0]-c[1];
if(tx==mx&&ty==my || mx==0&&my==0){
cout<<"Impossible\n";
continue;
}
int q[4]={
0,1,2,3}, ook=0;
do{
int x=0,y=0,ok=1;
for(int i=0; i<=3; i++){
//方向
for(int j=0;j<c[q[i]];j++){
//移动(方向q[i]有长度c[q[i]])
x += dx[q[i]], y+=dy[q[i]];
if(x==mx&&y==my){
ok=0; break;
}
}
if(ok==0)break;
}
if(ok==1){
//没有雷就全方向输出
for(int i=0; i<=3; i++)
for(int j=0; j<c[q[i]];j++)
putchar(a[q[i]]);
cout<<"\n";
ook=1;
break;
}
}while(next_permutation(q,q+4));
if(ook)continue;
cout<<"Impossible\n";
}
return 0;
}
F. Fireworks
Fireworks
Input file: standard input
Output file: standard output
Time limit: 1 second
Memory limit: 256 megabytes
Kotori is practicing making fireworks for the upcoming hanabi taikai1
. It takes her n minutes to make a
single firework, and as she is not really proficient in making fireworks, each firework only has a probability
of p × 10−4
to be perfect.
After she finishes making a firework, she can just start making the next firework, or take m minutes to
light all the remaining fireworks finished before. If there is at least one perfect firework among the lit ones,
she will be happy and go to rest. Otherwise, she will continue practicing. Can you tell her the minimum
expected practicing time before she goes to rest if she takes the optimal strategy?
Notice that no matter how many fireworks remain, it always takes m minutes to light them all.
Input
There are multiple test cases. The first line of the input contains an integer T (1 ≤ T ≤ 104
) indicating
the number of test cases. For each test case:
The first and only line contains three integers n, m and p (1 ≤ n, m ≤ 109
, 1 ≤ p ≤ 104
).
Output
For each test case, output one line containing one number indicating the minimum expected practicing
time.
Your answer will be considered correct if and only if the absolute or relative error does not exceed 10−4
.
Example
standard input standard output
3
1 1 5000
1 1 1
1 2 10000
4.0000000000
10141.5852891136
3.0000000000
题意：
- 制作一个烟花需要n分钟，成功的概率为p。完成一次制作后可以继续制作或花m分钟点燃之前所有的烟花，如果有一个烟花是成功的，那么就可以开始休息。
- 求最小的期望开始休息时间（即期望的最早成功制作一个烟花的时间）
思路：
- 因为每次都是做出来一批集中释放做好的看看有没有成功的，所以不妨设最优策略为每次做k个能最早休息。所以问题转化为每次制作k个释放，期望的最早制作成功的时间。
- 每轮制作耗费时间kn+m，至少一个烟花制作成功的概率为$(1-(1-p)^k)$，所以根据几何分布公式可以得到期望为$\frac{kn+m}{1-(1-p)^k}$。
- 对该式子打表或者求二阶导可以发现这是个单峰的凹函数。可以三分答案。
#include<bits/stdc++.h>
using namespace std;
typedef long double LD;
LD fun(int k, int n, int m, LD p){
return ((LD)k*n+m)/((LD)1.0-pow(1.0-p,k));
}
int main(){
int T; cin>>T;
while(T--){
int n, m; LD p;
cin>>n>>m>>p;
p *= (1e-4);
int l = 1, r = 1e9+10;
while(l < r){
int mid1 = l+(r-l)/3, mid2 = r-(r-l)/3;
if(fun(mid1,n,m,p)<fun(mid2,n,m,p))r = mid2-1;
else l = mid1+1;
}
printf("%.10Lf\n", fun(l,n,m,p));
}
return 0;
}
