S3. Common Card Choice
레이팅 미적용의견: 0
There are \(N\) cards with positive
integers written on them. Alice takes some of the cards, then Bob takes
some of the remaining cards. Both need to take at least one card; Alice
is not allowed to take all of the cards. Then Alice and Bob compute the
sum of numbers on the cards that they have taken. If these sums have a
common divisor greater than one, Alice and Bob get a bag of sweets;
otherwise they don’t. Given the cards on the table, determine if it is
possible for Alice and Bob to get the sweets, and if so, how.
To make it even more challenging, in some cases, neither Alice nor
Bob knows any of the values on the cards.
Note that an integer \(d\) is a
divisor of an integer \(q\) if
there is no remainder when \(q\) is
divided by \(d\). An integer \(z\) is a common divisor of
integers \(x\) and \(y\) if \(z\) is a divisor of both \(x\) and \(y\).
\(N~(2 \le N \le 10^{5})\)
\(c_i~(1 \le c_i \le 10^{12})\)
The first line of input contains \(N~(2 \le N \le 10^{5})\).
The second line contains \(N\)
integers, \(c_i~(1 \le c_i \le 10^{12})\).
Note: For the last subtask, you will be given \(N\), but all \(N\) card values will be labelled with
-1, indicating that those card values are unknown to you.
In this last subtask, there will always be a selection of cards that
Alice and Bob can pick to obtain a bag of sweets.
On the first line of output, print YES if it is possible
to get the sweets, otherwise, print NO.
If the answer is YES, on the second line of output,
produce \(A\), the number of cards that
Alice should take, followed by one space, followed by \(B\), the number of cards that Bob should
take. On the third line of output, print out \(A\) space-separated numbers corresponding
to the indices of the cards that Alice should take. On the fourth line
of output, print out \(B\)
space-separated numbers corresponding to the indices of the cards that
Bob should take. If there are several ways to select cards, print any of
them.
If the input is for the last subtask, output an integer \(K\leq 100\) on the first line, followed by
\(K\) possible combinations of output
as specified for all other subtasks. That is, each combination will be
the same sequence of three lines as stated above: one line containing
\(A\) and \(B\); one line containing \(A\) indices of cards; and one line
containing \(B\) indices of cards. All
guesses of indices of cards must be disjoint: that is, no card index can
appear in more than one guess. Your output will be judged correct if any
of the combinations would result in Alice and Bob obtaining a bag of
sweets. Note that you will not receive any feedback between guesses.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 14점 | \(2 \le N \le 3\) — \(1 \le c_i \le 100\) |
2 | 6점 | \(2 \le N \le 10\) — \(1 \le c_i \le 100\) |
3 | 6점 | \(2 \leq N \le 10^5\) — \(1 \le c_i \le 2\) |
4 | 14점 | \(2 \leq N \le 10^5\) — \(1 \le c_i \le 10^5\) |
5 | 13점 | \(2 \leq N \le 10^{5}\) — \(1 \le c_i \le 10^{12}\) |
6 | 47점 | \(N = 10^5\) — \(c_i=-1\) and see Note below |
7
19 7 11 31 99 13 17YES
3 3
2 3 7
4 6 1The sum of Alice’s cards is (7+11+17=35) and the sum of Bob’s cards is
(31+13+19=63), and both (35) and (63) are divisible by (7).
3
3 11 17NONotice that (3), (11), and (17) have no common divisors, and all
possible sums of two of these numbers ((14), (20), (28)) do not have a common factor with the
remaining third number.
100000
-1 -1 -1 ...2
1 2
1
3 5
3 2
100 101 102
201 200There are a total of two guesses. The first guess consists of indices
({1}) and ({3,5}). The second guess consists of
indices ({100,101,102}) and ({201,200}).
Note that all sets of indices are disjoint.
Although the output is formatted correctly, the output will receive
Wrong answer because the two guesses are not enough for
Alice and Bob to obtain a bag of sweets.
평가 및 의견
S3. Common Card Choice
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
S3. Common Card Choice