AlgoLensArena
ContestlərProblemlərOtaqlar
Vizualizator
← Məsələlər

DAPC21-037.Jack the Mole

Medium · 1 s · 256 MB

  • icpc
  • dapc
  • 2021

The spy agency you are employed by (When your family members ask, please lie to them and say you work as a computer programmer.) has sent you and some fellow spies on an important mission deep in the jungles of Luxembourg. Your colleagues and you are currently waiting on an abandoned and overgrown airstrip, about to be picked up by the finest spy plane the Dutch bureaucracy can buy.

However, an urgent communication from the HQ has just come in to inform you counterintelligence has learned that during the mission, an infamous counter-spy called Jack the Mole was planted among you! You do a headcount and to your horror realize that while you started the mission with n−1n-1n−1 people, there are now nnn! (Exclamation point, not factorial.) Since you all take Covid regulations very seriously, you all wore masks, so it is not obvious who the imposter is.

Then you remember: the finest spy plane in question is thrown off balance rather easily, so the agency picked the n−1n-1n−1 agents so that it is possible to divide them into two groups of equal weight, but not necessarily of equal size, for the left and the right side of the plane respectively. However, it did not specify exactly which two groups (anonymity and all that). Of course you have a scale with you (doesn't any good spy?), so you can find which of the nnn people on the mission is potentially the mole.

Giriş formatı

The input consists of:

• One line containing the number of spies present, nnn (3≤n≤3003 \leq n \leq 3003≤n≤300).

• One line containing nnn space separated integers w1,…,wnw_1, \ldots, w_nw1​,…,wn​ (1≤wi≤10001\leq w_{i} \leq 10001≤wi​≤1000), the iiith of which gives the weight of the iiith spy in kilograms (If those ranges seem odd, recall spies can be very muscular or very nimble.).

Çıxış formatı

Output a single number kkk, the number of spies that are potentially the mole, followed by kkk integers, the suspects, in increasing order.

Qeyd

Source: Delft Algorithm Programming Contest 2021 · Author: Pim Spelier · License: CC BY-SA 4.0 · Original: https://dapc.wisv.ch · Statement adapted for AlgoLens and shared under the same license.

Nümunələr

Giriş #1

3
1 1 2

Çıxış #1

1
3

Giriş #2

3
1 1 1

Çıxış #2

3
1 2 3

Giriş #3

5
2 1 3 4 2

Çıxış #3

3
1 4 5

Giriş #4

5
1 1 1 3 1

Çıxış #4

5
1 2 3 4 5

Giriş #5

4
2 1 5 3

Çıxış #5

2
2 3