projecteuler/90.cpp at master · kart/projecteuler · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cassert>

using namespace std;

int powers[] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};

int bit_count(int N)
{
	int		count = 0;

	while (N != 0)
	{
		count += (N % 2 == 1);
		N /= 2;
	}
	return count;
}

int can_form(int N, int A[], int B[])
{
	int		units, tens;

	units = N % 10;
	tens = N / 10;
	if ((9 == units) || (6 == units)) units = -1;
	if ((9 == tens) || (6 == tens)) tens = -1;
	assert(!((units == -1) && (tens == -1)));
	if ((units != -1) && (tens != -1))
		return (A[tens] && B[units]) || (B[tens] && A[units]);
	else if (units == -1)
		return (A[tens] && (B[9] || B[6])) || (B[tens] && (A[9] || A[6]));
	else	// tens == -1
		return ((A[9] || A[6]) && B[units]) || ((B[9] || B[6]) && A[units]);

}

int ok(int A, int B)
{
	int	a[10], b[10];

	for (int i = 0; i < 10; i++)
	{
		a[i] = (1 << i) & A;
		b[i] = (1 << i) & B;
	}
	for (int i = 1; i <= 9; i++)
		if (!can_form(powers[i], a, b))
			return 0;
	return 1;
}

// Ans = 1217
int main()
{
	int		i, j, count = 0;

	for (i = 1; i <= 1024; i++)
	{
		if (6 != bit_count(i))
			continue;
		for (j = 1; j <= 1024; j++)
		{
			if (6 != bit_count(j))
				continue;
			if (ok(i, j))
				count++;
		}
	}
	cout << count / 2 << endl;
}