{"id":72,"date":"2013-03-20T18:44:24","date_gmt":"2013-03-20T10:44:24","guid":{"rendered":"http:\/\/blog.dayandcarrot.net\/?p=72"},"modified":"2013-03-20T18:44:24","modified_gmt":"2013-03-20T10:44:24","slug":"1010-radix-25","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=72","title":{"rendered":"1010. Radix (25)"},"content":{"rendered":"<p>Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is &#8220;yes&#8221;, if 6 is a decimal number and 110 is a binary number.<br \/>\nNow for any pair of positive integers N1 and N2, your task is to find the radix of one number while that of the other is given.<br \/>\n<b>Input Specification:<\/b><br \/>\nEach input file contains one test case. Each case occupies a line which contains 4 positive integers:<br \/>\nN1 N2 tag radix<br \/>\nHere N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set {0-9, a-z} where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number &#8220;radix&#8221; is the radix of N1 if &#8220;tag&#8221; is 1, or of N2 if &#8220;tag&#8221; is 2.<br \/>\n<b>Output Specification:<\/b><br \/>\nFor each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print &#8220;Impossible&#8221;. If the solution is not unique, output the smallest possible radix.<br \/>\n<b>Sample Input 1:<\/b><\/p>\n<pre>6 110 1 10<\/pre>\n<p><b>Sample Output 1:<\/b><\/p>\n<pre>2<\/pre>\n<p><b>Sample Input 2:<\/b><\/p>\n<pre>1 ab 1 2<\/pre>\n<p><b>Sample Output 2:<\/b><\/p>\n<pre>Impossible<\/pre>\n<p>=================================================================<br \/>\n\u8c8c\u4f3c\u662f\u6d59\u5927PAT\u901a\u8fc7\u7387\u6700\u4f4e\u7684\u4e00\u9898\uff0c6%<br \/>\n\u4e00\u5f00\u59cb\u5f88\u4e0d\u89e3\uff0c\u4e3a\u5565\u901a\u8fc7\u7387\u8fd9\u4e48\u4f4e\uff0c\u660e\u660e\u662f\u5f88\u5bb9\u6613\u8bfb\u548c\u505a\u7684\u4e00\u9898\uff0c\u800c\u4e14\u5185\u5b58\u3001\u65f6\u95f4\u90fd\u633a\u5bbd\u88d5\u3002<br \/>\n\u505a\u8d77\u6765\u624d\u53d1\u73b0\uff0c\u5bf9\u4e8e\u6211\u6765\u8bf4\u6709\u8fd9\u4e9b\u95ee\u9898\uff1a<br \/>\n<strong>1\uff09\u601d\u7ef4\u5b9a\u52bf\u3002<\/strong>\u4e00\u5f00\u59cb\u8bef\u4ee5\u4e3a\u53ea\u53ef\u80fd\u8fdb\u5236\u523036\u4e3a\u6b62\uff0c\u56e0\u4e3a\u9898\u76ee\u8f93\u5165\u7684\u4e00\u4e2a\u6570\u7684\u8fdb\u5236\u6700\u9ad8\u53ea\u80fd\u523036\uff0c\u540e\u6765\u60f3\u60f3\uff0c\u8fd9\u8d27\u662f\u65e0\u7a77\u65e0\u5c3d\u7684\uff0c<br \/>\n\u5047\u5b9aA\u4e3a\u5df2\u77e5\u8fdb\u5236\u4e3ar1\u7684\u6570\uff0cB\u4e3a\u5f85\u6d4b\u8fdb\u5236(r2)\u7684\u6570\uff0c\u90a3\u4e48\u5f53\u7b2c\u4e00\u6b21\u9047\u5230r2,<em> s.t<\/em>. B@r2 > A@r1\u65f6\uff0c\u624d\u662f\u7ec8\u6b62\u6761\u4ef6\u3002<br \/>\n<strong>2\uff09\u6536\u655b\u901f\u5ea6\u3002<\/strong>\u89e3\u51b3\u95ee\u98981\u540e\uff0c\u7adf\u7136\u5c3c\u739b\u6709\u4e00\u4e2a\u8fd0\u884c\u8d85\u65f6\u4e86\uff0c\u4ed4\u7ec6\u60f3\u60f3\uff0cr2\u6309\u7167\u7ebf\u6027\u9012\u589e\u6d4b\u7b97\u7684\u8bdd\uff0c\u9047\u5230\u4ee5\u4e0b\u8f93\u5165\u5c06\u4f1a\u662f\u65e0\u7a77\u65e0\u5c3d\u7684\u65f6\u95f4\u624d\u80fd\u5224\u65ad<br \/>\n<em>e.g.<\/em><\/p>\n<pre>\nzzzzzzzzzz 1 1 36\n<\/pre>\n<p>\u6240\u4ee5r2\u80af\u5b9a\u4e0d\u80fd\u4e00\u4e2a\u4e00\u4e2a\u6765\u3002<br \/>\n\u7136\u540e\u5199\u4e86\u4e2a\u7b80\u5355\u7684\u56de\u6eaf\uff0c\u5f04\u4e86\u4e2a\u52a0\u901f\u5ea6\u7684\u4e1c\u897faccRate\uff0c\u5177\u4f53\u89c1\u4ee3\u7801\u300b\u3002\u5982\u679c\u4e00\u8def\u6210\u529f\u4f1a\u8d8a\u8d70\u8d8a\u5feb\uff0c\u5982\u679c\u9047\u5230\u5931\u8d25\uff0c\u90a3\u4e48\u9000\u56debackup\u7684\u503c\uff0c\u7136\u540e\u52a0\u901f\u5ea6\u56de\u52301\uff0c\u7136\u540e\u7ee7\u7eed\u3002\u7c97\u7565\u4e00\u7b97\u8fd9\u8d27\u7684\u6536\u655b\u901f\u5ea6\u6216\u8bb8\u662flog\u7ea7\u522b\u7684\uff0c\u76f4\u63a5\u653e\u5230pat\u5224\u9898\uff0c\u7136\u540e\u5168\u8fc7\u4e86:)<br \/>\n\u53e6\u5916\uff0c\u53d1\u73b0c++\u7528<math.lib>\u91cc\u9762\u7684pow\u7b97\u4e58\u65b9\u5176\u5b9e\u633a\u5feb\u7684\uff0c\u672c\u6765\u4ee5\u4e3a\u901f\u5ea6\u6162\u5728\u8fd9\u91cc\uff0c\u5475\u5475\u3002<br \/>\n\u8fd8\u6709\u4f7f\u7528long long\u662f\u56e0\u4e3a\u6309\u7167\u9898\u76ee\u7684\u9650\u5b9a\u6765\u8bf4\uff0c\u6700\u5927\u7684\u6570 zzzzzzzzzz \u653e\u5728\u4e00\u4e2along\u91cc\u9762\u4f3c\u4e4e\u4e0d\u591f\u7528&#8230;\u5f53\u7136\u7528double\u6216\u8bb8\u53ef\u4ee5\uff0c\u4e0d\u8fc7&#8230;\u6d6e\u70b9\u8fd0\u7b97\u5bf9cpu\u6765\u8bf4\u662f\u4e2a\u6050\u6016\u7684\u4e8b\u60c5\u5427<br \/>\n=================================================================<br \/>\n\u4ee5\u4e0b\u662f<br \/>\n\u6211\u7684\u53c2\u8003\u7b54\u6848\uff0c\u80af\u5b9a\u4e0d\u662f\u6700\u597d\u7684<br \/>\n\u91cc\u9762\u6709\u4e9b\u4e0d\u5fc5\u8981\u7684\u4e1c\u897f\uff0c\u61d2\u5f97\u5220\u4e86\u3002<br \/>\n\uff1a<\/p>\n<pre>\n#include <iostream>\n#include <math.h>\n#include <string.h>\n#include <time.h>\nusing namespace std;\nchar *N1, *N2;\nlong tag, radix;\nlong valueOfChar(char c)\n{\n\t\/\/get the value of a char\n\t\/\/0~9,a-z\n\tlong iC = (long)c;\n\tif(iC >= 0x30 && iC <= 0x39)\n\t\treturn iC - 0x30;\n\telse if(iC >=0x61 && iC <= 0x7a) \/\/a-z\n\t\treturn iC - 0x57;\n\telse \/\/wrong input\n\t{\n\t\tcerr << \"??? \" << c <<endl;\n\t\treturn -1;\n\t}\n}\nlong long getDecVal(char* input, long radix, long sSize = -1)\n{\n\t\/\/\u83b7\u5f97\u67d0\u8fdb\u5236\u6570\u768410\u8fdb\u5236\u503c\n\tint size = sSize;\n\tif(sSize == -1)\n\t\tsize = strlen(input);\n\tif(size <= 1)\n\t\treturn valueOfChar(input[0]);\n\telse\n\t{\n\t\t\/\/length of string > 1\n\t\tint X = valueOfChar(input[0]);\n\t\tlong long Z = X * pow(radix, size-1);\n\t\treturn Z + getDecVal(input+1, radix, size-1);\n\t}\n}\nlong getMinPossibleRadix(char* input)\n{\n\t\/\/\u83b7\u5f97\u6700\u5c0f\u53ef\u80fd\u7684\u57fa\u6570\n\tlong maxDigit = 0;\n\tlong nowDigit;\n\twhile( (*input) != '\u0000')\n\t{\n\t\tnowDigit = valueOfChar((*input));\n\t\tif(nowDigit > maxDigit)\n\t\t\tmaxDigit = nowDigit;\n\t\tinput ++;\n\t}\n\treturn maxDigit + 1;\n}\nchar *trial;\nint main()\n{\n\tclock_t start,mid;\n\tN1 = new char[10];\n\tN2 = new char[10];\n\tlong minPossibleRadix;\n\tcin >> N1 >> N2 >> tag >> radix;\n\tstart = clock();\n\tlong long lDecVal;\n\tif( tag == 1)\n\t{\n\t\tlDecVal = getDecVal(N1,radix);\n\t\tminPossibleRadix = getMinPossibleRadix(N2);\n\t\ttrial = N2;\n\t}\n\telse\n\t{\n\t\tlDecVal = getDecVal(N2,radix);\n\t\tminPossibleRadix = getMinPossibleRadix(N1);\n\t\ttrial = N1;\n\t}\n\tlong long rVal = -1;\n\tint strSize = strlen(trial);\n\tlong long accRate = 1;\/\/\u52a0\u901f\u5ea6\n\tlong long i= minPossibleRadix;\n\tlong long backup = i;\n\tbool inTrial = false; \/\/\u6b63\u5728\u5c1d\u8bd5\u7684\u72b6\u6001\n\twhile(true)\n\t{\n\t\trVal = getDecVal(trial,i,strSize);\n\t\tif(rVal == lDecVal)\n\t\t{\n\t\t\tcout << i;\n\t\t\t\/\/mid = clock();\n\t\t\t\/\/cout << mid - start << endl;\n\t\t\treturn 0;\n\t\t}\n\t\telse if(rVal > lDecVal)\n\t\t{\n\t\t\tif(!inTrial)\n\t\t\t\tbreak;\n\t\t\telse\n\t\t\t{\n\t\t\t\t\/\/\u56de\u6eaf\n\t\t\t\tinTrial = false;\n\t\t\t\tif( i == backup + 1)\n\t\t\t\t\tbreak;\n\t\t\t\ti = backup;\n\t\t\t\taccRate = 1;\n\t\t\t}\n\t\t}\n\t\telse\n\t\t{\n\t\t\tinTrial = true;\n\t\t\tbackup = i;\n\t\t\ti += accRate;\n\t\t\taccRate *= 10;\n\t\t\t\/\/cout << i << endl;\n\t\t}\n\t}\n\tmid = clock();\n\t\/\/cout << mid - start << endl;\n\tcout << \"Impossible\";\n\treturn 0;\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is &#8220;yes&#8221;, if 6 is a decimal number and 110 is a binary number. Now for any pair of positive integers N1 and N2, your task is to find the radix of one number [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[84],"class_list":["post-72","post","type-post","status-publish","format-standard","hentry","category-study","tag-pat"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/72","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=72"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/72\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=72"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=72"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=72"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}