QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

#17242. Clothes

Statistics

河狸比太郎打算在服装店购买 $0$ 件或以上的衣服。服装店一共出售 $100$ 种衣服,种类编号为 $1$ 到 $100$。每种衣服库存充足,无论比太郎购买多少件都不会售罄。

通过穿上购买的衣服,比太郎可以调节自己的体感温度。若当天气温为 $t$ 度,比太郎穿着种类为 $s_1, s_2, \ldots, s_k$ 的 $k$ 件衣服,则他的体感温度为 $t + s_1 + s_2 + \cdots + s_k$ 度。

比太郎可以穿 $0$ 件或以上任意数量的衣服(当 $k = 0$ 时,体感温度为 $t$ 度)。此外,他也可以同时穿同一种类的衣服多件,且每多穿一件该种类的衣服,体感温度都会相应增加。

根据天气预报,比太郎得知未来 $N$ 天的气温分别为 $A_1$ 度,$A_2$ 度,$\ldots$,$A_N$ 度。

比太郎希望通过在服装店适当地购买衣服,使得在未来 $N$ 天中的任意一天,都可以通过选择合适的穿法,使体感温度恰好为 $23$ 度。此外,如果存在可行的购买方案,他希望所购买的衣服总数尽可能少。

给定未来 $N$ 天的气温信息,请判断是否存在一种购买方案,使得比太郎在每一天都可以将体感温度调节为 $23$ 度;若存在,请给出一种使购买衣服总数最少的方案。

输入格式

输入从标准输入按如下格式给出:

N
A_1 A_2 \cdots A_N

输出格式

输出到标准输出,格式如下:

  • 若不存在一种购买方案,使得比太郎在每一天都可以将体感温度调节为 $23$ 度,则输出 No
  • 若存在这样的购买方案,则:
    • 第 $1$ 行输出 Yes
    • 设最少需要购买的衣服总数为 $k$,购买的 $k$ 件衣服的种类分别为 $s_1, s_2, \ldots, s_k$。
    • 第 $2$ 行输出整数 $k$。
    • 第 $3$ 行输出 $k$ 个整数 $s_1, s_2, \ldots, s_k$(以空格分隔)。

$s_1, s_2, \ldots, s_k$ 的输出顺序任意。若满足条件的方案有多个,输出其中任意一个即可。

限制

  • $1 \le N \le 81$。
  • $-40 \le A_i \le 40 \ (1 \le i \le N)$。
  • $A_i < A_{i+1} \ (1 \le i \le N-1)$。
  • 输入中的所有值均为整数。

子任务

  1. (6 分)$N = 1$。
  2. (14 分)$N \le 3$。
  3. (15 分)$A_{i+1} = A_i + 1 \ (1 \le i \le N-1)$,且 $A_N = 23$。
  4. (16 分)$A_i \ge 12 \ (1 \le i \le N)$。
  5. (9 分)$A_i \ge 4 \ (1 \le i \le N)$。
  6. (21 分)$A_i \ge -8 \ (1 \le i \le N)$。
  7. (19 分)无额外限制。

样例数据

样例 1

输入

3
17 20 23

输出

Yes
2
3 3

通过购买 2 件种类为 $3$ 的衣服,比太郎可以在未来 3 天的任意一天将体感温度调节为 $23$ 度。具体如下:

  • 第 1 天穿 2 件种类 $3$ 的衣服。
  • 第 2 天穿 1 件种类 $3$ 的衣服。
  • 第 3 天不穿衣服。

若只购买不超过 1 件衣服,则无法保证未来 3 天的体感温度均为 $23$ 度。

该样例满足子任务 2, 4, 5, 6, 7 的限制。

样例 2

输入

1
24

输出

No

当气温为 $24$ 度时,无法将体感温度调节为 $23$ 度。因此,无论如何购买衣服,都无法满足要求。

该样例满足子任务 1, 2, 4, 5, 6, 7 的限制。

样例 3

输入

5
-1 3 6 10 16

输出

Yes
3
4 7 13

该样例满足子任务 6, 7 的限制。

样例 4

输入

3
21 22 23

输出

Yes
2
1 1

该样例满足子任务 2, 3, 4, 5, 6, 7 的限制。

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.