• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            coreBugZJ

            此 blog 已棄。

            A hard Aoshu Problem, ACM/ICPC 2010/2011 亞洲,福州區(qū)域賽 J, UVA 5107

            5107 - A hard Aoshu Problem
            Asia - Fuzhou - 2010/2011

             

            Math Olympiad is called ``Aoshu" in China. Aoshu is very popular in elementary schools. Nowadays, Aoshu is getting more and more difficult. Here is a classic Aoshu problem:

             

             

            ABBDE$\displaystyle \_$$\displaystyle \_$$\displaystyle \_abccc$ = BDBDE

            In the equation above, a letter stands for a digit(0 - 9), and different letters stands for different digits. You can fill the blank with `+', `-`, ` x' or `÷'.

            How to make the equation right? Here is a solution:

             

             

            12245 + 12000 = 24245

            In that solution, A = 1, B = 2, C = 0, D = 4, E = 5, and `+' is filled in the blank.

            When I was a kid, finding a solution is OK. But now, my daughter's teacher tells her to find all solutions. That's terrible. I doubt whether her teacher really knows how many solutions are there. So please write a program for me to solve this kind of problems.

             

            Input 

            The first line of the input is an integer T (T$ \le$20) indicating the number of test cases.

            Each test case is a line which is in the format below:

             


            s1 s2 s3

             


            s1, s2 and s3 are all strings which are made up of capital letters. Those capital letters only include ` A',' B', ' C',' D' and ` E', so forget about ` F' to ` Z'. The length of s1, s2 or s3 is no more than 8.

            When you put a `=' between s2 and s3, and put a operator (`+','-`, ` x' or `÷'.) between s1 and s2, and replace every capital letter with a digit, you get a equation.

            You should figure out the number of solutions making the equation right.

            Please note that same letters must be replaced by same digits, and different letters must be replaced by different digits.

            If a number in the equation is more than one digit, it must not have leading zero.

             

            Output 

            For each test case, print an integer in a line. It represents the number of solutions.

             

            Sample Input 

             

            2 
            A A A
            BCD BCD B

             

            Sample Output 

             

            5
            72

            Fuzhou 2010-2011


            暴力搜索之。。。

            我的代碼:

             1 #include <stdio.h>
             2 #include <string.h>
             3 
             4 typedef long long Lint;
             5 
             6 #define  L  10
             7 
             8 char s1[ L ], s2[ L ], s3[ L ];
             9 
            10 #define  DIGIT  6
            11 
            12 int digit[ DIGIT ], used[ DIGIT ];
            13 int a[ L ], b[ L ], c[ L + L ];
            14 
            15 void parse( char s[], int a[], int size ) {
            16         int i, len = strlen( s );
            17         memset( a, 0, size );
            18         for ( i = 0; i < len; ++i ) {
            19                 used[ a[ len - i - 1 ] = s[ i ] - 'A' + 1 ] = 1;
            20         }
            21 }
            22 
            23 void init() {
            24         memset( used,  0sizeof(used)  );
            25         parse( s1, a, sizeof(a) );
            26         parse( s2, b, sizeof(b) );
            27         parse( s3, c, sizeof(c) );
            28 }
            29 
            30 int parseInt( int a[], int n, Lint *num ) {
            31         int i = n-1;
            32         while ( (i>=0&& (a[i]==0) ) --i;
            33         if ( (i<0|| ((i>0)&&(digit[a[i]]==0)) ) return 0;
            34         *num = 0;
            35         for ( ; i >= 0--i ) {
            36                 if ( digit[ a[ i ] ] > 9 ) return 0;
            37                 *num = (*num) * 10 + digit[ a[ i ] ];
            38         }
            39         return 1;
            40 }
            41 
            42 int equal() {
            43         Lint x, y, z;
            44         int i, ans = 0;
            45         for ( i = 1; i < DIGIT; ++i ) {
            46                 if ( (digit[i]<10&& (used[i]==0) ) {
            47                         return 0;
            48                 }
            49         }
            50         if ( !parseInt( a, sizeof(a)/sizeof(a[0]), &x ) ) return 0;
            51         if ( !parseInt( b, sizeof(b)/sizeof(b[0]), &y ) ) return 0;
            52         if ( !parseInt( c, sizeof(c)/sizeof(c[0]), &z ) ) return 0;
            53         if ( x + y == z ) ++ans;
            54         if ( x - y == z ) ++ans;
            55         if ( x * y == z ) ++ans;
            56         if ( (y!=0&& (x%y==0&& (x/y==z) ) ++ans;
            57         return ans;
            58 }
            59 
            60 int solve() {
            61         int ans = 0, have[ 22 ] = { 0 };
            62 #define  F(i) for ( digit[ i ] = 0; digit[ i ] < 11; ++digit[ i ] ) { \
            63                 if ( have[ digit[ i ] ] ) continue; \
            64                 if ( digit[ i ] < 10 ) have[ digit[ i ] ] = 1;
            65 #define  E(i)  have[ digit[ i ] ] = 0; \
            66         }
            67         F(1) F(2) F(3) F(4) F(5) {
            68                 ans += equal();
            69         } E(5) E(4) E(3) E(2) E(1)
            70         return ans;
            71 }
            72 
            73 int main() {
            74         int td;
            75         scanf( "%d"&td );
            76         while ( td-- > 0 ) {
            77                 scanf( "%s%s%s", s1, s2, s3 );
            78                 init();
            79                 printf( "%d\n", solve() );
            80         }
            81         return 0;
            82 }
            83 


            posted on 2011-03-24 22:14 coreBugZJ 閱讀(2097) 評(píng)論(3)  編輯 收藏 引用 所屬分類: ACM

            Feedback

            # re: A hard Aoshu Problem, ACM/ICPC 2010/2011 亞洲,福州區(qū)域賽, UVA 5107 2011-03-25 09:53 電腦知識(shí)與技術(shù)

            全都是英文。看不懂啊  回復(fù)  更多評(píng)論   

            # re: A hard Aoshu Problem, ACM/ICPC 2010/2011 亞洲,福州區(qū)域賽, UVA 5107[未登錄] 2011-03-25 15:45 Bill

            純建議,不要一次發(fā)一堆文章到主頁上。可以慢慢發(fā)。  回復(fù)  更多評(píng)論   

            # re: A hard Aoshu Problem, ACM/ICPC 2010/2011 亞洲,福州區(qū)域賽, UVA 5107 2011-03-25 16:21 coreBugZJ

            @Bill
            我是剛來的菜鳥,不懂事,謝謝提醒。。。  回復(fù)  更多評(píng)論   


            91精品婷婷国产综合久久| 人人狠狠综合久久亚洲88| 国产精品无码久久久久| 国产三级观看久久| 久久九九免费高清视频| 三上悠亚久久精品| 国产精品无码久久久久| 伊人情人综合成人久久网小说| 久久精品极品盛宴观看| 一本色道久久综合亚洲精品| 亚洲国产成人久久综合碰碰动漫3d| 国产高潮久久免费观看| 99久久国产综合精品女同图片| 精品国产91久久久久久久| 亚洲中文字幕久久精品无码APP | 亚洲国产一成久久精品国产成人综合| 亚洲国产精品无码久久一线 | 99久久婷婷国产综合精品草原 | 亚洲精品白浆高清久久久久久| 久久这里只有精品久久| 亚洲国产精品久久电影欧美| 国内精品久久久久久久久| 久久精品一区二区| 亚洲狠狠婷婷综合久久久久| 亚洲国产成人精品无码久久久久久综合| 精品久久久久久久久中文字幕| 亚洲天堂久久久| 久久亚洲精品无码观看不卡| 国产亚洲成人久久| 久久99精品国产99久久| 久久ZYZ资源站无码中文动漫| 久久久噜噜噜www成人网| 午夜精品久久影院蜜桃| 久久综合伊人77777| 青青草原1769久久免费播放| 久久精品国产91久久综合麻豆自制 | 久久婷婷色综合一区二区| 免费观看久久精彩视频| 精品精品国产自在久久高清| 久久久久亚洲av无码专区| 久久国产精品无码HDAV|