【算法】算法之美—Crashing Balloon

題目概述：Crashing Balloon

　　On every  June 1st, the Children's Day, there will be a game named "crashing balloon" on  TV.   The rule is very simple.  On the ground there are 100 labeled balloons,  with the numbers 1 to 100. After the referee shouts "Let's go!" the two  players, who each starts with a score of  "1", race to crash the balloons by  their feet and, at the same time, multiply their scores by the numbers written  on the balloons they crash.  After a minute, the little audiences are allowed to  take the remaining balloons away, and each contestant reports his\her score, the  product of the numbers on the balloons he\she's crashed.  The unofficial winner  is the player who announced the highest score.

　　Inevitably,  though, disputes arise, and so the official winner is not determined until the  disputes are resolved.  The player who claims the lower score is entitled to  challenge his\her opponent's score.  The player with the lower score is presumed  to have told the truth, because if he\she were to lie about his\her score,  he\she would surely come up with a bigger better lie.  The challenge is upheld  if the player with the higher score has a score that cannot be achieved with  balloons not crashed by the challenging player.  So, if the challenge is  successful, the player claiming the lower score wins.

　　So, for  example, if one player claims 343 points and the other claims 49, then clearly  the first player is lying; the only way to score 343 is by crashing balloons  labeled 7 and 49, and the only way to score 49 is by crashing a balloon labeled  49.  Since each of two scores requires crashing the balloon labeled 49, the one  claiming 343 points is presumed to be lying.

　　On the  other hand, if one player claims 162 points and the other claims 81, it is  possible for both to be telling the truth (e.g. one crashes balloons 2, 3 and  27, while the other crashes balloon 81), so the challenge would not be  upheld.

　　By the  way, if the challenger made a mistake on calculating his/her score, then the  challenge would not be upheld. For example, if one player claims 10001 points  and the other claims 10003, then clearly none of them are telling the truth. In  this case, the challenge would not be upheld.

　　Unfortunately,  anyone who is willing to referee a game of crashing balloon is likely to get  over-excited in the hot atmosphere that he\she could not reasonably be expected  to perform the intricate calculations that refereeing requires.  Hence the need  for you, sober programmer, to provide a software solution.

Pairs of  unequal, positive numbers, with each pair on a single line, that are claimed  scores from a game of crashing balloon.

Output

　　Numbers,  one to a line, that are the winning scores, assuming that the player with the  lower score always challenges the outcome.

Sample  Input

343 49

3599 610

62 36

Sample  Output

49

610

62

簡單描述

　　這也是一個很有意思的題,不認真讀題,可能還不太明白.我來簡單翻譯一下

有一個遊戲,規則是這樣,有一堆氣球100個,标号1->100,有兩個人參與.一但開始,兩個人就瘋狂的踩氣球,時間到就結束了(也許就10s),把他們各自踩破的球上的編号乘起來,分别是M,N,那麼排名自然揭曉了

　　可是分數低的人不服氣,想申訴.現在問題來了,怎麼申訴呢?因為每個标号的球隻有一個,是以加入B踩破的話,A就沒辦法踩了,申訴想要産生的沖突就在這兒.現在假如分數是 343 49 ,343可以是踩了 7和49,49隻能是踩49,他們兩都同時必須要踩這個49,那麼就産生沖突了.是以49赢了.還有要是有人的分數,不能由1->100的數的成績的出,算說假話,如果兩個人都說假話,還是分高的赢.

題目分析

　　有三種情況:

　　(1)A,B沒有沖突,那麼A赢

　　(2)A,B怎麼都會有沖突,而且B說的是真話,那麼B赢

　　(3)A,B怎麼都會有沖突,而且B說的是假話,那麼A赢

#include < stdio.h>
int flagA,flagB;
int result ;
void dfs(int m,int n,int kk)    //運用了深度優先 的搜尋政策
{
    int k =kk;
    if(m==1 && n==1)    //在兩個數的所有各不相同的因子中，有因子能重新乘出給出的兩個數，則A說了真話
    {
       flagA=1; //A說了真話
       return ;
    }
    if(n==1) //在兩個數的所有各不相同的因子中，沒有任何因子能重新乘出給出的兩個數，則B說了真話
        flagB =1;   //B說了真話
    while( (k <  m || k <  n) && (k< 100) )
    {
       k++;
       /*
       *依次找出兩個數所有各不相同的因子，如24和12的所有因子為 2，3，4，6，8，12 ，
        再在這些因子中搜尋，看是否能重新乘出給出的兩個數
       */
       if(m%k ==0)
       {
            dfs(m/k,n,k);
            if(flagA)
                return ;
       }
       if(n%k ==0 )
       {
            dfs(m,n/k,k);
            if(flagA)
                return ;
       }
    }
}
int main()
{
    int A,B,t;
    while(scanf("%d%d",&A,&B)!=EOF )
    {
        if(A <  B )  //保證A大B小
        {
            t=A;
            A=B;
            B=t;
        }
        flagA =0;   //先假定AB都說假話
        flagB =0;
        dfs(A,B,1); //判斷AB沖突         
        /*
        *要求:
        *較小者發起挑戰，若較大者被證明說謊，較小者勝（較小者說真話，同時較大者說了假話）;
        *若較大者可以成立，則較大者勝;
        *若較小者對自己的結果計算錯誤，也就是較小者不能成立，如因子中包含一個大于100的質數，則挑戰不會舉行，較大者勝
        */
        result =A;   
        if(flagA ==0 && flagB ==1)  //隻有證明A說了假話，并且B說了真話，才算B赢
            result =B;
        printf("%d\n",result);
    }
    return 0;
}