B. Рудольф и книжные коллекции

Codeforces

IDCF10176B

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Некоторое время назад Рудольф активно покупал книги по программированию и алгоритмам. Каждая из этих книг относилась к определённой коллекции — например, «Магический мир модулярной математики» или «Укконен (и его друзья) для самых маленьких». К сожалению, Рудольфу не всегда удавалось приобрести все выходящие книги, поэтому сейчас у него скопилось N неполных книжных коллекций. Рудольф хочет оставить только полные коллекции, поэтому он решил, что с каждой из имеющихся коллекций он поступит одним из двух способов — либо докупит недостающие книги, либо продаст имеющиеся. В интернет-магазинах Рудольфу удалось найти все интересующие книги, и теперь он знает, что i-ю из его коллекций можно сделать полной за Ai рублей либо продать за Bi рублей. У Рудольфа есть M рублей, которые он может потратить на приобретение книг; кроме того, приобретать книги можно и на деньги, вырученные от продажи книг. Рудольф хочет собрать как можно больше полных коллекций. Помогите ему определить, какое максимальное количество коллекций он сможет получить, если будет покупать и продавать книги оптимальным образом. Первая строка содержит целое число N (1 ≤ N ≤ 1000) — количество неполных книжных коллекций у Рудольфа. Следующие N строк описывают книжные коллекции. Каждая из них содержит целые числа Ai и Bi (0 ≤ Ai, Bi ≤ 106) — соответственно стоимость покупки недостающих книг и стоимость продажи имеющихся книг. Следующая строка содержит целое число M (0 ≤ M ≤ 106) — начальное количество денег у Рудольфа. Выведите одно целое число — максимальное количество полных коллекций, которое может собрать Рудольф. ## Входные Данные Первая строка содержит целое число N (1 ≤ N ≤ 1000) — количество неполных книжных коллекций у Рудольфа.Следующие N строк описывают книжные коллекции. Каждая из них содержит целые числа Ai и Bi (0 ≤ Ai, Bi ≤ 106) — соответственно стоимость покупки недостающих книг и стоимость продажи имеющихся книг.Следующая строка содержит целое число M (0 ≤ M ≤ 106) — начальное количество денег у Рудольфа. ## Выходные Данные Выведите одно целое число — максимальное количество полных коллекций, которое может собрать Рудольф. ## Примеры Входные данные3600 600200 800300 550415Выходные данные2Входные данные6130 160110 170190 120180 130180 180100 170170Выходные данные3 [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of incomplete book collections. For each collection $ i \in \{1, \dots, N\} $: - $ A_i \in \mathbb{Z}_{\geq 0} $: cost to complete the collection. - $ B_i \in \mathbb{Z}_{\geq 0} $: revenue from selling the collection. Let $ M \in \mathbb{Z}_{\geq 0} $ be the initial amount of money. **Decision Variables** For each collection $ i $, define: - $ x_i \in \{0, 1, 2\} $: - $ x_i = 0 $: sell the collection (gains $ B_i $), - $ x_i = 1 $: do nothing, - $ x_i = 2 $: complete the collection (spends $ A_i $). **Constraints** 1. $ \sum_{i=1}^N \left( x_i = 2 \right) \cdot A_i - \sum_{i=1}^N \left( x_i = 0 \right) \cdot B_i \leq M $ 2. $ x_i \in \{0, 1, 2\} $ for all $ i \in \{1, \dots, N\} $ **Objective** Maximize: $$ \sum_{i=1}^N \mathbb{I}(x_i = 2) $$

API Response (JSON)

{
  "problem": {
    "name": "B. Рудольф и книжные коллекции",
    "description": {
      "content": "Некоторое время назад Рудольф активно покупал книги по программированию и алгоритмам. Каждая из этих книг относилась к определённой коллекции — например, «Магический мир модулярной математики» или «Ук",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10176B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Некоторое время назад Рудольф активно покупал книги по программированию и алгоритмам. Каждая из этих книг относилась к определённой коллекции — например, «Магический мир модулярной математики» или «Ук...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of incomplete book collections.  \nFor each collection $ i \\in \\{1, \\dots, N\\} $:  \n- $ A_i \\in \\mathbb{Z}_{\\geq 0} $: cost to complete the co...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments