3971587_tle.java

北大大牛代码 1240道题的原代码 超级权威

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	private Scanner in;
	private static BigInteger ONE = BigInteger.ONE;
	private static BigInteger ZERO = BigInteger.ZERO;
	private static BigInteger TEN = new BigInteger("10");

	public static void main(String[] args) {
		new Main().run();
	}

	private void run() {
		in = new Scanner(System.in);
		String subnumber = in.next();
		boolean find = false;
		BigInteger ans = ZERO;
	/*	
		String bstr = "";

		int v = 0;
		for (int i = 1; i < 13124; i++) {
			v += Integer.toString(i).length();
		}

		System.out.println(v + 1);
	*/
		for (int len = 1; !find && len < subnumber.length(); len++) {
			for (int st = 0; st <= len; st++) {
				if (st + len > subnumber.length()) {
					continue;
				}
				BigInteger now = new BigInteger(subnumber.substring(st, st + len));
				BigInteger last = now.subtract(ONE);
				if (st != 0) {	
					if (last.compareTo(ZERO) <= 0 
						|| last.toString().lastIndexOf(subnumber.substring(0, st))
						!= last.toString().length() - st) {
						continue;
					}
				}
				//System.out.println("now1 is " + now);
				BigInteger prev = now;
				boolean error = false;
				int delta = 0;
				for (int i = st + len; !error && i < subnumber.length(); i += len + delta) {
					if (i + len + delta< subnumber.length()) {
						if (allNine(prev)) {
							delta++;
						}
						BigInteger tmp = new BigInteger(subnumber.substring(i, i + len + delta));
						if (tmp.subtract(ONE).equals(prev)) {
							prev = tmp;
						} else {
							error = true;
						}
					} else {
						if (prev.add(ONE).toString().indexOf(subnumber.substring(i)) != 0) {
							error = true;
						}
					}
				}
				//System.out.println("now2 is " + now);
				if (!error) {
					find = true;
					if (st == 0) {
						ans = getPosition(now);
					} else {
						ans = getPosition(last).add(BigInteger.valueOf(last.toString().length() - st));
					}
				}
			}
		}
		if (find) {
			System.out.println(ans);
			return ;
		}
		while (true) {
		}
	/*
		for (int i = 1; i <= 20000; i++) {
			bstr += Integer.toString(i);
		}
		System.out.println("done " + bstr.length());
		int pos = bstr.indexOf(subnumber);
		System.out.println(bstr.substring(pos, pos + 20));
	*/
	}

	private boolean allNine(BigInteger num) {
		String str = num.toString();

		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) != '9') {
				return false;
			}
		}
		return true;
	}

	private BigInteger getPosition(BigInteger num) {
		//System.out.println("num is " + num);
		BigInteger ret = ZERO;
		int len = num.toString().length();

		for (int i = 1; i < len; i++) {
			ret = ret.add(BigInteger.valueOf(i * 9).multiply(TEN.pow(i - 1)));
		}
		ret  = ret.add(num.subtract(TEN.pow(len - 1)).multiply(BigInteger.valueOf(len)));
		return ret.add(ONE);
	}
}