J. Triangles

Codeforces

IDCF10048J

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Tom has just found out that he can’t make a triangle using three line segments of lengths 1, 2 and 5. He has lots of different line segments and wants to know how many different triangles he can make. The triangles are different if the sets of their line segments’ lengths are different. The first line contains the number of test cases _T_ (T ≤ 50). The first line of each test case contains the number of segments _N_ (N ≤ 100). The second line of each test case contains _N_ integers ai separated by spaces, ai is the length of _i_-th line segment (1 ≤ ai ≤ 105). For each test case output one line containing “_Case #tc: num_”, where _tc_ is the number of the test case (starting from 1) and _num_ is the number of distinct triangles Tom can make. ## Input The first line contains the number of test cases _T_ (T ≤ 50). The first line of each test case contains the number of segments _N_ (N ≤ 100). The second line of each test case contains _N_ integers ai separated by spaces, ai is the length of _i_-th line segment (1 ≤ ai ≤ 105). ## Output For each test case output one line containing “_Case #tc: num_”, where _tc_ is the number of the test case (starting from 1) and _num_ is the number of distinct triangles Tom can make. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ N_k \in \mathbb{Z} $ denote the number of line segments. - Let $ A_k = (a_{k,1}, a_{k,2}, \dots, a_{k,N_k}) $ be a multiset of positive integers representing segment lengths. **Constraints** 1. $ 1 \le T \le 50 $ 2. For each $ k \in \{1, \dots, T\} $: - $ 1 \le N_k \le 100 $ - $ 1 \le a_{k,i} \le 10^5 $ for all $ i \in \{1, \dots, N_k\} $ **Objective** For each test case $ k $, compute the number of distinct unordered triples $ \{x, y, z\} \subseteq A_k $ with $ x \le y \le z $ such that the triangle inequality holds: $$ x + y > z $$

API Response (JSON)

{
  "problem": {
    "name": "J. Triangles",
    "description": {
      "content": "Tom has just found out that he can’t make a triangle using three line segments of lengths 1, 2 and 5. He has lots of different line segments and wants to know how many different triangles he can make.",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10048J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Tom has just found out that he can’t make a triangle using three line segments of lengths 1, 2 and 5. He has lots of different line segments and wants to know how many different triangles he can make....",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ N_k \\in \\mathbb{Z} $ denote the number of line segments.  \n- Let $ A_k...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments