Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1104
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1104
Exchanging Cards
Maratona de Programação da SBC 
Brazil
Timelimit: 1
Alice and Betty collect Pok´mon cards. The cards are printed for a game that imitates the 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 a 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 ≤ 104 and 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.
| Input Sample | Output Sample |
|
1 1 |
0 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <string.h>
#define true 1
#define false 0
#define MAXSIZE 100101
typedef struct Cartas{
_Bool alice;
_Bool beatriz;
} Cartas;
Cartas cartas[MAXSIZE];
int main ()
{
unsigned i, tmp;
unsigned alice, beatriz;
while (scanf("%u %u", &alice, &beatriz), alice)
{
memset(cartas, false, sizeof(cartas));
for (i = 0; i < alice; ++i)
scanf("%u", &tmp), cartas[tmp].alice = true;
for (i = 0; i < beatriz; ++i)
scanf("%u", &tmp), cartas[tmp].beatriz = true;
alice = beatriz = 0;
for (i = 0; i < MAXSIZE; ++i)
{
if (cartas[i].alice && !cartas[i].beatriz)
++alice;
if (!cartas[i].alice && cartas[i].beatriz)
++beatriz;
}
printf("%d\n", beatriz > alice ? alice : beatriz);
}
}
Input
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
Output
3
4
#2 Code Example with C++ Programming
Code -
C++ Programming
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b;
while(cin >> a >> b)
{
if(a == 0 && b == 0)
break;
set < int> x;
set<int> y;
for(int i = 0; i < a; i++)
{
int c;
cin >> c;
x.insert(c);
}
for(int i = 0; i < b; i++)
{
int c;
cin >> c;
y.insert(c);
}
vector<int> num1;
set < int>::iterator it1;
for(it1 = x.begin();it1 != x.end(); it1++)
num1.push_back(*it1);
vector<int> num2;
set < int>::iterator it2;
for(it2 = y.begin(); it2 != y.end(); it2++)
num2.push_back(*it2);
int min1=0,min2=0;
for(int i = 0; i < num1.size(); i++)
{
bool check=false;
for(int j = 0; j < num2.size(); j++)
{
if(num1[i] == num2[j])
{
check = true;
min2++;
break;
}
}
if(!check)
min1++;
}
min2 = num2.size()-min2;
cout << min(min1,min2) << endl;
}
return 0;
}
Input
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
Output
3
4
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(System.out);
public static void main(String[] args) throws Exception {
String l;
int cards1, cards2;
while (!(l = in.readLine()).equals("0 0")) {
Set < String> c1 = new HashSet<>(Arrays.asList(in.readLine().split("\\s")));
Set c2 = new HashSet<>(Arrays.asList(in.readLine().split("\\s")));
cards1 = 0;
cards2 = 0;
for (Iterator < String> iterator = c1.iterator(); iterator.hasNext();) {
String a = iterator.next();
cards1 += (!c2.contains(a) ? 1 : 0);
}
for (Iterator < String> iterator = c2.iterator(); iterator.hasNext();) {
cards2 += (!c1.contains(iterator.next()) ? 1 : 0);
}
out.println(cards1 > cards2 ? cards2 : cards1);
}
out.close();
}
}
Input
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
Output
3
4
#4 Code Example with Python Programming
Code -
Python Programming
while True:
a, b = input().split()
if a == b == '0':
break
fa = [int(x) for x in input().split()]
fb = [int(x) for x in input().split()]
a = set(fa)
b = set(fb)
c = b
f = 0
if len(a) < len(b):
c = a
a = b
c = [x for x in c if x not in a]
print(len(c))
Input
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
Output
3
4