USACO 1.3.4 – Prime Cryptarithm

#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

int main() {
	ofstream fout("crypt1.out");
	ifstream fin("crypt1.in");

	int n, i, x, sol = 0, d, have[10] = { 0 }, t = 0, v[10];

	fin >> n >> x;
	for (i = 1; i <= n; fin >> x, i++)
		v[t++] = x, have[x] = true;

	for (int a1 = 0; a1 < n; a1++)
		for (int a2 = 0; a2 < n; a2++)
			for (int a3 = 0; a3 < n; a3++)
				for (int b1 = 0; b1 < n; b1++)
					for (int b2 = 0; b2 < n; b2++) {
						int a[3] = { v[a1], v[a2], v[a3] }, b[2] = { v[b1], v[b2] }, ans[2][3], carry = 0, valid = 1;

						for (int bi = 0; bi < 2; bi++, valid &= carry ==0)
							for (int ai = 0; ai < 3; ai++)
								ans[bi][ai] = a[ai]*b[bi] + carry, carry = ans[bi][ai]/10, ans[bi][ai]%=10, valid &= have[ans[bi][ai]];

						valid &= carry == 0;

						for (i = 0; i < 3; i++)
							d = (i==2? 0 : ans[0][i+1]) + ans[1][i] + carry, carry = d/10, d%=10, valid &= have[d];
						valid &= carry == 0;

						if (valid)
							sol++;
					}
	fout << sol << endl;
}
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

%d bloggers like this: