CF286E.Ladies' Shop

省选/NOI-

通过率:0%

时间限制:8.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

A ladies' shop has recently opened in the city of Ultima Thule. To get ready for the opening, the shop bought n bags. Each bag is characterised by the total weight a__i of the items you can put there. The weird thing is, you cannot use these bags to put a set of items with the total weight strictly less than a__i. However the weights of the items that will be sold in the shop haven't yet been defined. That's what you should determine right now.

Your task is to find the set of the items' weights _p_1, _p_2, ..., p__k (1 ≤ _p_1 < _p_2 < ... < p__k), such that:

  1. Any bag will be used. That is, for any i (1 ≤ i ≤ n) there will be such set of items that their total weight will equal a__i. We assume that there is the infinite number of items of any weight. You can put multiple items of the same weight in one bag.
  2. For any set of items that have total weight less than or equal to m, there is a bag into which you can put this set. Similarly, a set of items can contain multiple items of the same weight.
  3. Of all sets of the items' weights that satisfy points 1 and 2, find the set with the minimum number of weights. In other words, value k should be as small as possible.

Find and print the required set.

一座女士精品店最近在乌尔蒂玛·图勒城开业。为迎接开业,该店购入了 nn 个包。每个包由其可容纳物品的总重量 aia_i 刻画。奇怪的是,你不能用这些包来装总重量严格小于 aia_i 的物品集合。然而,该店即将销售的物品的重量尚未确定——这正是你现在需要确定的内容。

你的任务是找出一组物品重量 p1, p2, …, pkp_1,\,p_2,\,\dots,\,p_k(满足 1≤p1<p2<⋯<pk1 \le p_1 < p_2 < \dots < p_k),使得:

  1. 每个包都会被使用:即对任意 ii(1≤i≤n1 \le i \le n),均存在某个物品集合,其总重量恰好等于 aia_i。我们假定每种重量的物品均有无限多个;同一包中可放入多个相同重量的物品。
  2. 对任意总重量不超过 mm 的物品集合,均存在一个包可以装下它。同样地,该物品集合中也可包含多个相同重量的物品。
  3. 在所有满足条件 1 和 2 的物品重量集合中,找出重量种类数最少的那个集合。换言之,使 kk 尽可能小。

请找出并输出所要求的集合。

输入格式

The first line contains space-separated integers n and m (1 ≤ n, m ≤ 106). The second line contains n distinct space-separated integers _a_1, _a_2, ..., a__n (1 ≤ _a_1 < _a_2 < ... < a__n ≤ m) — the bags' weight limits.

第一行包含两个用空格分隔的整数 nn 和 mm(1 ≤ n, m ≤ 1061 ≤ n, m ≤ 10^6)。第二行包含 nn 个互不相同的、用空格分隔的整数 a1, a2, ..., ana_1, a_2, ..., a_n(1 ≤ a1 < a2 < ... < an ≤ m1 ≤ a_1 < a_2 < ... < a_n ≤ m)—— 各背包的重量限制。

输出格式

In the first line print "NO" (without the quotes) if there isn't set p__i, that would meet the conditions.

Otherwise, in the first line print "YES" (without the quotes), in the second line print an integer k (showing how many numbers are in the suitable set with the minimum number of weights), in the third line print k space-separated integers _p_1, _p_2, ..., p__k (1 ≤ _p_1 < _p_2 < ... < p__k). If there are multiple solutions, print any of them.

如果不存在满足条件的集合 {pi}\{p_i\},则在第一行输出 “NO”(不带引号)。

否则,在第一行输出 “YES”(不带引号),在第二行输出一个整数 kk(表示满足条件且权重个数最少的集合中元素的个数),在第三行输出 kk 个以空格分隔的整数 p1, p2, …, pkp_1,\,p_2,\,\dots,\,p_k(满足 1≤p1<p2<⋯<pk1\le p_1<p_2<\dots<p_k)。若存在多个解,输出任意一个即可。

输入输出样例

  • 输入#1

    6 10
    5 6 7 8 9 10

    输出#1

    YES
    5
    5 6 7 8 9
  • 输入#2

    1 10
    1

    输出#2

    NO
  • 输入#3

    1 10
    6

    输出#3

    YES
    1
    6

输入解题思路,AI测评打分。不知道怎么写?

首页