学步园

pku 1152:http://acm.pku.edu.cn/JudgeOnline/problem?id=1152

解答:

import java.io.BufferedReader;<br /> import java.io.File;<br /> import java.io.FileInputStream;<br /> import java.io.FileNotFoundException;<br /> import java.io.FileOutputStream;<br /> import java.io.InputStreamReader;<br /> import java.util.ArrayList;<br /> import java.util.Scanner;</p> <p>public class Main {<br /> public static String numberList = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";<br /> public static final String ERROR_MESSAGE = "such number is impossible!";</p> <p> public static void main(String[] args){<br /> try {<br /> File source = new File("input.txt");<br /> Scanner cin = new Scanner(source);<br /> // BufferedReader in = new BufferedReader(new InputStreamReader(System.in));<br /> // String str = in.readLine();<br /> // for (; str != null && str.length() > 0; str = in.readLine()) {<br /> while(cin.hasNextLine()) {<br /> String inputNumber = cin.nextLine();<br /> // String inputNumber = str;<br /> int result = -1;<br /> int index = numberList.indexOf(inputNumber);<br /> if (index == 0 || index == 1) {<br /> result = 2;<br /> } else if (index == -1) {<br /> result = -1;<br /> } else {<br /> result = index + 1;<br /> }<br /> if (result == -1) {<br /> System.out.println(ERROR_MESSAGE);<br /> } else {<br /> System.out.println(result);<br /> }<br /> }<br /> } catch (Exception ex) {<br /> ex.printStackTrace();<br /> }<br /> }<br /> } 

这道题目至今一直是WA的效果.但是我还是没有找出到底哪里是错误的.如果有人看到这篇文章 望指点^^

算法的思想其实很简单,除了0,1以及特殊符号以外,只需要在之前定义的字符串中找到输入的字符的index,之后N 即为index+1;如果为0或者1,则为2;如果为特殊字符,那么就是输出错误信息.

===================================================================

现在发现一个问题：You will be given an N based integer number R and you are given the guaranty that R is divisible by (N-1)。这句话被我忽略了。也就是说这个给出来的数当它转化为N进制数之后要能被N整除。我做到的是把给出来的数从N进制转化为十进制数，然后是否可以整除N。

可是现在是Time Limit Exceeded

import java.io.BufferedReader;<br /> import java.io.File;<br /> import java.io.FileInputStream;<br /> import java.io.FileNotFoundException;<br /> import java.io.FileOutputStream;<br /> import java.io.InputStreamReader;<br /> import java.math.BigInteger;<br /> import java.util.ArrayList;<br /> import java.util.Scanner;</p> <p>public class Main {<br /> public static String numberList = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";<br /> public static final String ERROR_MESSAGE = "such number is impossible!";</p> <p> private static BigInteger parseInt(String input, int radix) {<br /> BigInteger result = new BigInteger("0");<br /> BigInteger base = new BigInteger("1");<br /> for (int i = input.length() - 1; i >= 0; i--) {<br /> // System.out.println(base);<br /> result = result.add(new BigInteger(String.valueOf(numberList.indexOf(input.charAt(i)))).multiply(base));<br /> // System.out.println(result);<br /> base = base.multiply(new BigInteger(String.valueOf(radix)));<br /> }<br /> return result;<br /> }<br /> private static boolean isDivisible(int radix, int divisor, String input) {<br /> BigInteger dividend = parseInt(input, radix);<br /> // System.out.println(dividend + " % " + divisor + " == 0?");<br /> return dividend.divideAndRemainder(<br /> new BigInteger(String.valueOf(divisor)))[1].compareTo(new BigInteger("0")) == 0 ? true:false;<br /> }<br /> public static void main(String[] args){<br /> try {<br /> // File source = new File("input.txt");<br /> // Scanner cin = new Scanner(source);<br /> BufferedReader in = new BufferedReader(new InputStreamReader(System.in));<br /> String str = in.readLine();<br /> for (; str != null && str.length() > 0; str = in.readLine()) {<br /> // while(cin.hasNextLine()) {<br /> // String inputNumber = cin.nextLine();<br /> String inputNumber = str;<br /> int radix = -1;<br /> int index = -1;<br /> for (int i = inputNumber.length()-1; i >= 0 ; i--) {<br /> int temp = numberList.indexOf(inputNumber.charAt(i));<br /> if (temp >= index) {<br /> index = temp;<br /> }<br /> }<br /> if (index == 0 || index == 1) {<br /> radix = 2;<br /> } else if (index == -1) {<br /> radix = -1;<br /> } else {<br /> while(!isDivisible(index + 1, index, inputNumber) && index <= 61) {<br /> index++;<br /> }<br /> if (isDivisible(index + 1, index, inputNumber) && index <= 61) {<br /> radix = index + 1;<br /> }<br /> else {<br /> radix = -1;<br /> }<br /> }<br /> if (radix == -1) {<br /> System.out.println(ERROR_MESSAGE);<br /> } else {<br /> System.out.println(radix);<br /> }<br /> }<br /> } catch (Exception ex) {<br /> ex.printStackTrace();<br /> }<br /> }<br /> }<br />