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 people, there are now ! (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 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 people on the mission is potentially the mole.
Giriş formatı
The input consists of:
• One line containing the number of spies present, ().
• One line containing space separated integers (), the th of which gives the weight of the th spy in kilograms (If those ranges seem odd, recall spies can be very muscular or very nimble.).
Çıxış formatı
Output a single number , the number of spies that are potentially the mole, followed by 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