primecryptarithm - codetrick
X.
http://code.antonio081014.com/2012/09/usaco-prime-cryptarithm.html
for (int A:digits) {
for (int B:digits) {
for (int C:digits) {
for (int D:digits) {
for (int E:digits) {
int ABC = 100*A + 10*B + C;
int DE = 10*D + E;
if (val(ABC*D) && val(ABC*E) && val(ABC*DE) && String.valueOf(ABC*DE).length()==4 && String.valueOf(ABC*D).length()==String.valueOf(ABC*E).length() && String.valueOf(ABC*D).length()==3) {
System.out.print(ABC*DE+"\t");
count++;
}
}
}
}
}
}
http://jackneus.com/programming-archives/usaco-1-3-prime-cryptarithm/
Read full article from primecryptarithm - codetrick
The following cryptarithm is a multiplication problem that can be solved by substituting digits from a specified set of N digits into the positions marked with *. If the set of prime digits {2,3,5,7} is selected, the cryptarithm is called a PRIME CRYPTARITHM.
* * * x * * ------- * * * * * * ------- * * * *Digits can appear only in places marked by `*'. Of course, leading zeroes are not allowed.
Write a program that will find all solutions to the cryptarithm above for any subset of digits from the set {1,2,3,4,5,6,7,8,9}.
PROGRAM NAME: crypt1
INPUT FORMAT
| Line 1: | N, the number of digits that will be used |
| Line 2: | N space separated digits with which to solve the cryptarithm |
SAMPLE INPUT (file crypt1.in)
5 2 3 4 6 8
OUTPUT FORMAT
A single line with the total number of unique solutions. Here is the single solution for the sample input:
2 2 2
x 2 2
-------
4 4 4
4 4 4
---------
4 8 8 4
SAMPLE OUTPUT (file crypt1.out)
1
下面是一个乘法竖式，如果用我们给定的那n个数字来取代*，可以使式子成立的话，我们就叫这个式子牛式。
1
2
3
4
5
6
7
| * * * x * *---------- * * * * * *---------- * * * * |
数字只能取代*，当然第一位不能为0,况且给定的数字里不包括0。注意一下在美国的学校中教的“部分乘积”，第一部分乘积是第二个数的个位和第一个数的积，第二部分乘积是第二个数的十位和第一个数的乘积.
写一个程序找出所有的牛式。
bool num[10]; int N;bool check(int n){ while (n>0) { if (!num[n%10]) return false; n/=10; } return true;}int main(){ ifstream fin("crypt1.in"); ofstream fout("crypt1.out"); int a,b,c,tmp,ans(0); fin >> N; for (int i = 0; i < N; ++i) { fin >> tmp; num[tmp]=true; } for (int i = 111; i < 999; ++i) { if (!check(i)) continue; for (int j = 11; j < 99; ++j) { if (!check(j)) continue; a = i * (j % 10); b = i * (j - j % 10) / 10; c = i * j; if (a > 999 || b > 999 || c > 9999) continue; if (check(a) && check(b) && check(c)) ++ans; } } fout << ans << endl;}* Method One: solve1(), using the features of the length of numbers; * Method Two: solve2(), iterate all of the possible numbers from the existing * digit set.
public void solve1() throws Exception { BufferedReader br = new BufferedReader(new FileReader("crypt1.in")); BufferedWriter out = new BufferedWriter(new FileWriter("crypt1.out")); int N = Integer.parseInt(br.readLine()); String strLine = br.readLine(); strLine = strLine.replaceAll("\\s", ""); int count = 0; for (int i = 100; i < 1000; i++) { if (checkString(Integer.toString(i), strLine) == false) continue; for (int j = 10; j < 100; j++) { if (checkString(Integer.toString(j), strLine) == false) continue; // int a = j % 10 * i; // int b = j / 10 * i; String a = Integer.toString(j % 10 * i); String b = Integer.toString(j / 10 * i); String c = Integer.toString(j % 10 * i + (j / 10 * i) * 10); if (a.length() == 3 && b.length() == 3 && c.length() == 4 && checkString(a, strLine) && checkString(b, strLine) && checkString(c, strLine)) count++; } } out.write("" + count + "\n"); out.close(); }
X.
http://code.antonio081014.com/2012/09/usaco-prime-cryptarithm.html
public void solve2() throws Exception { BufferedReader br = new BufferedReader(new FileReader("crypt1.in")); BufferedWriter out = new BufferedWriter(new FileWriter("crypt1.out")); int N = Integer.parseInt(br.readLine()); String strLine = br.readLine(); strLine = strLine.replaceAll("\\s", ""); int count = 0; for (int a = 0; a < N; a++) { for (int b = 0; b < N; b++) { for (int c = 0; c < N; c++) { int p = Integer.parseInt("" + strLine.charAt(a) + strLine.charAt(b) + strLine.charAt(c)); for (int d = 0; d < N; d++) { String tmp1 = Integer.toString(p * (strLine.charAt(d) - '0')); if (tmp1.length() != 3 || checkString(tmp1, strLine) == false) continue; for (int e = 0; e < N; e++) { String tmp2 = Integer.toString(p * (strLine.charAt(e) - '0')); if (tmp1.length() != 3 || checkString(tmp2, strLine) == false) continue; String tmp3 = Integer.toString(p * (strLine.charAt(d) - '0' + 10 * (strLine .charAt(e) - '0'))); if (tmp3.length() == 4 && checkString(tmp3, strLine)) count++; } } } } } out.write("" + count + "\n"); out.close(); }http://usacounraveled.blogspot.com/2012/10/crypt1-prime-cryptarithm.html
for (int A:digits) {
for (int B:digits) {
for (int C:digits) {
for (int D:digits) {
for (int E:digits) {
int ABC = 100*A + 10*B + C;
int DE = 10*D + E;
if (val(ABC*D) && val(ABC*E) && val(ABC*DE) && String.valueOf(ABC*DE).length()==4 && String.valueOf(ABC*D).length()==String.valueOf(ABC*E).length() && String.valueOf(ABC*D).length()==3) {
System.out.print(ABC*DE+"\t");
count++;
}
}
}
}
}
}
http://jackneus.com/programming-archives/usaco-1-3-prime-cryptarithm/
bool check(int num){
stringstream ss;
ss << num;
string nume = ss.str();
for(int i = 0; i < nume.length(); i++){
for(int j = 0; j < N + 1; j++){
if(nume[i] == chars[j]){
break;
}
else if(j == N){
return false;
}
}
}
return true;
}
int main(){
ifstream in("crypt1.in");
ofstream out("crypt1.out");
in >> N;
for(int i = 0; i < N; i++){
int num;
in >> num;
nums.push_back(num);
char charNum = 48 + num;
chars.push_back(charNum);
}
vector<int> firstnum;
vector<int> secondnum;
int solut = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
for(int k = 0; k < N; k++){
firstnum.push_back((100 * nums[i]) + (10 * nums[j]) + nums[k]);
}
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
secondnum.push_back(10 * nums[i] + nums[j]);
}
}
for(int i = 0; i < firstnum.size(); i++){
for(int j = 0; j < secondnum.size(); j++){
int partial1 = firstnum[i] * (secondnum[j] % 10), partial2 = firstnum[i] * (secondnum[j] / 10), final = partial1 + (partial2 * 10);
if(partial1 / 1000 < 1 && partial2 / 1000 < 1 && final / 1000 < 10){
if(check(partial1) && check(partial2) && check(final)){
solut++;
}
}
}
}
out << solut << endl;
}
