锐客网

  1. 首页 > it技术 > >

刷题|C - Game With Array CodeForces - 1355D

codeforces刷题

传送

Petya and Vasya are competing with each other in a new interesting game as they always do.
【刷题|C - Game With Array CodeForces - 1355D】At the beginning of the game Petya has to come up with an array of NN positive integers. Sum of all elements in his array should be equal to SS. Then Petya has to select an integer KK such that 0≤K≤S0≤K≤S.
In order to win, Vasya has to find a non-empty subarray in Petya's array such that the sum of all selected elements equals to either KK or S?KS?K. Otherwise Vasya loses.
You are given integers NN and SS. You should determine if Petya can win, considering Vasya plays optimally. If Petya can win, help him to do that.
Input
The first line contains two integers NN and SS (1≤N≤S≤1061≤N≤S≤106) — the required length of the array and the required sum of its elements.
Output
If Petya can win, print "YES" (without quotes) in the first line. Then print Petya's array in the second line. The array should contain NN positive integers with sum equal to SS. In the third line print KK. If there are many correct answers, you can print any of them.
If Petya can't win, print "NO" (without quotes).
You can print each letter in any register (lowercase or uppercase).
Examples
Input

1 4

Output
YES 4 2

Input
3 4

Output
NO

Input
3 8

Output
YES 2 1 5 4

题意：哇这题可以说是表达的非常非常绕了，反正我是同学帮我解释题意的。让你构造一个有n个元素的数组，并且这些元素和等于s。问能不能找到一个整数值k（1≤k≤s），使得构造数组任何的子序列之和不等于k或s-k。直接看样例一吧：n=1,s=4，那么只能构造一个单个元素为4的数组，那么他的子序列只有4咯，那么我们能得到的子序列之和就只有4。所以k=1，k=2，k=3都符合题意。再看样例二：n=3,s=4。那么只能构造一个1，1，2的数组，能 得到的子序列之和有1，2，3，4和（s-子序列之和）3，2，1，0.也就是说1-4之间没有能符合条件的k值。
题解：通过样例一很明显能得到数值k，是有一个区间的，并且当元素个数增加的时候，数组构造的不同，k值也不同。那么对于这种情况，直接构造极端的数组（初中数学老师教的特殊值法深得我心）。令n个元素的数组中前n-1个元素全为1，最后一个为s-(n-1)即s-n+1.那我们就可以得到k值的一个开区间（n-1，s-n+1），因为k是整数，我们将这个开区间转换成闭区间[n, s-n]。那么为了使k值存在，必须有n <= s-n，也就是说当2*n > s时，无论如何构造的数组，都找不到符合条件的数值k。然后找k值的时候只要我前面说的，构造极端数组即可，因为符合的k值可能有很多，题目也只要你输出其中一个。（当然我代码里构造的极端数组和我前面说的不太一样，代码里我先确定k值为1，然后令n-1个元素均为2，求最后一个元素即可）。
#include #include using namespace std; int n, s; int main(){ scanf("%d%d", &n, &s); if(2*n > s) printf("NO\n"); else{ printf("YES\n"); for(int i=0; i


    推荐阅读


    上一篇：两行代码搞定导航吸顶（position:sticky）

    下一篇：刷题|D - Count Triangles CodeForces - 1355C