1. sum

You are given three integers $a$ , $b$ , and $c$ . Determine if one of them is the sum of the other two.

Input

The first line contains a single integer $t (1≤t≤9261)$ — the number of test cases.

The description of each test case consists of three integers $a$ , $b$ , $c$ ( $0≤a,b,c≤20$ ).

Output

For each test case, output “YES” if one of the numbers is the sum of the other two, and “NO” otherwise.

You can output the answer in any case (for example, the strings “yEs”, “yes”, “Yes” and “YES” will be recognized as a positive answer).

Example

input

output

YES
NO
YES
YES
NO
NO
YES

Note

In the first test case, $1 + 3 = 4$

In the second test case, none of the numbers is the sum of the other two.

In the third test case, $9 + 11 = 20$

直接枚举所有情况判断即可

#include <iostream>
 
int main()
{
    int num{ 0 };
    std::cin >> num;
 
    for (int i = 0; i < num; ++i)
    {
        int a{ 0 }, b{ 0 }, c{ 0 };
        std::cin >> a >> b >> c;
 
        if (a == b + c || b == a + c || c == a + b)
        {
            std::cout << "Yes" << std::endl;
        }
        else
        {
            std::cout << "No" << std::endl;
        }
    }
   
    return 0;
}

2. Money Buys Happiness

Being a physicist, Charlie likes to plan his life in simple and precise terms.

For the next $m$ months, starting with no money, Charlie will work hard and earn $x$ pounds per month. For the $i_{th}$ month $(1≤i≤m)$ , there’ll be a single opportunity of paying cost $c_i$ pounds to obtain happiness $h_i$ .

Borrowing is not allowed. Money earned in the $i_{th}$ month can only be spent in a later $j_{th}$ month $(j > i)$ .

Since physicists don’t code, help Charlie find the maximum obtainable sum of happiness.

Input

The first line of input contains a single integer $t$ $(1≤t≤1000)$ — the number of test cases.

The first line of each test case contains two integers, $m$ and $x$ $(1≤m≤50, 1≤x≤10^8)$ — the total number of months and the monthly salary.

The $i_{th}$ of the following $m$ lines contains two integers, $c_i$ and $h_i$ $(0≤ci≤10^8, 1≤hi≤10^3)$ — the cost and happiness on offer for the $i_{th}$ month. Note that some happiness may be free ( $ci=0$ for some $i's$ ).

It is guaranteed that the sum of $\sum_{i}h_i$ over all test cases does not exceed $10^5$ .

Output

For each test case, print a single integer, the maximum sum of happiness Charlie could obtain.

Example

input

output

Note

In the first test case, Charlie only gets paid at the end of the month, so is unable to afford anything.

In the second test case, Charlie obtains the free happiness in the first month.

In the third test case, it’s optimal for Charlie to buy happiness in the second month. Even with money left at the end, Charlie could not go back in time to obtain the happiness on offer in the first month.

Charlie 在接下来的 $m$ 个月中，初始资金为 $0$ ，每个月所获工资为 $x$ 。在第 $i$ 个月，他可以选择花费 $c_i$ 获取快乐值 $h_i$ 。但是当月的工资至少要等到下个月才能使用。计算出能获取的最大快乐值。

输入第一行为用例数量，第二行输入 $m$ 和 $x$ ，接下来 $m$ 行输入 $c_i$ 和 $h_i$ 。

因为题目中规定快乐值之和不会超过 $10^5$ ，所以我们使用一个 dp 数组表示前 i 个月获得 j 的快乐值能留下的最多资金在时间上也是可以接受的。

首先明确这样一个事实，能获得的最大快乐值不会超过 sum，因为 sum 是所有快乐值的总和。假设我们已经求解出 dp 数组，我们自 sum 开始，从大到小遍历，第一个大于 0 的下标就是所求的快乐值。即：

for (int i = sum; i >= 0; --i)
{
    if (dp[i] >= 0)
        return i;
}

那么如何求解 dp 呢，对于每个 dp 数组的每一项我们都先初始化为 -1，这是一个非法值，因为小于 0 表示资金不够，所对应的下标一定不是题解。然后从 sum 开始依次向下求解。

dp[j] 有两种选择：

要么是维持原先状态
要么是从 dp[j - offers[i].happiness] 转移而来，转移的代价是 dp[j - offers[i].happiness]（因为 dp[j - offers[i].happiness] 的意义是为了获得快乐值 j - offers[i].happiness 所能留下的最多资金）大于购买快乐所需要的花费 offers[i].cost，并且减去它。即：
1
2
3
4
if (dp[j - offers[i].happiness] >= offers[i].cost)
{
dp[j] = max(dp[j], dp[j - offers[i].happiness] - offers[i].cost);
}

我们将月份放在循环最层，因为我们的目的是在所有月份中求解出最大的快乐值。每当月份递增时，我们需要为对应的 dp 加上资金 $x$ 。

最终的解法如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Offer
{
    int cost;
    int happiness;
};

int solve(int m, int x, int sum, vector<Offer>& offers)
{
    // dp 表示前 i 个月获得 j 的快乐能留下的最多资金
    vector<long long> dp(sum + 1, -1);
    dp[0] = 0;

    for (int i = 1; i <= m; ++i)
    {
        for (int j = sum; j >= offers[i].happiness; --j)
        {
            if (dp[j - offers[i].happiness] >= offers[i].cost)
            {
                dp[j] = max(dp[j], dp[j - offers[i].happiness] - offers[i].cost);
            }
        }
        for (int j = 0; j <= sum; ++j)
        {
            if (dp[j] >= 0)
            {
                dp[j] += x;
            }
        }
    }

    for (int i = sum; i >= 0; --i)
    {
        if (dp[i] >= 0)
            return i;
    }
    
    return -1;
}

int main()
{
    int t{0};
    cin >> t;

    while (t--)
    {
        int m{ 0 }, x{0};
        cin >> m >> x;

        vector<Offer> offers(m + 1);
        int sum{ 0 };
        for (int i = 1; i <= m; ++i)
        {
            cin >> offers[i].cost >> offers[i].happiness;
            sum += offers[i].happiness;
        }

        cout << solve(m, x, sum, offers) << endl;
    }
   
    return 0;
}

3. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)
     偷窃到的最高金额 = 1 + 3 = 4

