题目I:巧妙的分解

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 0 总提交人数: 0
Special Judge

原比赛ID为:376。建议做题之前查看比赛简介,和比赛的前两条公告。以上包含的问题概不回答。

题目描述

对于连续正整数序列1到n,现在你需要把他们分成两部分。设两部分的和分别是sum1和sum2,你需要保证gcd(sum1,sum2)>1(其中gcd表示两个数的最大公因数)。如果找不到这样的分解,请输出”impossible!”。

输入

包括一行,一个整数n。

输出

如果找不到这样的分解,请输出”impossible!”(无引号),占一行。

如果你找到了这样的分解,请在第一行输出”YES”(无引号),之后的两行表示一个可以的方案:第一行第一个数a,表示第一个集合一共有多少个数,后面有a个数表示每个数;第二行一个数b,表示第二个集合一共有多少个数,后面有b个数表示每个数。

对于多个正确答案,你只需要输出任意一个。

输入样例1

3

输出样例1

YES
1 2
2 1 3

输入样例2

4

输出样例2

YES
2 1 3
2 2 4

样例解释

对于样例1,sum1=2,sum2=4,它们满足gcd(2,4)>1。

对于样例2,sum1=4,sum2=6,它们满足gcd(4,6)>1。同样你也可以把它们分解为(2)和(134),也就是说输出:

YES
1 2
3 1 3 4 

也被视为正确的。

数据范围

保证2≤n≤100000。

相关推荐