B. Door Frames

Codeforces

IDCF910B

Time1000ms

Memory256MB

Difficulty—

greedyimplementation

English · Original

Chinese · Translation

Formal · Original

Petya has equal wooden bars of length _n_. He wants to make a frame for _two_ equal doors. Each frame has two vertical (left and right) sides of length _a_ and one top side of length _b_. A solid (i.e. continuous without breaks) piece of bar is needed for each side. Determine a minimal number of wooden bars which are needed to make the frames for two doors. Petya can cut the wooden bars into any parts, but each side of each door should be a solid piece of a wooden bar (or a whole wooden bar). ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 1 000) — the length of each wooden bar. The second line contains a single integer _a_ (1 ≤ _a_ ≤ _n_) — the length of the vertical (left and right) sides of a door frame. The third line contains a single integer _b_ (1 ≤ _b_ ≤ _n_) — the length of the upper side of a door frame. ## Output Print the minimal number of wooden bars with length _n_ which are needed to make the frames for two doors. [samples] ## Note In the first example one wooden bar is enough, since the total length of all six sides of the frames for two doors is 8. In the second example 6 wooden bars is enough, because for each side of the frames the new wooden bar is needed.

Petya 有若干根长度为 #cf_span[n] 的相同木条。他想为 _两_ 扇相同的门制作框架。每个框架由两个垂直边（左、右）组成，长度为 #cf_span[a]，以及一个顶部边，长度为 #cf_span[b]。每条边都需要使用一根完整的（即连续无断裂）木条。请确定制作两扇门的框架所需的最少木条数量。Petya 可以将木条切割成任意部分，但每扇门的每条边都必须由一根完整的木条（或整根木条）构成。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1 000]) —— 每根木条的长度。第二行包含一个整数 #cf_span[a] (#cf_span[1 ≤ a ≤ n]) —— 门框垂直边（左、右）的长度。第三行包含一个整数 #cf_span[b] (#cf_span[1 ≤ b ≤ n]) —— 门框顶部边的长度。请输出制作两扇门的框架所需的最少长度为 #cf_span[n] 的木条数量。在第一个例子中，一根木条就足够了，因为两扇门的六个边的总长度为 #cf_span[8]。在第二个例子中，需要 #cf_span[6] 根木条，因为每个框架边都需要使用一根新的木条。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1 000]) —— 每根木条的长度。第二行包含一个整数 #cf_span[a] (#cf_span[1 ≤ a ≤ n]) —— 门框垂直边（左、右）的长度。第三行包含一个整数 #cf_span[b] (#cf_span[1 ≤ b ≤ n]) —— 门框顶部边的长度。 ## Output 请输出制作两扇门的框架所需的最少长度为 #cf_span[n] 的木条数量。 [samples] ## Note 在第一个例子中，一根木条就足够了，因为两扇门的六个边的总长度为 #cf_span[8]。在第二个例子中，需要 #cf_span[6] 根木条，因为每个框架边都需要使用一根新的木条。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of each wooden bar. Let $ a \in \mathbb{Z}^+ $ be the length of each vertical side of a door frame. Let $ b \in \mathbb{Z}^+ $ be the length of the top side of a door frame. **Constraints** $ 1 \leq n \leq 1000 $, $ 1 \leq a \leq n $, $ 1 \leq b \leq n $. **Objective** Construct frames for **two** identical doors. Each door requires: - Two vertical sides of length $ a $, - One top side of length $ b $. Thus, two doors require: - $ 4 $ vertical pieces of length $ a $, - $ 2 $ top pieces of length $ b $. Each piece must be cut as a **solid segment** from a bar of length $ n $; cuts are allowed, but no piece may be assembled from multiple bars. Minimize the number of bars needed such that all 6 pieces can be cut from them, with each bar’s total cut length ≤ $ n $. Find the minimal number of bars $ k \in \mathbb{Z}^+ $ such that the multiset $ \{a, a, a, a, b, b\} $ can be partitioned into $ k $ subsets, each with sum ≤ $ n $.

Samples

Input #1

8
1
2

Output #1

Input #2

5
3
4

Output #2

Input #3

6
4
2

Output #3

Input #4

20
5
6

Output #4

API Response (JSON)

{
  "problem": {
    "name": "B. Door Frames",
    "description": {
      "content": "Petya has equal wooden bars of length _n_. He wants to make a frame for _two_ equal doors. Each frame has two vertical (left and right) sides of length _a_ and one top side of length _b_. A solid (i.e",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF910B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Petya has equal wooden bars of length _n_. He wants to make a frame for _two_ equal doors. Each frame has two vertical (left and right) sides of length _a_ and one top side of length _b_. A solid (i.e...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Petya 有若干根长度为 #cf_span[n] 的相同木条。他想为 _两_ 扇相同的门制作框架。每个框架由两个垂直边（左、右）组成，长度为 #cf_span[a]，以及一个顶部边，长度为 #cf_span[b]。每条边都需要使用一根完整的（即连续无断裂）木条。\n\n请确定制作两扇门的框架所需的最少木条数量。Petya 可以将木条切割成任意部分，但每扇门的每条边都必须由一根完整的木条（或整根木条）...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of each wooden bar.  \nLet $ a \\in \\mathbb{Z}^+ $ be the length of each vertical side of a door frame.  \nLet $ b \\in \\mathbb{Z}^+ $ be the len...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments