AT_1202Contest_j.Hated Number

普及+/提高

通过率:0%

AC君温馨提醒

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

题目描述

给定正整数 $ X,\ M\ (X\ \leq\ M) $。
你喜欢 $ M $ 及以下的正整数,但是唯独讨厌 $ X $。因此,你决定创建一个满足以下条件的集合 $ S $:

  • $ S $ 由不超过 $ 10^5 $ 的不同的正整数组成。
  • $ S $ 的元素个数不超过 $ 20 $。
  • 对于满足 $ 1\ \leq\ k\ \leq\ M,\ k\ \neq\ X $ 的任意正整数 $ k $,存在 $ S $ 的一个子集,其元素之和为 $ k $。
  • 不存在 $ S $ 的一个子集,其元素之和为 $ X $。

判断是否存在这样的集合 $ S $,如果存在,输出其中一个满足条件集合。
对于每个输入,回答 $ T $ 个测试用例。

输入格式

输入以以下格式给出:

$ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $

每个测试用例以以下格式给出:

$ X\ M $

输出格式

对于每个输入,如果满足条件的集合 $ S $ 不存在,输出 $ -1 $;如果存在,输出一个满足条件的集合 $ S $,并以以下格式输出:

$ N $ $ a_1\ a_2\ \dots\ a_N $

其中, $ N $ 是集合 $ S $ 的元素个数, $ (a_1,\ a_2,\ \dots,\ a_N) $ 是按升序排列的集合 $ S $ 的元素,满足以下约束:

  • $ 1\ \leq\ N\ \leq\ 20 $
  • $ 1\ \leq\ a_1\ \lt\ a_2\ \lt\ \dots\ \lt\ a_N\ \leq\ 10^5 $

对于每个输入,输出之后换行。

约束条件

  • $ 1\ \leq\ T\ \leq\ 100 $
  • $ 1\ \leq\ X\ \le\ M\ \leq\ 10^5 $
  • $ M\ \geq\ 2 $
  • 输入均为整数

Translate by @XYQ_102

输入输出样例

  • 输入#1

    3
    4 6
    3 7
    11 11

    输出#1

    3
    1 2 5
    -1
    4
    1 2 3 4

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

首页