示例2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)
     偷窃到的最高金额 = 2 + 9 + 1 = 12

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

我们使用一个 dp 数组来表示偷窃前 i 家房屋所得的最多钱财。因为小偷无法连续两次进行偷盗，那么 dp[i] 的状态便只能是由 dp[i-1] 或者 dp[i-2] 转移而来。

假如第 (i -1) 家被偷窃了，那么第 i 家就不能被偷窃，则 dp[i] = dp[i - 1]。而如果第 (i - 1) 家没有被偷窃，则 dp[i] = dp[i - 2] + nums[i]。最终取这两种可能中较大的那一个。

class Solution 
{
public:
    int rob(vector<int>& nums) 
    {
        if(nums.empty())
            return 0;

        if(nums.size() == 1)
            return nums[0];

        // dp[i] 表示偷窃前 i 家房屋所得的最多钱财
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for(int i = 2; i < nums.size(); ++i)
        {
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }

        return dp[nums.size() - 1];
    }
};

4. 设计数字容器系统

设计一个数字容器系统，可以实现以下功能：

在系统中给定下标处插入或者替换一个数字
返回系统中给定数字的最小下标

请你实现一个 NumberContainers 类：

NumberContainers() 初始化数字容器系统
void change(int index, int number) 在下标 index 处填入 number 。如果该下标 index 处已经有数字了，那么用 number 替换该数字
int find(int number) 返回给定数字 number 在系统中的最小下标。如果系统中没有 number ，那么返回 -1

示例：

输入：
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
    
输出：
[null, -1, null, null, null, null, 1, null, 2]
    
解释：
NumberContainers nc = new NumberContainers();
nc.find(10); // 没有数字 10 ，所以返回 -1 。
nc.change(2, 10); // 容器中下标为 2 处填入数字 10 。
nc.change(1, 10); // 容器中下标为 1 处填入数字 10 。
nc.change(3, 10); // 容器中下标为 3 处填入数字 10 。
nc.change(5, 10); // 容器中下标为 5 处填入数字 10 。
nc.find(10); // 数字 10 所在的下标为 1 ，2 ，3 和 5 。因为最小下标为 1 ，所以返回 1 。
nc.change(1, 20); // 容器中下标为 1 处填入数字 20 。注意，下标 1 处之前为 10 ，现在被替换为 20 。
nc.find(10); // 数字 10 所在下标为 2 ，3 和 5 。最小下标为 2 ，所以返回 2 。

提示：

1 <= index, number <= 109
调用 change 和 find 的 总次数 不超过 105 次

change 本质上是基于 index 的查找和更改，find 是基于 value 的查找。所以这里使用两个哈希表，第一个哈希表 nums 是 index 和 value 的映射，第二个哈希表是 value 和 index 的映射，因为 value 值可能重复，而且我们有返回最小索引的需求，所以使用 set 存储 index。

在 change 中，如果 nums 中没有找到 index，说明不存在 index 对应的数据，给两张表都加入这份数据。如果找到了，则需要先从 numsDic 中先删除 value 对应的 index。

class NumberContainers 
{
public:
    NumberContainers() 
    {
    }
    
    void change(int index, int number) 
    {
        auto it = nums.find(index);
        if(it != nums.end())
        {
            numsDic[it->second].erase(index);
        }
        numsDic[number].insert(index);
        nums[index] = number;
    }
    
    int find(int number) 
    {
        if(numsDic[number].empty())
            return -1;
        return *numsDic[number].begin();
    }

private:
    std::unordered_map<int, int> nums;
    std::unordered_map<int, set<int>> numsDic;
};

Zwei

Coding Problems

1. sum

2. Money Buys Happiness

3. 打家劫舍

4. 设计数字容器系统