I. Домики

Codeforces

IDCF10144I

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Маленький Леша очень любит рисовать домики. Он готов часами рисовать домики разных форм и размеров. Как-то раз Леша попал на одну Очень Серьезную Олимпиаду. Чтобы справиться с волнением, он решил прибегнуть к любимому занятию и нарисовать много-много домиков. Леша считает, что множество из шести отрезков образует домик, если можно выбрать три из них так, что они образуют равнобедренный треугольник, а из оставшихся трех отрезков и основания треугольника можно составить прямоугольник (смотри рисунок). У Леши в запасе есть множество отрезков, пронумерованных от 1 до n. Лешу очень интересует, сколькими способами можно выбрать шесть отрезков из множества таким образом, чтобы из них можно было составить домик. Две шестерки отрезков считаются различными, если в одной из шестерок найдется отрезок, которого нет в другой шестерке. В первой строке дано целое число n (6 ≤ n ≤ 105) – количество отрезков. Во второй строке даны n целых чисел ai через пробел – длины отрезков (1 ≤ ai ≤ 109). Выведите единственное число – ответ на задачу. Так как Леша еще маленький и боится больших чисел, ответ нужно вывести по модулю 109 + 9. ## Входные Данные В первой строке дано целое число n (6 ≤ n ≤ 105) – количество отрезков. Во второй строке даны n целых чисел ai через пробел – длины отрезков (1 ≤ ai ≤ 109). ## Выходные Данные Выведите единственное число – ответ на задачу. Так как Леша еще маленький и боится больших чисел, ответ нужно вывести по модулю 109 + 9. ## Примеры Входные данные61 1 1 1 1 1Выходные данные1Входные данные71 1 1 1 1 2 2Выходные данные5 [samples]

**Definitions** Let $ P $ be a strictly convex polygon with $ n $ vertices, given in clockwise order by coordinates $ (x_i, y_i) \in \mathbb{Z}^2 $, $ i = 1, \dots, n $, where $ 3 \leq n \leq 100 $. **Constraints** 1. $ P $ is strictly convex: all interior angles $ < \pi $, and no three vertices are collinear. 2. The polygon is simple and closed. **Objective** Determine whether $ P $ can be partitioned into exactly 2017 parallelograms, each with non-zero area, such that their union is $ P $ and their interiors are pairwise disjoint.

API Response (JSON)

{
  "problem": {
    "name": "I. Домики",
    "description": {
      "content": "Маленький Леша очень любит рисовать домики. Он готов часами рисовать домики разных форм и размеров. Как-то раз Леша попал на одну Очень Серьезную Олимпиаду. Чтобы справиться с волнением, он решил приб",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10144I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Маленький Леша очень любит рисовать домики. Он готов часами рисовать домики разных форм и размеров. Как-то раз Леша попал на одну Очень Серьезную Олимпиаду. Чтобы справиться с волнением, он решил приб...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ P $ be a strictly convex polygon with $ n $ vertices, given in clockwise order by coordinates $ (x_i, y_i) \\in \\mathbb{Z}^2 $, $ i = 1, \\dots, n $, where $ 3 \\leq n \\leq 100 $....",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments