2014 Mock CCC by Alex and Timothy
Alice had recently pursued her (not so) secret love interest, Bob, on a long roadtrip to see just who he was meeting in another town. To her dismay, she learned that Bob was getting back together with one of his ex-girlfriends. As she made the discovery, her body convulsed with rage, the sky spun around her head, and the ground trembled under her feet. One thing led to another; before you know it, Bob has found himself tied up and gagged in Alice's basement. Because Bob is a computer scientist, Alice stands before him offering him only two options — play the Elimination Game with her, or prepare to be eliminated. If she can't have him, nobody can!
To play the Elimination Game, Alice presents Bob with two piles of
cards — a pile of black cards and a pile of
white cards
. Every card has a positive integer no greater than
written on it. The rules of the game are as follows:
- Bob picks two cards — one from the black pile and one from the white
pile, such that the numbers on both cards share a factor greater
than
.
- The two cards are eliminated from their respective piles.
- Bob repeats this process until there are no more pairs that can be eliminated.
- The objective is to eliminate as many cards as possible.
Using many days and nights of computational power from a supercomputer, Alice has obtained the maximum (total) number of cards that can be eliminated from the two piles under these rules. If Bob finds this number, then he is free to go. Otherwise, he himself will be forever "eliminated" by the crazed, lust-driven Alice. Write a program that helps Bob escape!
Scoring
Bob immediately comes up with a strategy. He decides to start at the
beginning of the black cards and go through them one by one. For each
card in the black pile, he goes through all of the (non-eliminated)
cards in the white pile from beginning to end. If at any one point the
two cards he's examining can be eliminated, he eliminates them and moves
on to the next black card. If no white cards share a factor greater than
with the black card, he then skips to the next black card. Clearly,
this strategy is not perfect and will not always lead to the correct
answer. However, implementing it efficiently will get you at least
of the points.
On an unrelated note:
- For test cases worth
of the points:
,
.
- For test cases worth
of the points:
,
.
Input Specification
Line of input contains the two integers
and
.
Line contains
integers, the values of the black cards.
Line contains
integers, the values of the white cards.
Output Specification
The output should contain one integer, the maximum total number of cards that can be eliminated from the piles.
Sample Input
5 5
3 10 6 7 17
3 5 14 4 15
Sample Output
8
Explanation
One way to eliminate of the
cards is to eliminate the pairs
,
,
, and
, with
left over in the black pile and
left over in the white pile. Another way is to eliminate the pairs
,
,
, and
, with
left over from the black pile
and
left over from the white pile. We know that it's not possible to
eliminate all
cards because we cannot eliminate
, since it does not
share factors greater than
with any other number except for itself
(and there are no
's in the white pile). Therefore,
is the most we
can eliminate.
Comments