Abc 286 D - Money in Hand
您是打尖儿还是住店呢
2024年06月30日 07:10
收录于文集
共499篇

Problem Statement

Takahashi has N kinds of coins; specifically, for 1≤i≤N, he has B i  coins worth A i  yen (the currency in Japan) each.

Determine if Takahashi can pay exactly X yen (without change) with the coins he currently has.

高桥有 N 种硬币;具体来说,对于 1≤i≤N,他有 B i 枚硬币,每枚价值 A i 日元(日本货币)。确定高桥是否能用他目前拥有的硬币支付 X 日元(不找零)。

Constraints

1≤N≤50

1≤X≤10 4

1≤A i ≤100 1≤B i ≤50 A i  are pairwise distinct.

All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N

X

A 1  B 1 A 2  B 2 ⋮A N  B N

Output

Print Yes if Takahashi can pay exactly X yen with the coins he currently has; print No otherwise.

Sample Input 1

2 19

2 3

5 6

Sample Output 1

Yes

Takahashi has three 2-yen coins and six 5-yen coins. He can use two 2-yen coins and three 5-yen coins to pay exactly 2×2+5×3=19 yen. Thus, Yes should be printed.

Sample Input 2

2 18

2 3

5 6

Sample Output 2

No

There is no combination of the coins that he can use to pay exactly

18 yen. Thus, No should be printed.

 

Sample Input 3

3 1001

1 1

2 1

100 10

Sample Output 3

Yes

He need not use all kinds of coins.

构造一个数组,然后每次去更新能达到的最长的位置,也就是能换成多少钱。

然后每次重新更新数组。最后判断canPay[n]是true or false。

-------------

代码块
JavaScript
自动换行
复制代码
import java.util.Scanner;

public class Abc286 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int x=sc.nextInt();
        boolean[]canpay=new boolean[x+1];
        canpay[0]=true;
        while (n-->0) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            boolean[]next=new boolean[x+1];
            for (int i = 0; i <=x; i++) {
                for (int j = 0; j <=b&&i+a*j<=x; j++) {
                    next[i+a*j]=next[i+a*j]|canpay[i];
                }
            }
            canpay=next;
        }
        System.out.println(canpay[x]?"Yes":"No");
        sc.close();
    }
}

复制成功