G. Perfectionist Arkadiy

Codeforces

IDCF795G

Time1000ms

Memory256MB

Difficulty—

mathnumber theory

English · Original

Chinese · Translation

Formal · Original

Arkadiy has lots square photos with size _a_ × _a_. He wants to put some of them on a rectangular wall with size _h_ × _w_. The photos which Arkadiy will put on the wall must form a rectangular grid and the distances between neighboring vertically and horizontally photos and also the distances between outside rows and columns of photos to the nearest bound of the wall must be equal to _x_, where _x_ is some non-negative **real** number. Look on the picture below for better understanding of the statement. <center>![image](https://espresso.codeforces.com/a732e2b47d768b7f609ec4bd187f2a057170ad61.png)</center>Arkadiy haven't chosen yet how many photos he would put on the wall, however, he want to put at least one photo. Your task is to determine the **minimum** value of _x_ which can be obtained after putting photos, or report that there is no way to put positive number of photos and satisfy all the constraints. Suppose that Arkadiy has enough photos to make any valid arrangement according to the constraints. Note that Arkadiy wants to put at least one photo on the wall. The photos should not overlap, should completely lie inside the wall bounds and should have sides parallel to the wall sides. ## Input The first line contains three integers _a_, _h_ and _w_ (1 ≤ _a_, _h_, _w_ ≤ 109) — the size of photos and the height and the width of the wall. ## Output Print one non-negative real number — the minimum value of _x_ which can be obtained after putting the photos on the wall. The absolute or the relative error of the answer must not exceed 10 - 6. Print _\-1_ if there is no way to put positive number of photos and satisfy the constraints. [samples] ## Note In the first example Arkadiy can put 7 rows of photos with 5 photos in each row, so the minimum value of _x_ equals to 0.5. In the second example Arkadiy can put only 1 photo which will take the whole wall, so the minimum value of _x_ equals to 0. In the third example there is no way to put positive number of photos and satisfy the constraints described in the statement, so the answer is _\-1_.

Arkadiy 有大量边长为 $a × a$ 的正方形照片。他想将其中一些贴在一面尺寸为 $h × w$ 的矩形墙上。 Arkadiy 贴在墙上的照片必须形成一个矩形网格，且相邻照片之间在垂直和水平方向上的间距，以及最外层照片行/列到墙边界的距离，都必须等于某个非负实数 $x$。请参考下图以更好地理解题意。 Arkadiy 尚未决定要贴多少张照片，但他至少要贴一张。你的任务是确定在满足所有约束条件下可能获得的最小 $x$ 值，或者报告不存在满足条件的正数张照片的贴法。假设 Arkadiy 拥有足够多的照片，可以实现任何符合约束的排列。注意：Arkadiy 至少要贴一张照片。照片不能重叠，必须完全位于墙的边界内，且边必须与墙的边平行。第一行包含三个整数 $a$, $h$ 和 $w$ ($1 ≤ a, h, w ≤ 10^9$) —— 照片的尺寸以及墙的高度和宽度。请输出一个非负实数，表示贴完照片后可能得到的最小 $x$ 值。答案的绝对误差或相对误差不得超过 $10^{-6}$。如果不存在满足约束的正数张照片的贴法，请输出 _-1_。在第一个例子中，Arkadiy 可以贴 7 行照片，每行 5 张，此时最小的 $x$ 值为 $0.5$。在第二个例子中，Arkadiy 只能贴 1 张照片，恰好填满整面墙，此时最小的 $x$ 值为 $0$。在第三个例子中，不存在满足题述约束的正数张照片的贴法，因此答案为 _-1_。 ## Input 第一行包含三个整数 $a$, $h$ 和 $w$ ($1 ≤ a, h, w ≤ 10^9$) —— 照片的尺寸以及墙的高度和宽度。 ## Output 请输出一个非负实数，表示贴完照片后可能得到的最小 $x$ 值。答案的绝对误差或相对误差不得超过 $10^{-6}$。如果不存在满足约束的正数张照片的贴法，请输出 _-1_。 [samples] ## Note 在第一个例子中，Arkadiy 可以贴 7 行照片，每行 5 张，此时最小的 $x$ 值为 $0.5$。在第二个例子中，Arkadiy 只能贴 1 张照片，恰好填满整面墙，此时最小的 $x$ 值为 $0$。在第三个例子中，不存在满足题述约束的正数张照片的贴法，因此答案为 _-1_。

**Definitions** Let $ a, h, w \in \mathbb{Z}^+ $ be the side length of each square photo, and the height and width of the wall, respectively. Let $ m, n \in \mathbb{Z}^+ $ be the number of rows and columns of photos, respectively. Let $ x \in \mathbb{R}_{\geq 0} $ be the uniform spacing between adjacent photos and between the outermost photos and the wall boundaries. **Constraints** The arrangement of $ m $ rows and $ n $ columns of photos must satisfy: $$ m \cdot a + (m + 1) \cdot x = h \tag{1} $$ $$ n \cdot a + (n + 1) \cdot x = w \tag{2} $$ **Objective** Find the minimum $ x \geq 0 $ such that there exist $ m, n \in \mathbb{Z}^+ $ satisfying (1) and (2). If no such $ m, n $ exist, output $-1$. From (1) and (2): $$ x = \frac{h - m a}{m + 1} = \frac{w - n a}{n + 1} $$ Thus, we require: $$ \frac{h - m a}{m + 1} = \frac{w - n a}{n + 1} \geq 0 $$ Which implies: $$ h \geq m a, \quad w \geq n a, \quad \text{and} \quad \frac{h - m a}{m + 1} = \frac{w - n a}{n + 1} $$ Rewriting: $$ (h - m a)(n + 1) = (w - n a)(m + 1) $$ We seek to minimize $ x = \frac{h - m a}{m + 1} $ over all $ m, n \in \mathbb{Z}^+ $ satisfying the above, or return $-1$ if none exist.

Samples

Input #1

2 18 13

Output #1

0.5

Input #2

4 4 4

Output #2

Input #3

3 4 3

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "G. Perfectionist Arkadiy",
    "description": {
      "content": "Arkadiy has lots square photos with size _a_ × _a_. He wants to put some of them on a rectangular wall with size _h_ × _w_. The photos which Arkadiy will put on the wall must form a rectangular grid ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF795G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Arkadiy has lots square photos with size _a_ × _a_. He wants to put some of them on a rectangular wall with size _h_ × _w_.\n\nThe photos which Arkadiy will put on the wall must form a rectangular grid ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Arkadiy 有大量边长为 $a × a$ 的正方形照片。他想将其中一些贴在一面尺寸为 $h × w$ 的矩形墙上。\n\nArkadiy 贴在墙上的照片必须形成一个矩形网格，且相邻照片之间在垂直和水平方向上的间距，以及最外层照片行/列到墙边界的距离，都必须等于某个非负实数 $x$。请参考下图以更好地理解题意。\n\nArkadiy 尚未决定要贴多少张照片，但他至少要贴一张。你的任务是确定在满足所有约束...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ a, h, w \\in \\mathbb{Z}^+ $ be the side length of each square photo, and the height and width of the wall, respectively.  \nLet $ m, n \\in \\mathbb{Z}^+ $ be the number of rows an...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments