A. Balloons

Codeforces

IDCF998A

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsimplementation

English · Original

Chinese · Translation

Formal · Original

There are quite a lot of ways to have fun with inflatable balloons. For example, you can fill them with water and see what happens. Grigory and Andrew have the same opinion. So, once upon a time, they went to the shop and bought $n$ packets with inflatable balloons, where $i$\-th of them has exactly $a_i$ balloons inside. They want to divide the balloons among themselves. In addition, there are several conditions to hold: * Do not rip the packets (both Grigory and Andrew should get unbroken packets); * Distribute all packets (every packet should be given to someone); * Give both Grigory and Andrew at least one packet; * To provide more fun, the total number of balloons in Grigory's packets should not be equal to the total number of balloons in Andrew's packets. Help them to divide the balloons or determine that it's impossible under these conditions. ## Input The first line of input contains a single integer $n$ ($1 \le n \le 10$) — the number of packets with balloons. The second line contains $n$ integers: $a_1$, $a_2$, $\ldots$, $a_n$ ($1 \le a_i \le 1000$) — the number of balloons inside the corresponding packet. ## Output If it's impossible to divide the balloons satisfying the conditions above, print $-1$. Otherwise, print an integer $k$ — the number of packets to give to Grigory followed by $k$ distinct integers from $1$ to $n$ — the indices of those. The order of packets doesn't matter. If there are multiple ways to divide balloons, output any of them. [samples] ## Note In the first test Grigory gets $3$ balloons in total while Andrey gets $1$. In the second test there's only one way to divide the packets which leads to equal numbers of balloons. In the third test one of the boys won't get a packet at all.

有非常多的方式可以和充气气球玩得开心。例如，你可以给它们装满水，然后看会发生什么。 Grigory 和 Andrew 有同样的想法。因此，有一天，他们去商店买了 $n$ 包充气气球，其中第 $i$ 包恰好有 $a_i$ 个气球。他们希望将这些气球分给自己。此外，还需要满足以下条件：请帮助他们分配气球，或判断在这些条件下是否不可能实现。输入的第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10$) —— 气球包的数量。第二行包含 $n$ 个整数：$a_1$, $a_2$, $dots.h$, $a_n$ ($1 lt.eq a_i lt.eq 1000$) —— 每个包中气球的数量。如果无法在满足上述条件的情况下分配气球，请输出 $-1$。否则，请输出一个整数 $k$ —— 给 Grigory 的包的数量，接着输出 $k$ 个从 $1$ 到 $n$ 的不同整数 —— 这些包的编号。包的顺序无关紧要。如果有多种分配方式，输出任意一种即可。在第一个测试用例中，Grigory 总共得到 $3$ 个气球，而 Andrey 得到 $1$ 个。在第二个测试用例中，只有一种分配方式能使两人得到的气球数量相等。在第三个测试用例中，其中一个男孩将得不到任何包。 ## Input 输入的第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10$) —— 气球包的数量。第二行包含 $n$ 个整数：$a_1$, $a_2$, $dots.h$, $a_n$ ($1 lt.eq a_i lt.eq 1000$) —— 每个包中气球的数量。 ## Output 如果无法在满足上述条件的情况下分配气球，请输出 $-1$。否则，请输出一个整数 $k$ —— 给 Grigory 的包的数量，接着输出 $k$ 个从 $1$ 到 $n$ 的不同整数 —— 这些包的编号。包的顺序无关紧要。如果有多种分配方式，输出任意一种即可。 [samples] ## Note 在第一个测试用例中，Grigory 总共得到 $3$ 个气球，而 Andrey 得到 $1$ 个。在第二个测试用例中，只有一种分配方式能使两人得到的气球数量相等。在第三个测试用例中，其中一个男孩将得不到任何包。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of packets. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers, where $ a_i $ is the number of balloons in packet $ i $. Let $ G \subseteq \{1, 2, \dots, n\} $ be the set of packet indices given to Grigory. Let $ A = \{1, 2, \dots, n\} \setminus G $ be the set of packet indices given to Andrew. **Constraints** 1. $ 1 \leq n \leq 10 $ 2. $ 1 \leq a_i \leq 1000 $ for all $ i \in \{1, \dots, n\} $ 3. The total number of balloons given to Grigory equals that given to Andrew: $$ \sum_{i \in G} a_i = \sum_{j \in A} a_j $$ **Objective** Find a subset $ G \subseteq \{1, \dots, n\} $ such that $$ \sum_{i \in G} a_i = \frac{1}{2} \sum_{i=1}^{n} a_i $$ If such a $ G $ exists, output $ |G| $ and the elements of $ G $. If no such subset exists, output $ -1 $.

Samples

Input #1

3
1 2 1

Output #1

2
1 2

Input #2

2
5 5

Output #2

\-1

Input #3

1
10

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "A. Balloons",
    "description": {
      "content": "There are quite a lot of ways to have fun with inflatable balloons. For example, you can fill them with water and see what happens. Grigory and Andrew have the same opinion. So, once upon a time, the",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF998A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are quite a lot of ways to have fun with inflatable balloons. For example, you can fill them with water and see what happens.\n\nGrigory and Andrew have the same opinion. So, once upon a time, the...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "有非常多的方式可以和充气气球玩得开心。例如，你可以给它们装满水，然后看会发生什么。\n\nGrigory 和 Andrew 有同样的想法。因此，有一天，他们去商店买了 $n$ 包充气气球，其中第 $i$ 包恰好有 $a_i$ 个气球。\n\n他们希望将这些气球分给自己。此外，还需要满足以下条件：\n\n请帮助他们分配气球，或判断在这些条件下是否不可能实现。\n\n输入的第一行包含一个整数 $n$ ($1 lt.e...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of packets.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ a_i $ is the number of balloons in packet $ i $.  ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments