Codeforces Round #240 (Div. 2) C Mashmokh and Numbers
Mashmokh and Numbers
It's holiday. Mashmokh and his boss, Bimokh, are playing a game invented by Mashmokh.
In this game Mashmokh writes sequence of n distinct integers on the board. Then Bimokh makes several (possibly zero) moves. On the first move he removes the first and the second integer from from the board, on the second move he removes the first and the second integer of the remaining sequence from the board, and so on. Bimokh stops when the board contains less than two numbers. When Bimokh removes numbers x and yfrom the board, he gets gcd(x, y) points. At the beginning of the game Bimokh has zero points.
Mashmokh wants to win in the game. For this reason he wants his boss to get exactly k points in total. But the guy doesn't know how choose the initial sequence in the right way.
Please, help him. Find n distinct integers a1, a2, ..., an such that his boss will score exactly k points. Also Mashmokh can't memorize too huge numbers. Therefore each of these integers must be at most 109.
The first line of input contains two space-separated integers n, k (1 ≤ n ≤ 105; 0 ≤ k ≤ 108).
If such sequence doesn't exist output -1 otherwise output n distinct space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109).
5 2
1 2 3 4 5
5 3
2 4 3 7 1
7 2
-1
题意:找出一组数列,满足每相邻的两个数的最大公因数和为给定的值。
sl:无以言状的水题,最终挂了,为什么呢,我把最后一个数字写的太小了。在知道直接0走起。
相邻两个数字互素。利用这点很容易求出答案。
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<queue>
5 using namespace std;
6 typedef long long LL;
7 const int MAX = ;
8 int main()
9 {
int n,k;
while(scanf("%d %d",&n,&k)==)
{
if(n==&&k!=) printf("-1\n");
else if(n==&&k==) printf("1\n");
else if(n/>k) printf("-1\n");
else
{
int a=,b=;
int t=n/; t*=; int x=n/;
int last=k-(x-);
for(int i=;i<x;i++)
{
if(a!=last&&b!=last&&a!=*last&&b!=*last)
{
if(i==) printf("%d %d",a,b),a+=, b+=;
else printf(" %d %d",a,b),a+=, b+=;
}
else
{
while(a==last||b==last||a==*last||b==*last)
a+=, b+=;
if(i==) printf("%d %d",a,b),a+=, b+=;
else printf(" %d %d",a,b),a+=, b+=;
}
}
if(x!=&&last!=) printf(" %d %d",*last,last);
else if(last!=&&x==) printf("%d %d",*last,last);
else if(x!=&&last==) printf(" 99999997 99999998");
else if(last==&&x==) printf("99999997 99999998");
if(n%) printf(" 1000000000");
printf("\n");
}
}
return ;
}
最新文章
- 利用WCF的双工通讯实现一个简单的心跳监控系统
- WebView的使用及添加进度条
- Wifi-Direct
- Canopy v. 1.5.5 ubuntu安装流程
- can&#39;t find which disk is full
- 在Eclipse/MyEclipse中安装spket插件
- PHP检测文件能否下载
- 使用C语言和Java分别实现冒泡排序和选择排序
- netty源码分析
- PGM:有向图模型:贝叶斯网络
- Vim使用技巧:常用光标跳转命令
- Linux 下编程
- Ubuntu、CenOS、Debian等不同版本简单概念与不同
- 6. CountDownLatch 闭锁
- CF 670C Cinema(算竞进阶习题)
- 【托业】新托业全真题库---TEST1
- day16 Python map函数
- rsync+inotify磁盘数据实时同步
- Alpha 冲刺 (6/10
- 怎样删除windows.old文件