English · Original
Chinese · Translation
Formal · Original
One day, Hongcow goes to the store and sees a brand new deck of _n_ special cards. Each individual card is either red or blue. He decides he wants to buy them immediately. To do this, he needs to play a game with the owner of the store.
This game takes some number of turns to complete. On a turn, Hongcow may do one of two things:
* Collect tokens. Hongcow collects 1 red token **and** 1 blue token by choosing this option (thus, 2 tokens in total per one operation).
* Buy a card. Hongcow chooses some card and spends tokens to purchase it as specified below.
The _i_\-th card requires _r__i_ red resources and _b__i_ blue resources. Suppose Hongcow currently has _A_ red cards and _B_ blue cards. Then, the _i_\-th card will require Hongcow to spend _max_(_r__i_ - _A_, 0) red tokens, and _max_(_b__i_ - _B_, 0) blue tokens. Note, only tokens disappear, but the cards stay with Hongcow forever. Each card can be bought only once.
Given a description of the cards and their costs determine the minimum number of turns Hongcow needs to purchase all cards.
## Input
The first line of input will contain a single integer _n_ (1 ≤ _n_ ≤ 16).
The next _n_ lines of input will contain three tokens _c__i_, _r__i_ and _b__i_. _c__i_ will be '_R_' or '_B_', denoting the color of the card as red or blue. _r__i_ will be an integer denoting the amount of red resources required to obtain the card, and _b__i_ will be an integer denoting the amount of blue resources required to obtain the card (0 ≤ _r__i_, _b__i_ ≤ 107).
## Output
Output a single integer, denoting the minimum number of turns needed to acquire all the cards.
[samples]
## Note
For the first sample, Hongcow's four moves are as follows:
1. Collect tokens
2. Buy card 1
3. Buy card 2
4. Buy card 3
Note, at the fourth step, Hongcow is able to buy card 3 because Hongcow already has one red and one blue card, so we don't need to collect tokens.For the second sample, one optimal strategy is as follows:
1. Collect tokens
2. Collect tokens
3. Buy card 2
4. Collect tokens
5. Buy card 3
6. Buy card 1
At the fifth step, even though Hongcow has a red token, Hongcow doesn't actually need to spend it, since Hongcow has a red card already.
一天，Hongcow 去商店看到一套全新的 #cf_span[n] 张特殊卡片。每张卡片要么是红色，要么是蓝色。他决定立即买下它们。为此，他需要与商店老板玩一个游戏。
这个游戏需要若干轮才能完成。在每一轮中，Hongcow 可以执行以下两种操作之一：
第 #cf_span[i] 张卡片需要 #cf_span[ri] 个红色资源和 #cf_span[bi] 个蓝色资源。假设 Hongcow 目前拥有 #cf_span[A] 张红色卡片和 #cf_span[B] 张蓝色卡片，则购买第 #cf_span[i] 张卡片需要花费 #cf_span[max(ri - A, 0)] 个红色令牌和 #cf_span[max(bi - B, 0)] 个蓝色令牌。注意，只有令牌会被消耗，而卡片将永久属于 Hongcow。每张卡片只能购买一次。
给定卡片及其花费的描述，请确定 Hongcow 购买所有卡片所需的最少轮数。
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 16])。
接下来的 #cf_span[n] 行每行包含三个标记：#cf_span[ci]、#cf_span[ri] 和 #cf_span[bi]。#cf_span[ci] 将是 '_R_' 或 '_B_'，表示卡片的颜色为红色或蓝色。#cf_span[ri] 是一个整数，表示获取该卡片所需的红色资源量，#cf_span[bi] 是一个整数，表示获取该卡片所需的蓝色资源量（#cf_span[0 ≤ ri, bi ≤ 107]）。
请输出一个整数，表示获取所有卡片所需的最少轮数。
对于第一个样例，Hongcow 的四步操作如下：
对于第二个样例，一种最优策略如下：
## Input
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 16])。接下来的 #cf_span[n] 行每行包含三个标记：#cf_span[ci]、#cf_span[ri] 和 #cf_span[bi]。#cf_span[ci] 将是 '_R_' 或 '_B_'，表示卡片的颜色为红色或蓝色。#cf_span[ri] 是一个整数，表示获取该卡片所需的红色资源量，#cf_span[bi] 是一个整数，表示获取该卡片所需的蓝色资源量（#cf_span[0 ≤ ri, bi ≤ 107]）。
## Output
请输出一个整数，表示获取所有卡片所需的最少轮数。
[samples]
## Note
对于第一个样例，Hongcow 的四步操作如下：
收集令牌
购买第 #cf_span[1] 张卡片
购买第 #cf_span[2] 张卡片
购买第 #cf_span[3] 张卡片
注意，在第四步时，Hongcow 已经拥有一张红色卡片和一张蓝色卡片，因此无需再收集令牌。
对于第二个样例，一种最优策略如下：
收集令牌
收集令牌
购买第 #cf_span[2] 张卡片
收集令牌
购买第 #cf_span[3] 张卡片
购买第 #cf_span[1] 张卡片
在第五步时，尽管 Hongcow 拥有红色令牌，但他实际上无需花费，因为他已经拥有一张红色卡片。
**Definitions:**
- Let $ n \in \mathbb{N} $, $ 1 \leq n \leq 16 $, be the number of cards.
- For each card $ i \in \{1, 2, \dots, n\} $:
- Let $ c_i \in \{\text{R}, \text{B}\} $ denote its color.
- Let $ r_i \in \mathbb{Z}_{\geq 0} $ denote the red resource requirement.
- Let $ b_i \in \mathbb{Z}_{\geq 0} $ denote the blue resource requirement.
**State:**
- Let $ A \in \mathbb{Z}_{\geq 0} $ be the number of red cards already owned.
- Let $ B \in \mathbb{Z}_{\geq 0} $ be the number of blue cards already owned.
- Initially, $ A = 0 $, $ B = 0 $.
**Cost to acquire card $ i $ given current state $ (A, B) $:**
- Red tokens required: $ \max(r_i - A, 0) $
- Blue tokens required: $ \max(b_i - B, 0) $
**Game mechanics:**
- Each turn, Hongcow may acquire **exactly one** card $ i $, provided he can pay the required tokens.
- After acquiring card $ i $:
- If $ c_i = \text{R} $, then $ A \gets A + 1 $
- If $ c_i = \text{B} $, then $ B \gets B + 1 $
- Tokens are consumed and do not accumulate; only cards are retained.
**Objective:**
- Find the minimum number of turns (i.e., the minimum sequence length) to acquire all $ n $ cards.
**Formal Problem:**
Given a set $ S = \{(c_i, r_i, b_i)\}_{i=1}^n $, find the minimum $ k \in \mathbb{N} $ such that there exists a permutation $ \pi \in S_n $ (ordering of card acquisitions) where, defining $ (A_0, B_0) = (0, 0) $ and for each $ t = 1 $ to $ k $:
- Let $ i = \pi(t) $
- Cost at step $ t $: $ \max(r_i - A_{t-1}, 0) $ red tokens and $ \max(b_i - B_{t-1}, 0) $ blue tokens are paid.
- Update:
- $ A_t = A_{t-1} + \mathbf{1}_{c_i = \text{R}} $
- $ B_t = B_{t-1} + \mathbf{1}_{c_i = \text{B}} $
Such that $ A_k + B_k = n $, and all cards are acquired.
**Output:** Minimum such $ k $.
API Response (JSON)
{
"problem": {
"name": "C. Hongcow Buys a Deck of Cards",
"description": {
"content": "One day, Hongcow goes to the store and sees a brand new deck of _n_ special cards. Each individual card is either red or blue. He decides he wants to buy them immediately. To do this, he needs to play",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF744C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "One day, Hongcow goes to the store and sees a brand new deck of _n_ special cards. Each individual card is either red or blue. He decides he wants to buy them immediately. To do this, he needs to play...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "一天，Hongcow 去商店看到一套全新的 #cf_span[n] 张特殊卡片。每张卡片要么是红色，要么是蓝色。他决定立即买下它们。为此，他需要与商店老板玩一个游戏。\n\n这个游戏需要若干轮才能完成。在每一轮中，Hongcow 可以执行以下两种操作之一：\n\n第 #cf_span[i] 张卡片需要 #cf_span[ri] 个红色资源和 #cf_span[bi] 个蓝色资源。假设 Hongcow 目前...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions:**\n- Let $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 16 $, be the number of cards.\n- For each card $ i \\in \\{1, 2, \\dots, n\\} $:\n - Let $ c_i \\in \\{\\text{R}, \\text{B}\\} $ denote its color.\n ...",
"is_translate": false,
"language": "Formal"
}
]
}