第17回オフラインリアルタイムどう書く参考問題の解答

Scheherazade.java

import static org.junit.Assert.assertEquals;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

/**
 * Question: http://nabetani.sakura.ne.jp/hena/ord17scheherazade/
 */
public class Scheherazade {
	public String solve(String input) {
		BigInteger dn = parse(input);

		StringBuilder sb = new StringBuilder();
		for (BigInteger base = BigInteger.valueOf(2); base.compareTo(dn) < 0; base = base
				.add(BigInteger.ONE)) {
			List<BigInteger> num = getNum(dn, base);
			if (0 < num.size() && isPalinum(num)) {
				sb.append(String.valueOf(base));
				sb.append(',');
			}
		}
		if (sb.length() == 0) {
			return "-";
		}
		return sb.substring(0, sb.length() - 1);
	}

	boolean isPalinum(List<BigInteger> num) {
		for (int i = 0; i < num.size() / 2; i++) {
			if (0 != num.get(i).compareTo(num.get(num.size() - 1 - i))) {
				return false;
			}
		}
		return true;
	}

	List<BigInteger> getNum(BigInteger origin, BigInteger base) {
		List<BigInteger> result = new ArrayList<>();
		BigInteger answer = origin;
		for (; 0 < answer.compareTo(BigInteger.ZERO);) {
			BigInteger[] dr = answer.divideAndRemainder(base);
			result.add(dr[1]);
			answer = dr[0];
		}
		return result;
	}

	BigInteger parse(String input) {
		return new BigInteger(input);
	}

	@Test
	public void testGetNum() throws Exception {
		Scheherazade target = new Scheherazade();
		List<BigInteger> expected = new ArrayList<>();
		expected.add(BigInteger.ZERO);
		expected.add(BigInteger.ONE);
		expected.add(BigInteger.ZERO);
		expected.add(BigInteger.ONE);

		List<BigInteger> actual = target.getNum(BigInteger.valueOf(10),
				BigInteger.valueOf(2));
		for (int i = 0; i < actual.size(); i++) {
			assertEquals(0, expected.get(i).compareTo(actual.get(i)));
		}
	}

	private int counter = 0;

	void test(String input, String expected) throws Exception {
		Scheherazade target = new Scheherazade();
		// assertEquals(expected, target.solve(input));
		String answer = target.solve(input);
		System.out.println(counter++ + ": "
				+ (expected.equals(answer) ? "ok" : "*** NG ***" + answer));
	}

	@Test
	public void testSceherazade() throws Exception {
		/* 0 */test("17301", "5,38,100,218,236,5766,17300");
		/* 1 */test("2", "-");
		/* 2 */test("1", "-");
		/* 3 */test("3", "2");
		/* 4 */test("4", "3");
		/* 5 */test("5", "2,4");
		/* 6 */test("6", "5");
		/* 7 */test("10", "3,4,9");
		/* 8 */test("101", "10,100");
		/* 9 */test("1001", "10,25,76,90,142,1000");
		/* 10 */test("10001", "10,24,30,42,80,100,136,10000");
		/* 11 */test("1212", "22,100,201,302,403,605,1211");
		/* 12 */test("123412", "62,100,205,215,30852,61705,123411");
		/* 13 */test("5179", "5178");
		/* 14 */test("4919", "4918");
		/* 15 */test("5791", "5790");
		/* 16 */test("5498", "2748,5497");
		/* 17 */test("453", "150,452");
		/* 18 */test("134", "66,133");
		/* 19 */test("8489", "27,652,8488");
		/* 20 */test("1234", "22,616,1233");
		/* 21 */test("5497", "41,238,5496");
		/* 22 */test("4763", "19,35,432,4762");
		/* 23 */test("3974", "17,27,1986,3973");
		/* 24 */test("3521", "44,55,502,3520");
		/* 25 */test("5513", "20,38,53,148,5512");
		/* 26 */test("8042", "23,29,60,4020,8041");
		/* 27 */test("7442", "37,60,121,3720,7441");
		/* 28 */test("4857", "25,1618,4856");
		/* 29 */test("22843", "49,69,91,141,430,22842");
		/* 30 */test("194823", "84,121,21646,64940,194822");
		/* 31 */test("435697", "160,169,235,626,1822,435696");
		/* 32 */test("142", "3,7,70,141");
		/* 33 */test("886", "5,14,442,885");
		/* 34 */test("3102", "7,65,93,140,281,516,1033,1550,3101");
		/* 35 */test("17326", "11,28,99,105,8662,17325");
		/* 36 */test("32982", "13,72,238,477,716,1433,5496,10993,16490,32981");
		/* 37 */test("36", "5,8,11,17,35");
		/* 38 */test("37", "6,36");
		/* 39 */test("251", "8,250");
		/* 40 */test("252", "5,10,17,20,27,35,41,62,83,125,251");
		/* 41 */test("253", "12,14,22,252");
		/* 42 */test("6643", "2,3,9,81,90,510,948,6642");
		/* 43 */test(
				"5040",
				"71,79,83,89,104,111,119,125,139,143,167,179,209,239,251,279,314,335,359,419,503,559,629,719,839,1007,1259,1679,2519,5039");
		/* 44 */test(
				"9240",
				"23,38,62,104,109,119,131,139,153,164,167,209,219,230,263,279,307,329,384,419,439,461,615,659,769,839,923,1154,1319,1539,1847,2309,3079,4619,9239");
	}
}