Cod sursa(job #1265422)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 17 noiembrie 2014 12:11:10
Problema Dtcsu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <cstdio>
using namespace std;

struct TRNode
{
	TRNode* p[2];
	TRNode()
	{
		p[0] = p[1] = NULL;
	}
};

TRNode* root;
int answer;
int n;

long long BISRead()
{
	long long aux;
	scanf("%lld",&aux);
	return aux;
}

void TRInsertNumber(long long x)
{
	TRNode* currentNode = root;
	for (int i=0;i<=63;i++)
	{
		int ctBit = x%2;
		if (currentNode -> p[ctBit] == NULL) currentNode -> p[ctBit] = new TRNode();
		currentNode = currentNode -> p[ctBit];
		x = (x >> 1);
	}
}

bool TRCheckNumber(long long x)
{
	TRNode* currentNode = root;
	for (int i=0;i<=63;i++)
	{
		int ctBit = x%2;
		if (currentNode -> p[ctBit] == NULL) return false;
		currentNode = currentNode -> p[ctBit];
		x = (x >> 1);
	}
	return true;
}

int main()
{
	freopen("dtcsu.in","r",stdin);
	freopen("dtcsu.out","w",stdout);
	
	root = new TRNode();
	
	for (int i=1;i <= 276997;i++)
	{
		TRInsertNumber(BISRead());
	}
	
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		if (TRCheckNumber(BISRead())) 
		{
			answer++;
		}
	}
	
	printf("%d\n",answer);
	return 0;
}