`
925695531
  • 浏览: 22194 次
  • 性别: Icon_minigender_1
文章分类
社区版块
存档分类
最新评论

usaco Prime Cryptarithm 解题报告

 
阅读更多
题意:

下面是一个乘法竖式,如果用我们给定的那n个数字来取代*,可以使式子成立的话,我们就叫这个式子牛式。

        * * *
    x     * *
   ----------
        * * *
      * * *
   ----------
      * * * *

数字只能取代*,当然第一位不能为0,况且给定的数字里不包括0。

注意一下在美国的学校中教的“部分乘积”,第一部分乘积是第二个数的个位和第一个数的积,第二部分乘积是第二个数的十位和第一个数的乘积.

写一个程序找出所有的牛式。

题解:

枚举符合题意的乘数a和b,然后产生product1,product2,和总的product,分别检查是否符合要求,符合就计数器加一

代码:

/*
ID:     lishicao
PROG:   crypt1
LANG:   C++
*/
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std ;

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

int  N  , Count = 0 ;
int  number[10] , num[5] ;

void  dfs( int ) ;
bool  check() ;

int  main()
{
    fin >> N ;
    for( int i = 0 ; i < N ; i ++ )
        fin >> number[i] ;
    dfs( 0 ) ;
    fout << Count << endl ;
    return 0 ;
}

void  dfs( int depth )
{
    if( depth == 5 )
    {
        if( check() ){
            Count ++ ;
        }
        return ;
    }
    for( int i = 0 ; i < N ; i ++ )
    {
        num[depth] = number[i] ;
        dfs( depth + 1 ) ;
    }
}

bool  check()
{
    int  product1 , product2 , product , temp , flag = 0 ;
    product1 = num[4] * ( 100 * num[0] + 10 * num[1] + num[2] ) ;
    product2 = num[3] * ( 100 * num[0] + 10 * num[1] + num[2] ) ;
    product  = product1 + product2 * 10 ;

    if( product1 >= 1000  || product1 < 100  ) return false ;
    if( product2 >= 1000  || product2 < 100  ) return false ;
    if( product  >= 10000 || product  < 1000 ) return false ;


    for( int i = 0 ; i < 3 ; i ++ )
    {
        temp = product1 % 10 ;
        product1 /= 10 ;
        int flag = 0 ;
        for( int j = 0 ; j < N ; j ++ )
            if( temp == number[j] ) flag = 1 ;
        if( flag == 0 ) return false ;

        temp = product2 % 10 ;
        product2 /= 10 ;
        flag = 0 ;
        for( int j = 0 ; j < N ; j ++ )
            if( temp == number[j] ) flag = 1 ;
        if( flag == 0 ) return false ;
    }
    for( int i = 0 ; i < 4 ; i ++ )
    {
        temp = product % 10 ;
        product /= 10 ;
        int flag = 0 ;
        for( int j = 0 ; j < N ; j ++ )
            if( temp == number[j] ) flag = 1 ;
        if( flag == 0 ) return false ;
    }
    return true ;
}

分享到:
评论

相关推荐

    usaco 2005年解题报告

    usaco 2005年比赛的解题报告以及测试数据

    usaco 2004年解题报告

    包括usaco2004年比赛的解题报告以及测试数据

    usaco 2003年解题报告

    包括usaco2003年比赛的解题报告及测试数据

    usaco 2001年解题报告

    包括usaco2003年比赛的解题报告及测试数据

    usaco5.2解题报告1

    usaco5.2解题报告1

    usaco2.1解题报告1

    usaco2.1解题报告1

    usaco2.3解题报告1

    usaco2.3解题报告1

    usaco1.3解题报告1

    usaco1.3解题报告1

    usaco2.4解题报告1

    usaco2.4解题报告1

    usaco解题报告,希望对大家有用

    usaco解题报告,就是usaco.training.gateway上面的题目全解

    ACM----USACO Training(解题博客网)

    ACM----USACO Training(解题博客网),提供了USACO Training解题的代码,可以参考一下

    usaco5.3解题报告1

    第一行应该包括一个正整数:子任务 A 第二行应该包括子任务 B 的解 第二问的要求是最少添加多少条有向边可以使得整张图任意一个学校有软件,其

    usaco3.1解题报告1

    本章主要衔接第二章,题目类型不定描述农民约翰被选为他们镇的镇长!他其中一个竞选承诺就是在镇上建立起互联网,并连接到所有的农场。当然,他需要你的帮助。约翰已经给他

    usaco3.4解题报告1

    1.歌曲必须按照创作的时间顺序在 CD 盘上出现 2.选中的歌曲数目尽可能地多 3.不仅同光盘上的歌曲写入时间要按顺序,前一张光盘上的歌曲不能比后一张

    usaco3.2解题报告1

    因为 10=2*5,所以每有一个 0 就有一对 2*5=10 出现,反之,如果这个数的质因数分解没有成对的 2,5,我们就可以简单的对 10 求模,而不用管前面

    usaco5.4解题报告1

    1.假设一个 nxn 的拉丁方在固定第一行和第一列的情况下的构造数目是 L[n],那 2.最后一行不用构造,如果搜索完 N-1 行,到达第 N 行,那么一定存在

    usaco3.3解题报告1

    第一行 优惠商品的种类数(0 ) 第二行..第 s+1 行 每一行都用几个整数来表示一种优惠方式 第一个整数 n 第一行: 两个用空格隔开的

    usaco4.4解题报告1

    3 5 6 4 2 1 3 5 7 6 4 2 3 5 4分析:先观察样例数据,如果把还没移动的那一步也算上,那么空格的位置为4 3 5 6 4 2 1 3 5

    usaco4.2解题报告1

    第二行到第 N+1 行: 每行有三个整数,Si, Ei, 和 Ci 第一个星期,农夫约翰随便地让 第一行 两个整数,N (0 ) 和 M

    usaco5.1解题报告1

    与第 4 章衔接引入凸包,DP 的单调思想加强。Fencing the Cows 圈奶牛译 by Felicia Crazy描述农夫约翰想要建造一个围栏用来围住

Global site tag (gtag.js) - Google Analytics