[URI Online Judge] – 1104 – Exchanging Cards

Alice and Betty collect Pok´mon cards. The cards are printed for a game that imitates the e battle system of one of the most popular videogames in history, but Alice and Betty are too young to actually play the game, and are only interested in the actual cards. To make it easier, we\’ll assume each card has an unique identifier, given as an integer number.

Both girls have a set of cards, and, like most girls their age, like to trade the cards they have. They obviously don\’t care about identical cards they both have, and they don\’t want to receive repeated cards in the trade. Besides, the cards are traded in a single operation: Alice gives Betty N distinct cards and receives back other N distinct cards.

The girls want to know what is the maximum number of cards they can trade. For instance, if Alice has cards {1, 1, 2, 3, 5, 7, 8, 8, 9, 15} and Betty has cards {2, 2, 2, 3, 4, 6, 10, 11, 11}, they can trade at most four cards.

Write a program that given the sets of cards owned by Alice and Betty, determines the maximum number of cards they can trade.

Input

The input contains several test cases. The first line of a test case contains two integers A and B, separated by a blank space, indicating respectively the number of cards Alice and Betty have (1 ≤ A ≤ 104and 1 ≤ B ≤ 104). The second line contains A space-separated integers Xi, each indicating one of Alice\’s cards(1 ≤ Xi ≤ 105). The third line contains B integers Yi separated by whitespaces, each number indicating one of Betty\’s cards(1 ≤ Yi ≤ 105). Alice and Betty\’s cards are listed in non-descending order.

The end of input is indicated by a line containing only two zeros, separated by a blank space.

Output

For each test case, your program should print a single line, containing an integer number, indicating the maximum number of cards Alice and Betty can trade.

Sample Input Sample Output
1 1
1000
1000
3 4
1 3 5
2 4 6 8
10 9
1 1 2 3 5 7 8 8 9 15
2 2 2 3 4 6 10 11 11
0 0
0
3
4

My solution:

#include <cstdio>
#include <set>
#include <algorithm>

using namespace std;

int main() {
int a, b, aux;

while (scanf(“%d %d”, &a, &b) && a && b) {

set<int> cards_a;
set<int> cards_b;
set<int> cards_b_not_in_a;
set<int> cards_a_not_in_b;

while (a–) {
scanf(“%d”, &aux);
cards_a.insert(aux);
}

set<int>::iterator it_a = cards_a.begin();

while (b–) {
scanf(“%d”, &aux);

cards_b.insert(aux);

while (*it_a < aux && it_a != cards_a.end()) ++it_a;

if (it_a == cards_a.end() || *it_a != aux){
cards_b_not_in_a.insert(aux);
}
}

set<int>::iterator it_b = cards_b.begin();

for (it_a = cards_a.begin(); it_a != cards_a.end(); ++it_a) {
while (*it_b < *it_a && it_b != cards_b.end()) ++it_b;

if (it_b == cards_b.end() || *it_b != *it_a){
cards_a_not_in_b.insert(*it_a);
}
}

if (cards_a_not_in_b.size() < cards_b_not_in_a.size()) {
printf(“%d\n”, cards_a_not_in_b.size());
} else {
printf(“%d\n”, cards_b_not_in_a.size());
}
}

return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s