3802287_ac_438ms_4828k.java

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

import java.util.Scanner;

public class Main {

	private long[] f = new long[50];

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main().run();
	}

	private void init() {
		f[0] = 1l;
		f[1] = 2l;
		for (int i = 2; i < 50; i++) {
			f[i] = f[i - 1] + f[i - 2];
		}
	}

	private void run() {
		Scanner in = new Scanner(System.in);
		String X, Y, Z;
		long x, y, z;

		init();
		while (in.hasNext()) {
			X = in.next();
			Y = in.next();
			x = turn(X);
			y = turn(Y);
			z = x + y;
			X = change(x);
			Y = change(y);
			Z = change(z);
			for (int i = 0; i < Z.length() - X.length() + 2; i++) {
				System.out.print(' ');
			}
			System.out.println(X);
			System.out.print('+');
			for (int i = 1; i < Z.length() - Y.length() + 2; i++) {
				System.out.print(' ');
			}
			System.out.println(Y);
			System.out.print("  ");
			for (int i = 0; i < Z.length(); i++) {
				System.out.print('-');
			}
			System.out.println();
			System.out.println("  " + Z + "\n");
		}
	}

	private String change(long z) {
		// TODO Auto-generated method stub
		if (z == 0) {
			return "0";
		}
		String ret = "";
		boolean[] mark = new boolean[50];

		while (z != 0) {
			for (int i = 49; i >= 0; i--) {
				if (f[i] <= z) {
					mark[i] = true;
					z -= f[i];
					break;
				}
			}
		}
		for (int i = 49; i >= 0; i--) {
			if (mark[i] == true) {
				for (int j = i; j >= 0; j--) {
					if (mark[j] == true) {
						ret += "1";
					} else {
						ret += "0";
					}
				}
				break;
			}
		}
		return ret;
	}

	private long turn(String x) {
		// TODO Auto-generated method stub
		long ret = 0;
		int length = x.length();
		for (int i = length - 1; i >= 0; i--) {
			if (x.charAt(i) == '1') {
				ret += f[length - i - 1];
			}
		}
		return ret;
	}

}