L. MaratonIME goes karting

Codeforces

IDCF10098L

Time1000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Once after a contest, the competitive programmers were sad because of bad results. Seeing the situation, Renzo, MaratonIME's coach, suggested they should do something fun to relax. After a big discussion, they decided to go karting. Looking for a place that was viable to all students, they found Kartforces, a kart track near Cidade Universitária. However, the track was too small and only fitted two racers by race. As passionate competitive programmers, they organised a fair tournament where everyone raced against everyone, two by two, only once. In each race, the winner got one point on the scoreboard. Draws were allowed and no one scored in this case. The winner was the biggest scorer. There were N competitive programmers present and: You had access to the skills of all competitive programmers and now asks who was the champion. The first line consists on a single integer N, the number of competitive programmers. The second line contains N integers hi, the skill of the i - th competitive programmer. The output consists in a single integer i, the champion competitive programmer. If it's not possible to determine the champion, print - 1. ## Input The first line consists on a single integer N, the number of competitive programmers. The second line contains N integers hi, the skill of the i - th competitive programmer. 1 ≤ N ≤ 105 0 ≤ hi ≤ 109 ## Output The output consists in a single integer i, the champion competitive programmer. If it's not possible to determine the champion, print - 1. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ with $ 2 \leq n \leq 20 $ be the number of terms. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers with $ 1 \leq a_i \leq 10^8 $. Let $ s_i \in \{+1, -1\} $ denote the initial sign of term $ a_i $, where $ s_1 = +1 $ (first term is always positive), and for $ i \geq 2 $, $ s_i $ is determined by the operator before $ a_i $: $ + \mapsto +1 $, $ - \mapsto -1 $. **Constraints** The equation is of the form: $$ s_1 a_1 \pm a_2 \pm a_3 \pm \cdots \pm a_n = 0 $$ We may flip any subset of signs $ s_2, s_3, \dots, s_n $ (i.e., change $ + \leftrightarrow - $), but $ s_1 $ is fixed at $ +1 $. **Objective** Find the minimum number of sign flips among $ s_2, \dots, s_n $ such that: $$ \sum_{i=1}^n s_i' a_i = 0 $$ where $ s_1' = s_1 = +1 $, and $ s_i' \in \{+1, -1\} $ for $ i \geq 2 $. If no such assignment exists, output $ -1 $.

API Response (JSON)

{
  "problem": {
    "name": "L. MaratonIME goes karting",
    "description": {
      "content": "Once after a contest, the competitive programmers were sad because of bad results. Seeing the situation, Renzo, MaratonIME's coach, suggested they should do something fun to relax. After a big discuss",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10098L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Once after a contest, the competitive programmers were sad because of bad results. Seeing the situation, Renzo, MaratonIME's coach, suggested they should do something fun to relax. After a big discuss...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 20 $ be the number of terms.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ 1 \\leq a_i \\leq 10^8 $.  \nLet $ s_i \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments