A. Alyona and copybooks

Codeforces

IDCF740A

Time1000ms

Memory256MB

Difficulty—

brute forceimplementation

English · Original

Chinese · Translation

Formal · Original

Little girl Alyona is in a shop to buy some copybooks for school. She study four subjects so she wants to have equal number of copybooks for each of the subjects. There are three types of copybook's packs in the shop: it is possible to buy one copybook for _a_ rubles, a pack of two copybooks for _b_ rubles, and a pack of three copybooks for _c_ rubles. Alyona already has _n_ copybooks. What is the minimum amount of rubles she should pay to buy such number of copybooks _k_ that _n_ + _k_ is divisible by 4? There are infinitely many packs of any type in the shop. Alyona can buy packs of different type in the same purchase. ## Input The only line contains 4 integers _n_, _a_, _b_, _c_ (1 ≤ _n_, _a_, _b_, _c_ ≤ 109). ## Output Print the minimum amount of rubles she should pay to buy such number of copybooks _k_ that _n_ + _k_ is divisible by 4. [samples] ## Note In the first example Alyona can buy 3 packs of 1 copybook for 3_a_ = 3 rubles in total. After that she will have 4 copybooks which she can split between the subjects equally. In the second example Alyuna can buy a pack of 2 copybooks for _b_ = 1 ruble. She will have 8 copybooks in total. In the third example Alyona can split the copybooks she already has between the 4 subject equally, so she doesn't need to buy anything. In the fourth example Alyona should buy one pack of one copybook.

小女生Alyona去商店为学校购买一些练习本。她学习四门课程，因此希望每门课程都有相同数量的练习本。商店中有三种类型的练习本包装：可以以 #cf_span[a] 卢布购买一本练习本，以 #cf_span[b] 卢布购买一包两本练习本，或以 #cf_span[c] 卢布购买一包三本练习本。Alyona 已经有 #cf_span[n] 本练习本。她最少需要支付多少卢布，才能购买数量为 #cf_span[k] 的练习本，使得 #cf_span[n + k] 能被 #cf_span[4] 整除？商店中每种类型的包装都有无限多。Alyona 可以在一次购买中购买不同类型的包装。仅一行包含 #cf_span[4] 个整数 #cf_span[n], #cf_span[a], #cf_span[b], #cf_span[c]（#cf_span[1 ≤ n, a, b, c ≤ 10^9]）。请输出她为购买满足 #cf_span[n + k] 能被 #cf_span[4] 整除的 #cf_span[k] 本练习本所需的最少卢布数。在第一个例子中，Alyona 可以购买 #cf_span[3] 包每包一本的练习本，总共花费 #cf_span[3a = 3] 卢布。之后她将拥有 #cf_span[4] 本练习本，可以平均分配给四门课程。在第二个例子中，Alyona 可以购买一包两本的练习本，花费 #cf_span[b = 1] 卢布。她总共将拥有 #cf_span[8] 本练习本。在第三个例子中，Alyona 已有的练习本可以平均分配给 #cf_span[4] 门课程，因此她无需购买任何东西。在第四个例子中，Alyona 应该购买一包一本的练习本。 ## Input 仅一行包含 #cf_span[4] 个整数 #cf_span[n], #cf_span[a], #cf_span[b], #cf_span[c]（#cf_span[1 ≤ n, a, b, c ≤ 10^9]）。 ## Output 请输出她为购买满足 #cf_span[n + k] 能被 #cf_span[4] 整除的 #cf_span[k] 本练习本所需的最少卢布数。 [samples] ## Note 在第一个例子中，Alyona 可以购买 #cf_span[3] 包每包一本的练习本，总共花费 #cf_span[3a = 3] 卢布。之后她将拥有 #cf_span[4] 本练习本，可以平均分配给四门课程。在第二个例子中，Alyona 可以购买一包两本的练习本，花费 #cf_span[b = 1] 卢布。她总共将拥有 #cf_span[8] 本练习本。在第三个例子中，Alyona 已有的练习本可以平均分配给 #cf_span[4] 门课程，因此她无需购买任何东西。在第四个例子中，Alyona 应该购买一包一本的练习本。

**Definitions** Let $ n, a, b, c \in \mathbb{Z}^+ $ be given integers. Let $ k \in \mathbb{Z}_{\geq 0} $ be the number of copybooks to buy. **Constraints** 1. $ 1 \leq n, a, b, c \leq 10^9 $ 2. $ k $ must satisfy $ (n + k) \equiv 0 \pmod{4} $ 3. $ k $ is expressible as $ k = x + 2y + 3z $ for some $ x, y, z \in \mathbb{Z}_{\geq 0} $ **Objective** Minimize the cost: $$ \min_{x,y,z \geq 0} \left( a \cdot x + b \cdot y + c \cdot z \right) $$ subject to: $$ x + 2y + 3z \equiv (-n) \pmod{4}, \quad x + 2y + 3z \geq 0 $$

Samples

Input #1

1 1 3 4

Output #1

Input #2

6 2 1 1

Output #2

Input #3

4 4 4 4

Output #3

Input #4

999999999 1000000000 1000000000 1000000000

Output #4

1000000000

API Response (JSON)

{
  "problem": {
    "name": "A. Alyona and copybooks",
    "description": {
      "content": "Little girl Alyona is in a shop to buy some copybooks for school. She study four subjects so she wants to have equal number of copybooks for each of the subjects. There are three types of copybook's p",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF740A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Little girl Alyona is in a shop to buy some copybooks for school. She study four subjects so she wants to have equal number of copybooks for each of the subjects. There are three types of copybook's p...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "小女生Alyona去商店为学校购买一些练习本。她学习四门课程，因此希望每门课程都有相同数量的练习本。商店中有三种类型的练习本包装：可以以 #cf_span[a] 卢布购买一本练习本，以 #cf_span[b] 卢布购买一包两本练习本，或以 #cf_span[c] 卢布购买一包三本练习本。Alyona 已经有 #cf_span[n] 本练习本。\n\n她最少需要支付多少卢布，才能购买数量为 #cf_sp...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, a, b, c \\in \\mathbb{Z}^+ $ be given integers.  \nLet $ k \\in \\mathbb{Z}_{\\geq 0} $ be the number of copybooks to buy.  \n\n**Constraints**  \n1. $ 1 \\leq n, a, b, c \\leq 10^9 $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments