题目描述在位置记数法中数字的位置表示该数字在数值中的权重。例如在十进制数362362362中222的权重为10010^0100666的权重为10110^1101333的权重为10210^2102因此数值为3×1026×1012×1003623 \times 10^2 6 \times 10^1 2 \times 10^0 3623×1026×1012×100362。同样的机制也适用于其他进制。虽然大多数人认为他们每天遇到的数字都是用十进制表示的但其他进制也是可能的。特别地九进制或十四进制下的362362362与十进制下的362362362代表完全不同的数值。对于本题程序将处理一系列整数对。设整数对的两个成员为XXX和YYY。程序需要确定XXX的最小可能进制和YYY的最小可能进制通常与XXX的不同使得XXX和YYY代表相同的数值。例如考虑整数121212和555。如果两者都用十进制它们显然不相等。但假设121212是三进制数555是六进制数三进制的121212等于1×312×3051 \times 3^1 2 \times 3^0 51×312×305十进制而任何进制下的555都等于555十进制。因此121212和555可以相等只要为它们选择正确的进制输入格式输入数据的每一行包含一对整数XXX和YYY由一个或多个空格分隔每行前后也可能有空格应被忽略。XXX和YYY的进制范围是111到363636含且不需要相同。在表示这些数字时数字0∼90 \sim 90∼9具有通常的十进制含义。大写字母A∼ZA \sim ZA∼Z分别表示数字10∼3510 \sim 3510∼35。输出格式对于输入中的每一对整数输出类似示例所示的消息。如果无论如何选择进制每个数的进制在222到363636之间两个数都无法相等则输出相应的消息。样例输入12 5 10 A 12 34 123 456 1 2 10 2样例输出12 base 3 5 base 6 10 base 10 A base 11 12 base 17 34 base 5 123 is not equal to 456 in any base 2..36 1 is not equal to 2 in any base 2..36 10 base 2 2 base 3题目分析问题的本质这是一个进制转换与数值比较问题。给定两个字符串可能包含数字和字母A∼ZA \sim ZA∼Z需要找出进制bXb_XbX和bYb_YbY2≤bX,bY≤362 \leq b_X, b_Y \leq 362≤bX,bY≤36使得XXX在bXb_XbX进制下的数值等于YYY在bYb_YbY进制下的数值。进制范围最小进制由字符串中的最大数字决定。例如如果字符串包含数字999则最小进制至少为101010如果包含字母AAA则最小进制至少为111111。最大进制363636因为字母最大为ZZZ代表353535特殊考虑当字符串为单个数字如1、2时它在任何进制下的值都相同但最小进制为222因为进制111无效注意题目描述中提到进制范围为111到363636但根据常识进制至少为222单数字0或1在进制111下也有定义但通常不考虑。示例中输出为base 2..36说明只考虑222到363636。算法思路枚举XXX的所有可能进制从最小进制到363636计算其十进制值存于集合中。同样枚举YYY的所有可能进制计算其十进制值。然后寻找一个共同值。如果有多个选择使XXX的进制最小的那个题目要求最小可能进制。参考代码// What Base Is This?// UVa ID: 343// Verdict: Accepted// Submission Date: 2016-06-27// UVa Run Time: 0.010s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){ios::sync_with_stdio(false);string X,Y;string digits0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ;mapchar,intkey;// 建立字符到数值的映射for(inti0;idigits.length();i)key.insert(make_pair(digits[i],i));while(cinXY){setlonglongXs,Ys;// 存储所有可能的数值mapint,longlongvalueXs,valueYs;// 进制 - 数值 映射// 计算 X 的最小可能进制intbaseX0;for(charc:X)baseXmax(baseX,key[c]1);baseXmax(baseX,2);// 枚举 X 的所有可能进制for(intbxbaseX;bx36;bx){longlongvalue0;for(charc:X)valuevalue*bxkey[c];valueXs[bx]value;Xs.insert(value);}// 计算 Y 的最小可能进制intbaseY0;for(charc:Y)baseYmax(baseY,key[c]1);baseYmax(baseY,2);// 枚举 Y 的所有可能进制for(intbybaseY;by36;by){longlongvalue0;for(charc:Y)valuevalue*bykey[c];valueYs[by]value;Ys.insert(value);}// 寻找匹配的数值boolflagfalse;for(intbxbaseX;bx36;bx){if(Ys.find(valueXs[bx])!Ys.end()){// 找到匹配找出 Y 对应的进制for(intbybaseY;by36;by)if(valueYs[by]valueXs[bx]){coutX base bx ;coutY base byendl;break;}flagtrue;break;}}if(!flag){coutX is not equal to Y in any base 2..36endl;}}return0;}
UVa 343 What Base Is This
题目描述在位置记数法中数字的位置表示该数字在数值中的权重。例如在十进制数362362362中222的权重为10010^0100666的权重为10110^1101333的权重为10210^2102因此数值为3×1026×1012×1003623 \times 10^2 6 \times 10^1 2 \times 10^0 3623×1026×1012×100362。同样的机制也适用于其他进制。虽然大多数人认为他们每天遇到的数字都是用十进制表示的但其他进制也是可能的。特别地九进制或十四进制下的362362362与十进制下的362362362代表完全不同的数值。对于本题程序将处理一系列整数对。设整数对的两个成员为XXX和YYY。程序需要确定XXX的最小可能进制和YYY的最小可能进制通常与XXX的不同使得XXX和YYY代表相同的数值。例如考虑整数121212和555。如果两者都用十进制它们显然不相等。但假设121212是三进制数555是六进制数三进制的121212等于1×312×3051 \times 3^1 2 \times 3^0 51×312×305十进制而任何进制下的555都等于555十进制。因此121212和555可以相等只要为它们选择正确的进制输入格式输入数据的每一行包含一对整数XXX和YYY由一个或多个空格分隔每行前后也可能有空格应被忽略。XXX和YYY的进制范围是111到363636含且不需要相同。在表示这些数字时数字0∼90 \sim 90∼9具有通常的十进制含义。大写字母A∼ZA \sim ZA∼Z分别表示数字10∼3510 \sim 3510∼35。输出格式对于输入中的每一对整数输出类似示例所示的消息。如果无论如何选择进制每个数的进制在222到363636之间两个数都无法相等则输出相应的消息。样例输入12 5 10 A 12 34 123 456 1 2 10 2样例输出12 base 3 5 base 6 10 base 10 A base 11 12 base 17 34 base 5 123 is not equal to 456 in any base 2..36 1 is not equal to 2 in any base 2..36 10 base 2 2 base 3题目分析问题的本质这是一个进制转换与数值比较问题。给定两个字符串可能包含数字和字母A∼ZA \sim ZA∼Z需要找出进制bXb_XbX和bYb_YbY2≤bX,bY≤362 \leq b_X, b_Y \leq 362≤bX,bY≤36使得XXX在bXb_XbX进制下的数值等于YYY在bYb_YbY进制下的数值。进制范围最小进制由字符串中的最大数字决定。例如如果字符串包含数字999则最小进制至少为101010如果包含字母AAA则最小进制至少为111111。最大进制363636因为字母最大为ZZZ代表353535特殊考虑当字符串为单个数字如1、2时它在任何进制下的值都相同但最小进制为222因为进制111无效注意题目描述中提到进制范围为111到363636但根据常识进制至少为222单数字0或1在进制111下也有定义但通常不考虑。示例中输出为base 2..36说明只考虑222到363636。算法思路枚举XXX的所有可能进制从最小进制到363636计算其十进制值存于集合中。同样枚举YYY的所有可能进制计算其十进制值。然后寻找一个共同值。如果有多个选择使XXX的进制最小的那个题目要求最小可能进制。参考代码// What Base Is This?// UVa ID: 343// Verdict: Accepted// Submission Date: 2016-06-27// UVa Run Time: 0.010s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){ios::sync_with_stdio(false);string X,Y;string digits0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ;mapchar,intkey;// 建立字符到数值的映射for(inti0;idigits.length();i)key.insert(make_pair(digits[i],i));while(cinXY){setlonglongXs,Ys;// 存储所有可能的数值mapint,longlongvalueXs,valueYs;// 进制 - 数值 映射// 计算 X 的最小可能进制intbaseX0;for(charc:X)baseXmax(baseX,key[c]1);baseXmax(baseX,2);// 枚举 X 的所有可能进制for(intbxbaseX;bx36;bx){longlongvalue0;for(charc:X)valuevalue*bxkey[c];valueXs[bx]value;Xs.insert(value);}// 计算 Y 的最小可能进制intbaseY0;for(charc:Y)baseYmax(baseY,key[c]1);baseYmax(baseY,2);// 枚举 Y 的所有可能进制for(intbybaseY;by36;by){longlongvalue0;for(charc:Y)valuevalue*bykey[c];valueYs[by]value;Ys.insert(value);}// 寻找匹配的数值boolflagfalse;for(intbxbaseX;bx36;bx){if(Ys.find(valueXs[bx])!Ys.end()){// 找到匹配找出 Y 对应的进制for(intbybaseY;by36;by)if(valueYs[by]valueXs[bx]){coutX base bx ;coutY base byendl;break;}flagtrue;break;}}if(!flag){coutX is not equal to Y in any base 2..36endl;}}return0;}
