【アルゴリズム】アルゴリズムの美しさ――Crassing Ballowon
タイトル概要:Crassing Ballowon
On every June 1 st,the Children's Day,there will be a game named“crassing ballon”on TV. The rule is very simple. On the ground there re 100 labeled ballons、 with the numbers 1 to 100.After the referee shuts「Let's go!」the two playrs,who each starts with a score of 「1」、race to crash the ballowons by their feet and,at the same time,multily their scores by the numbers written on the ballons the y cras. After a minute、the little audience are allowed to take the remaning ballons away、and each contestant reporthis\her score、the product of the numbers on the ballowons he\she's crased. The unoffical winner is the player who announced the highest score.
Inevitably、 though、disputes arse、and so the offical winner is not determined until the disputes are resoloved. The player who claims the lower score is entitled to challege 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、 ヘ\she would surely come up with a biggar better lie. The challege is uheld if the player with the higher score has a score that cannot be achieved with ballons not crased by the challing player. So,if the challeging is success ful,the player claiming the lower score wins.
フォーム 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 crassing ballowons labeled 7 and 49、and the only way to score 49 is by crassing a ballon labeled 49. Since each of two scores requires crassing the ballon 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 crases ballons 2,3 and 27,while the other crases ballon 81),so the challege would not be uplhed.
By the way,if the challeger made a mistake on callining his/her score,then the challege would not be uplhed.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 challege would not be uplhed.
Unfortunally、 anyone who is willing to referee a game of crassing ballowon is likelyto get over-excited in the hot atmosphere that he\she could not reasonably be expected to perform the intricate calculations that refeeing 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 crassing ballowon.
Output
ナンバーズ、 one to a line、that are the wining scores、asuming that the player with the lower score always challengs the outcome.
Sample Input
343
3599
62
Sample Output
49
610
62
簡単な説明
これも面白い問題です.問題をちゃんと読まないと、よく分かりません.簡単に訳してみます.
一つのゲームがあります.ルールはこうです.風船が100個あります.番号は1->>100で、二人が参加します.最初は、二人は気違いで風船を踏みました.時間はもう終わりました.(10 sだけかもしれません.)彼らがそれぞれ踏み潰したボールの番号を乗せて、それぞれM、Nという順位を自然に発表しました.
しかし、点数が低い人は不服で、訴えたいです.今問題が来ました.どうやって訴えますか?各マークのボールは一つしかないので、Bを入れて踏んではいけません.Aは踏んではいけません.発生したいと訴える矛盾はここにあります.今は点数が343なら、343は7と49、49を踏んで49を踏むしかないです.両方とも同時にこの49を踏まなければならないので、49が勝ちました.また、点数があれば、1から100までの成績が出せません.うそを言っても、二人ともうそをついたら、やはり点数が高いほうが勝ちです.
テーマ分析
三つの場合があります.
(1)A、Bは矛盾がないので、Aが勝つ.
(2)A、Bはどうしても矛盾があります.Bは本当のことを言っています.Bは勝ちます.
(3)A、Bはどうしても矛盾があります.そしてBは嘘を言っています.Aが勝ちます.
解題アルゴリズム
下記のソースコードの中で、主なコードに対して詳細な注釈を行いました.
On every June 1 st,the Children's Day,there will be a game named“crassing ballon”on TV. The rule is very simple. On the ground there re 100 labeled ballons、 with the numbers 1 to 100.After the referee shuts「Let's go!」the two playrs,who each starts with a score of 「1」、race to crash the ballowons by their feet and,at the same time,multily their scores by the numbers written on the ballons the y cras. After a minute、the little audience are allowed to take the remaning ballons away、and each contestant reporthis\her score、the product of the numbers on the ballowons he\she's crased. The unoffical winner is the player who announced the highest score.
Inevitably、 though、disputes arse、and so the offical winner is not determined until the disputes are resoloved. The player who claims the lower score is entitled to challege 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、 ヘ\she would surely come up with a biggar better lie. The challege is uheld if the player with the higher score has a score that cannot be achieved with ballons not crased by the challing player. So,if the challeging is success ful,the player claiming the lower score wins.
フォーム 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 crassing ballowons labeled 7 and 49、and the only way to score 49 is by crassing a ballon labeled 49. Since each of two scores requires crassing the ballon 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 crases ballons 2,3 and 27,while the other crases ballon 81),so the challege would not be uplhed.
By the way,if the challeger made a mistake on callining his/her score,then the challege would not be uplhed.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 challege would not be uplhed.
Unfortunally、 anyone who is willing to referee a game of crassing ballowon is likelyto get over-excited in the hot atmosphere that he\she could not reasonably be expected to perform the intricate calculations that refeeing 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 crassing ballowon.
Output
ナンバーズ、 one to a line、that are the wining scores、asuming that the player with the lower score always challengs the outcome.
Sample Input
343
3599
62
Sample Output
49
610
62
簡単な説明
これも面白い問題です.問題をちゃんと読まないと、よく分かりません.簡単に訳してみます.
一つのゲームがあります.ルールはこうです.風船が100個あります.番号は1->>100で、二人が参加します.最初は、二人は気違いで風船を踏みました.時間はもう終わりました.(10 sだけかもしれません.)彼らがそれぞれ踏み潰したボールの番号を乗せて、それぞれM、Nという順位を自然に発表しました.
しかし、点数が低い人は不服で、訴えたいです.今問題が来ました.どうやって訴えますか?各マークのボールは一つしかないので、Bを入れて踏んではいけません.Aは踏んではいけません.発生したいと訴える矛盾はここにあります.今は点数が343なら、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
",result);
}
return 0;
}