Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-06SRM300台を練習していく part8

SRM 320 ExtraordinarilyLarge

|  SRM 320 ExtraordinarilyLarge - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 320 ExtraordinarilyLarge - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6398

x, yの末尾についている階乗(!)の数をカウントし、同数だけ取り除く。(x! = y! なら x = y だから)

そして 0! = 1に注意してシミュレーション。


import java.math.BigInteger;

public class ExtraordinarilyLarge {

	public int compareMultiply(int times, BigInteger basex, BigInteger basey) {
		for (int yp = 0 ; yp < times ; yp++) {
			BigInteger cy = BigInteger.valueOf(basey.longValue());
			if (basey.longValue() == 0) {
				cy = BigInteger.valueOf(1);
			} else {
				for (long v = basey.longValue() - 1 ; v >= 2 ; v--) {
					cy = cy.multiply(BigInteger.valueOf(v));
					if (cy.compareTo(basex) > 0) {
						yp = times;
						break;
					}
				}
			}
			basey = cy.abs();
		}
		return basex.compareTo(basey);
	}
	
	public String compare(String x, String y) {
		int xx = 0, yy = 0;
		for (int l = x.length() - 1 ; l >= 0 ; l--) {
			if (x.charAt(l) == '!') {
				xx++;
			}
 		}
		for (int l = y.length() - 1 ; l >= 0 ; l--) {
			if (y.charAt(l) == '!') {
				yy++;
			}
 		}
		int removes = Math.min(xx, yy);
		long lbasex = Long.valueOf(x.substring(0, x.length() - xx));
		long lbasey = Long.valueOf(y.substring(0, y.length() - yy));
		if (lbasex == 0 && xx > 0) {
			lbasex = 1;
		}
		if (lbasey == 0 && yy > 0) {
			lbasey = 1;
		}
		
		BigInteger basex = BigInteger.valueOf(lbasex);
		BigInteger basey = BigInteger.valueOf(lbasey);
		xx -= removes;
		yy -= removes;
		int cp = -2;
		if (xx == 0 && yy == 0) {
			cp = basex.compareTo(basey);
		}
		if (xx == 0) {
			cp = compareMultiply(yy, basex, basey);
		}
		if (yy == 0) {
			cp = compareMultiply(xx, basey, basex) * -1;
		}
		if (cp == -1) {
			return "x<y";
		} else if (cp == 0) {
			return "x=y";
		} else {
			return "x>y";
		}
	}
}