2014 Mock CCC by Alex and Timothy

Problem S5: Elimination Game

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 N black cards and a pile of M white cards (1 ≤ N, M ≤ 100). Every card has a positive integer no greater than 100 000 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 1.
• 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 1 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 5/15 of the points.

On an unrelated note:

• For test cases worth 5/15 of the points: N, M ≤ 5.
• For test cases worth 10/15 of the points: N, M ≤ 10.

Input Format

Line 1 of input contains the two integers N and M.
Line 2 contains N integers, the values of the black cards.
Line 3 contains M integers, the values of the white cards.

Output Format

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 elimate 8 of the 10 cards is to eliminate the pairs (3, 3), (10, 5), (6, 4), and (7, 14), with 17 left over in the black pile and 15 left over in the white pile. Another way is to eliminate the pairs (3, 15), (10, 5), (6, 3), and (7, 14), with 17 left over from the black pile and 4 left over from the white pile. We know that it's not possible to eliminate all 10 cards because we cannot eliminate 17, since it does not share factors greater than 1 with any other number except for itself (and there are no 17's in the white pile). Therefore, 8 is the most we can eliminate.

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 27, 2014
Authors: FatalEagle, Alex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)