A. Kirill And The Game

Codeforces

IDCF842A

Time2000ms

Memory256MB

Difficulty—

brute forcetwo pointers

English · Original

Chinese · Translation

Formal · Original

Kirill plays a new computer game. He came to the potion store where he can buy any potion. Each potion is characterized by two integers — amount of experience and cost. The efficiency of a potion is the ratio of the amount of experience to the cost. Efficiency may be a non-integer number. For each two integer numbers _a_ and _b_ such that _l_ ≤ _a_ ≤ _r_ and _x_ ≤ _b_ ≤ _y_ there is a potion with experience _a_ and cost _b_ in the store (that is, there are (_r_ - _l_ + 1)·(_y_ - _x_ + 1) potions). Kirill wants to buy a potion which has efficiency _k_. Will he be able to do this? ## Input First string contains five integer numbers _l_, _r_, _x_, _y_, _k_ (1 ≤ _l_ ≤ _r_ ≤ 107, 1 ≤ _x_ ≤ _y_ ≤ 107, 1 ≤ _k_ ≤ 107). ## Output Print "_YES_" without quotes if a potion with efficiency exactly _k_ can be bought in the store and "_NO_" without quotes otherwise. You can output each of the letters in any register. [samples]

Kirill 正在玩一款新电脑游戏。他来到一家药水商店，可以购买任意药水。每种药水由两个整数表征——经验值和价格。药水的效率是经验值与价格的比值，效率可能不是整数。对于每一对整数 #cf_span[a] 和 #cf_span[b]，满足 #cf_span[l ≤ a ≤ r] 且 #cf_span[x ≤ b ≤ y]，商店中都存在一种经验值为 #cf_span[a]、价格为 #cf_span[b] 的药水（即共有 #cf_span[(r - l + 1)·(y - x + 1)] 种药水）。 Kirill 希望购买一种效率恰好为 #cf_span[k] 的药水。他能办到吗？第一行包含五个整数 #cf_span[l], #cf_span[r], #cf_span[x], #cf_span[y], #cf_span[k]（#cf_span[1 ≤ l ≤ r ≤ 10^7], #cf_span[1 ≤ x ≤ y ≤ 10^7], #cf_span[1 ≤ k ≤ 10^7]）。如果商店中存在一种效率恰好为 #cf_span[k] 的药水，则输出 "_YES_"（不含引号）；否则输出 "_NO_"（不含引号）。你可以以任意大小写输出字母。 ## Input 第一行包含五个整数 #cf_span[l], #cf_span[r], #cf_span[x], #cf_span[y], #cf_span[k]（#cf_span[1 ≤ l ≤ r ≤ 10^7], #cf_span[1 ≤ x ≤ y ≤ 10^7], #cf_span[1 ≤ k ≤ 10^7]）。 ## Output 如果商店中存在一种效率恰好为 #cf_span[k] 的药水，则输出 "_YES_"（不含引号）；否则输出 "_NO_"（不含引号）。你可以以任意大小写输出字母。 [samples]

**Definitions** Let $ l, r, x, y, k \in \mathbb{Z}^+ $ with $ 1 \leq l \leq r \leq 10^7 $, $ 1 \leq x \leq y \leq 10^7 $, $ 1 \leq k \leq 10^7 $. The set of possible potions is: $$ P = \{ (a, b) \in \mathbb{Z}^2 \mid a \in [l, r],\ b \in [x, y] \} $$ The efficiency of a potion $ (a, b) \in P $ is $ \frac{a}{b} $. **Objective** Determine whether there exists a pair $ (a, b) \in P $ such that: $$ \frac{a}{b} = k $$ Equivalently, determine whether there exist integers $ a \in [l, r] $, $ b \in [x, y] $ such that: $$ a = k \cdot b $$

Samples

Input #1

1 10 1 10 1

Output #1

YES

Input #2

1 5 6 10 1

Output #2

NO

API Response (JSON)

{
  "problem": {
    "name": "A. Kirill And The Game",
    "description": {
      "content": "Kirill plays a new computer game. He came to the potion store where he can buy any potion. Each potion is characterized by two integers — amount of experience and cost. The efficiency of a potion is t",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF842A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Kirill plays a new computer game. He came to the potion store where he can buy any potion. Each potion is characterized by two integers — amount of experience and cost. The efficiency of a potion is t...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Kirill 正在玩一款新电脑游戏。他来到一家药水商店，可以购买任意药水。每种药水由两个整数表征——经验值和价格。药水的效率是经验值与价格的比值，效率可能不是整数。\n\n对于每一对整数 #cf_span[a] 和 #cf_span[b]，满足 #cf_span[l ≤ a ≤ r] 且 #cf_span[x ≤ b ≤ y]，商店中都存在一种经验值为 #cf_span[a]、价格为 #cf_span...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ l, r, x, y, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq l \\leq r \\leq 10^7 $, $ 1 \\leq x \\leq y \\leq 10^7 $, $ 1 \\leq k \\leq 10^7 $.  \n\nThe set of possible potions is:  \n$$\nP = \\{ (a, b...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments