D - Shopping Challenge Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君はショッピングモールで開催されている「ぴったりお買い物チャレンジ」に参加しています。

このチャレンジのルールは次の通りです。会場には N 個の商品が 1 から N まで番号付けられて並んでおり、i 番目 (1 \leq i \leq N) の商品の価格は P_i 円です。高橋君はこれらの商品の中から 1 個以上を選んで購入し、選んだ商品の価格の合計がちょうど目標金額 S 円と一致すれば、チャレンジ成功となります。ただし、同じ商品を 2 回以上選ぶことはできません。

高橋君がチャレンジに臨むにあたって気にしているのは、成功する商品の選び方が何通りあるかです。成功する選び方が 1 通りもなければチャレンジは絶望的です。1 通りしかなければ、その唯一の組み合わせを正確に見つけ出さなければならず不安です。2 通り以上あれば、試行錯誤の余地があるので比較的気楽に挑めそうです。

ここで「選び方」とは、選ばれる商品の集合のことを指します。商品は番号で区別されるため、価格が同じ商品が複数あっても、それらは異なる商品として扱います。選ばれる商品の集合が異なれば、異なる選び方として数えます。

価格の合計がちょうど S 円になるような選び方の総数を C とするとき、C の値に応じて次のように出力してください。

  • C = 0 のとき：NO
  • C = 1 のとき：ALMOST
  • C \geq 2 のとき：YES

制約

  • 1 \leq N \leq 40
  • 1 \leq S \leq 10^{18}
  • 1 \leq P_i \leq 10^{18}
  • 入力はすべて整数

入力

N S
P_1 P_2 \ldots P_N
  • 1 行目には、商品の個数を表す整数 N と、目標金額を表す整数 S が、スペース区切りで与えられる。
  • 2 行目には、各商品の価格を表す N 個の整数 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。

出力

価格の合計がちょうど S 円となる選び方の総数 C に応じて、C = 0 なら NO を、C = 1 なら ALMOST を、C \geq 2 なら YES を 1 行で出力せよ。

入力例 1

4 7
2 3 4 5

出力例 1

YES

入力例 2

3 10
1 2 4

出力例 2

NO

入力例 3

12 50
1 2 4 8 16 32 64 128 256 512 1000 2000

出力例 3

ALMOST

入力例 4

35 1000000000000000000
1000000000000000000 1000000000000000000 600000000000000000 600000000000000001 600000000000000002 600000000000000003 600000000000000004 600000000000000005 600000000000000006 600000000000000007 600000000000000008 600000000000000009 600000000000000010 600000000000000011 600000000000000012 600000000000000013 600000000000000014 600000000000000015 600000000000000016 600000000000000017 600000000000000018 600000000000000019 600000000000000020 600000000000000021 600000000000000022 600000000000000023 600000000000000024 600000000000000025 600000000000000026 600000000000000027 600000000000000028 600000000000000029 600000000000000030 600000000000000031 600000000000000032

出力例 4

YES

入力例 5

1 1
1

出力例 5

ALMOST

Score : 400 pts

Problem Statement

Takahashi is participating in the "Exact Shopping Challenge" held at a shopping mall.

The rules of this challenge are as follows. There are N items lined up in the venue, numbered from 1 to N, and the price of the i-th item (1 \leq i \leq N) is P_i yen. Takahashi must select and purchase 1 or more of these items, and if the total price of the selected items exactly matches the target amount of S yen, the challenge is successful. However, the same item cannot be selected more than once.

What Takahashi is concerned about as he faces the challenge is how many ways there are to succeed. If there are 0 ways to succeed, the challenge is hopeless. If there is only 1 way, he must find that unique combination precisely, which makes him anxious. If there are 2 or more ways, there is room for trial and error, so he can approach it relatively relaxed.

Here, a "way of selecting" refers to the set of items chosen. Since items are distinguished by their numbers, even if multiple items have the same price, they are treated as different items. If the sets of selected items differ, they are counted as different ways.

Let C be the total number of ways to select items such that the total price is exactly S yen. Output the following according to the value of C:

  • When C = 0: NO
  • When C = 1: ALMOST
  • When C \geq 2: YES

Constraints

  • 1 \leq N \leq 40
  • 1 \leq S \leq 10^{18}
  • 1 \leq P_i \leq 10^{18}
  • All inputs are integers

Input

N S
P_1 P_2 \ldots P_N
  • The first line contains an integer N representing the number of items and an integer S representing the target amount, separated by a space.
  • The second line contains N integers P_1, P_2, \ldots, P_N representing the price of each item, separated by spaces.

Output

According to the total number C of ways to select items such that the total price is exactly S yen, output NO if C = 0, ALMOST if C = 1, or YES if C \geq 2, on a single line.

Sample Input 1

4 7
2 3 4 5

Sample Output 1

YES

Sample Input 2

3 10
1 2 4

Sample Output 2

NO

Sample Input 3

12 50
1 2 4 8 16 32 64 128 256 512 1000 2000

Sample Output 3

ALMOST

Sample Input 4

35 1000000000000000000
1000000000000000000 1000000000000000000 600000000000000000 600000000000000001 600000000000000002 600000000000000003 600000000000000004 600000000000000005 600000000000000006 600000000000000007 600000000000000008 600000000000000009 600000000000000010 600000000000000011 600000000000000012 600000000000000013 600000000000000014 600000000000000015 600000000000000016 600000000000000017 600000000000000018 600000000000000019 600000000000000020 600000000000000021 600000000000000022 600000000000000023 600000000000000024 600000000000000025 600000000000000026 600000000000000027 600000000000000028 600000000000000029 600000000000000030 600000000000000031 600000000000000032

Sample Output 4

YES

Sample Input 5

1 1
1

Sample Output 5

ALMOST