Flip and Adjust

题目描述

有 $N$ 张卡片，每张卡片的两面都写有一个整数。卡片 $i$ $(1 \leq i \leq N)$ 的正面写着整数 $a_i$，背面写着整数 $b_i$。 你可以选择将每张卡片以正面或背面朝外放置。 判定是否存在一种放置方式，使得朝外可见的整数之和恰好等于 $S$。如果可能，找出一种实现该和的放置方式。

输入格式

输入从标准输入给出，格式如下： $N$ $S$ $a_1$ $b_1$ $\vdots$ $a_N$ $b_N$

输出格式

首先，如果可以使朝外可见的整数之和恰好等于 $S$，则输出 $Yes$，否则输出 $No$，并换行。 此外，如果存在这样的放置方式，打印一个由 $H$ 和 $T$ 组成的长度为 $N$ 的字符串来表示实现该和的放置方式。
第 $i$ 个 $(1 \leq i \leq N)$ 字符应为 $H$，如果第 $i$ 张卡片应以正面朝外放置；应为 $T$，如果以背面朝外。
若存在多种可能的放置方式实现该和，打印其中任意一种均被接受。

3 11
1 4
2 3
5 7

Yes
THH

5 25
2 8
9 3
4 11
5 1
12 6

No

提示

$1 \leq N \leq 100$ $1 \leq S \leq 10000$ $1 \leq a_i, b_i \leq 100 \, (1 \leq i \leq N)$ 输入中的所有数值均为整数。例如，下面的放置方式可以使朝外可见的整数之和恰好等于 $S(= 11)$：

将第 1 张卡片以正面朝外放置，第 2 张以背面朝外，第 3 张以背面朝外。 将第 1 张卡片以背面朝外放置，第 2 张以正面朝外，第 3 张以正面朝外。

因此，像 $HTT$ 和 $THH$ 这样的输出是被接受的。
你无法将卡片放置为使朝外可见的整数之和恰好等于 $S(= 25)$。

标签: AtCoder|abc271D

来源

AtCoder|abc271D