B. Mahmoud and a Triangle

Codeforces

IDCF766B

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsgeometrygreedymathnumber theorysortings

English · Original

Chinese · Translation

Formal · Original

Mahmoud has _n_ line segments, the _i_\-th of them has length _a__i_. Ehab challenged him to use **exactly 3** line segments to form a non-degenerate triangle. Mahmoud doesn't accept challenges unless he is sure he can win, so he asked you to tell him if he should accept the challenge. Given the lengths of the line segments, check if he can choose exactly 3 of them to form a non-degenerate triangle. Mahmoud should use exactly 3 line segments, he can't concatenate two line segments or change any length. A non-degenerate triangle is a triangle with positive area. ## Input The first line contains single integer _n_ (3 ≤ _n_ ≤ 105) — the number of line segments Mahmoud has. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — the lengths of line segments Mahmoud has. ## Output In the only line print "_YES_" if he can choose exactly three line segments and form a non-degenerate triangle with them, and "_NO_" otherwise. [samples] ## Note For the first example, he can use line segments with lengths 2, 4 and 5 to form a non-degenerate triangle.

Mahmoud 有 #cf_span[n] 条线段，第 #cf_span[i] 条线段的长度为 #cf_span[ai]。Ehab 挑战他使用 *恰好 #cf_span[3]* 条线段组成一个非退化三角形。Mahmoud 只有在确信自己能赢时才会接受挑战，因此他请你告诉他是否应该接受这个挑战。给定线段的长度，请判断他是否能选出恰好 #cf_span[3] 条线段组成一个非退化三角形。 Mahmoud 必须使用恰好 #cf_span[3] 条线段，他不能将两条线段拼接，也不能改变任何长度。非退化三角形是指面积为正的三角形。第一行包含一个整数 #cf_span[n] (#cf_span[3 ≤ n ≤ 105]) —— Mahmoud 拥有的线段数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 109]) —— Mahmoud 拥有的线段长度。仅在一行中输出 "_YES_"（如果他能选出恰好三条线段组成一个非退化三角形），否则输出 "_NO_"。在第一个示例中，他可以使用长度为 #cf_span[2]、#cf_span[4] 和 #cf_span[5] 的线段组成一个非退化三角形。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[3 ≤ n ≤ 105]) —— Mahmoud 拥有的线段数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 109]) —— Mahmoud 拥有的线段长度。 ## Output 仅在一行中输出 "_YES_"（如果他能选出恰好三条线段组成一个非退化三角形），否则输出 "_NO_"。 [samples] ## Note 在第一个示例中，他可以使用长度为 #cf_span[2]、#cf_span[4] 和 #cf_span[5] 的线段组成一个非退化三角形。

Given a set of $ n $ positive integers $ a_1, a_2, \dots, a_n $ with $ 3 \leq n \leq 10^5 $ and $ 1 \leq a_i \leq 10^9 $, determine whether there exist three distinct indices $ i, j, k $ such that the three corresponding lengths $ a_i, a_j, a_k $ can form a non-degenerate triangle. A non-degenerate triangle with side lengths $ x, y, z $ satisfies the triangle inequality: $$ x + y > z, \quad x + z > y, \quad y + z > x. $$ Equivalently, if the three lengths are sorted such that $ x \leq y \leq z $, then the necessary and sufficient condition is: $$ x + y > z. $$ **Objective:** Determine if there exists a triplet $ (a_i, a_j, a_k) $ such that, when sorted as $ x \leq y \leq z $, we have $ x + y > z $. **Output:** Print "YES" if such a triplet exists; otherwise, print "NO".

Samples

Input #1

5
1 5 3 2 4

Output #1

YES

Input #2

3
4 1 2

Output #2

NO

API Response (JSON)

{
  "problem": {
    "name": "B. Mahmoud and a Triangle",
    "description": {
      "content": "Mahmoud has _n_ line segments, the _i_\\-th of them has length _a__i_. Ehab challenged him to use **exactly 3** line segments to form a non-degenerate triangle. Mahmoud doesn't accept challenges unless",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF766B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mahmoud has _n_ line segments, the _i_\\-th of them has length _a__i_. Ehab challenged him to use **exactly 3** line segments to form a non-degenerate triangle. Mahmoud doesn't accept challenges unless...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Mahmoud 有 #cf_span[n] 条线段，第 #cf_span[i] 条线段的长度为 #cf_span[ai]。Ehab 挑战他使用 *恰好 #cf_span[3]* 条线段组成一个非退化三角形。Mahmoud 只有在确信自己能赢时才会接受挑战，因此他请你告诉他是否应该接受这个挑战。给定线段的长度，请判断他是否能选出恰好 #cf_span[3] 条线段组成一个非退化三角形。\n\nMahmo...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given a set of $ n $ positive integers $ a_1, a_2, \\dots, a_n $ with $ 3 \\leq n \\leq 10^5 $ and $ 1 \\leq a_i \\leq 10^9 $, determine whether there exist three distinct indices $ i, j, k $ such that the...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments