A. Fraction

Codeforces

IDCF854A

Time1000ms

Memory512MB

Difficulty—

brute forceconstructive algorithmsmath

English · Original

Chinese · Translation

Formal · Original

Petya is a big fan of mathematics, especially its part related to fractions. Recently he learned that a fraction is called _proper_ iff its numerator is smaller than its denominator (_a_ < _b_) and that the fraction is called _irreducible_ if its numerator and its denominator are coprime (they do not have positive common divisors except 1). During his free time, Petya thinks about proper irreducible fractions and converts them to decimals using the calculator. One day he mistakenly pressed addition button ( + ) instead of division button (÷) and got sum of numerator and denominator that was equal to _n_ instead of the expected decimal notation. Petya wanted to restore the original fraction, but soon he realized that it might not be done uniquely. That's why he decided to determine maximum possible proper irreducible fraction such that sum of its numerator and denominator equals _n_. Help Petya deal with this problem. ## Input In the only line of input there is an integer _n_ (3 ≤ _n_ ≤ 1000), the sum of numerator and denominator of the fraction. ## Output Output two space-separated positive integers _a_ and _b_, numerator and denominator of the maximum possible proper irreducible fraction satisfying the given sum. [samples]

Petya 非常热爱数学，尤其是与分数相关的部分。最近他了解到，一个分数被称为 _真分数_ 当且仅当其分子小于分母（#cf_span[a < b]），并且当分子与分母互质（它们除了 #cf_span[1] 外没有正的公因数）时，该分数被称为 _最简分数_。在空闲时间，Petya 思考真最简分数，并使用计算器将它们转换为小数。一天，他错误地按下了加法按钮（#cf_span[ + ]）而不是除法按钮（#cf_span[÷]），得到了分子与分母的和等于 #cf_span[n]，而不是预期的小数表示。 Petya 希望还原原始的分数，但很快他意识到这可能不是唯一的。因此，他决定找出满足分子与分母之和等于 #cf_span[n] 的最大可能的真最简分数。请帮助 Petya 解决这个问题。输入中仅有一行包含一个整数 #cf_span[n]（#cf_span[3 ≤ n ≤ 1000]），即分数的分子与分母之和。请输出两个用空格分隔的正整数 #cf_span[a] 和 #cf_span[b]，表示满足给定和的最大可能的真最简分数的分子和分母。 ## Input 在输入的唯一一行中给出一个整数 #cf_span[n]（#cf_span[3 ≤ n ≤ 1000]），即分数的分子与分母之和。 ## Output 请输出两个用空格分隔的正整数 #cf_span[a] 和 #cf_span[b]，表示满足给定和的最大可能的真最简分数的分子和分母。 [samples]

Given: - Integer $ n $, where $ 3 \leq n \leq 1000 $. - Find positive integers $ a, b $ such that: 1. $ a + b = n $, 2. $ a < b $ (proper fraction), 3. $ \gcd(a, b) = 1 $ (irreducible), 4. $ \frac{a}{b} $ is maximized. Objective: Maximize $ \frac{a}{b} $ subject to the above constraints. Since $ a + b = n $, we have $ b = n - a $, so $ \frac{a}{b} = \frac{a}{n - a} $. To maximize $ \frac{a}{n - a} $, we maximize $ a $ under the constraints: - $ a < n - a \Rightarrow a < \frac{n}{2} $, - $ \gcd(a, n - a) = 1 \Rightarrow \gcd(a, n) = 1 $ (since $ \gcd(a, n - a) = \gcd(a, n) $). Thus, find the largest integer $ a < \frac{n}{2} $ such that $ \gcd(a, n) = 1 $. Then set $ b = n - a $. Output: $ a $ and $ b $.

Samples

Input #1

Output #1

1 2

Input #2

Output #2

1 3

Input #3

Output #3

5 7

API Response (JSON)

{
  "problem": {
    "name": "A. Fraction",
    "description": {
      "content": "Petya is a big fan of mathematics, especially its part related to fractions. Recently he learned that a fraction is called _proper_ iff its numerator is smaller than its denominator (_a_ < _b_) and th",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF854A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Petya is a big fan of mathematics, especially its part related to fractions. Recently he learned that a fraction is called _proper_ iff its numerator is smaller than its denominator (_a_ < _b_) and th...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Petya 非常热爱数学，尤其是与分数相关的部分。最近他了解到，一个分数被称为 _真分数_ 当且仅当其分子小于分母（#cf_span[a < b]），并且当分子与分母互质（它们除了 #cf_span[1] 外没有正的公因数）时，该分数被称为 _最简分数_。\n\n在空闲时间，Petya 思考真最简分数，并使用计算器将它们转换为小数。一天，他错误地按下了加法按钮（#cf_span[ + ]）而不是除法按...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given:  \n- Integer $ n $, where $ 3 \\leq n \\leq 1000 $.  \n- Find positive integers $ a, b $ such that:  \n  1. $ a + b = n $,  \n  2. $ a < b $ (proper fraction),  \n  3. $ \\gcd(a, b) = 1 $ (irreducible)...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments