結果

問題 No.491 10^9+1と回文
コンテスト
ユーザー tanzaku
提出日時 2017-03-10 23:48:31
言語 Java
(openjdk 23)
結果
AC  
実行時間 179 ms / 1,000 ms
コード長 1,576 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,837 ms
コンパイル使用メモリ 77,984 KB
実行使用メモリ 42,980 KB
最終ジャッジ日時 2024-10-01 08:22:15
合計ジャッジ時間 19,843 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 103
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class _491 {
	public static void main(String[] args) throws IOException {
		new _491().solve();
	}

	void solve() throws IOException {
		try (final Scanner in = new Scanner(System.in)) {
			n = in.nextLong();
			long ans = 0;
			for (int i = 1; i <= 9; i++) {
				ans += rec(i, 0, 0);
			}
			System.out.println(ans);
		}
	}
	
	long n;
	char[] cs;
	long x = 1000000000+1;
	long[] digits = new long[20];
	boolean palindrome(long cur) {
		int len = 0;
		while (cur > 0) {
			digits[len++] = cur % 10;
			cur /= 10;
		}
		for (int i = 0; i < len / 2; i++) {
			if (digits[i] != digits[len-1-i]) return false;
		}
		return true;
	}
	long rec(int len, int idx, long cur) {
		if (len % 2 == 0) {
			if (2*idx == len) {
				long c = cur;
				for (int i = 0; i < len / 2; i++) {
					cur = cur * 10 + c % 10;
					c /= 10;
				}
//				if (cur * x <= n) dump(cur);
				return cur <= n / x && palindrome(cur * x) ? 1 : 0;
			}
		} else {
			if (2*idx-1 == len) {
				long c = cur / 10;
				for (int i = 0; i < len / 2; i++) {
					cur = cur * 10 + c % 10;
					c /= 10;
				}
//				if (cur * x <= n) dump(cur);
				return cur <= n / x && palindrome(cur * x) ? 1 : 0;
			}
		}
		
		long ans = 0;
		for (int i = 0; i < 10; i++) {
			if (cur == 0 && i == 0) continue;
			ans += rec(len, idx + 1, cur * 10 + i);
		}
		return ans;
	}
	
	// for debug
	static void dump(Object... o) {
		System.err.println(Arrays.deepToString(o));
	}
}
0