結果

問題 No.220 世界のなんとか2
コンテスト
ユーザー tutuz
提出日時 2018-06-15 22:29:11
言語 Java
(openjdk 23)
結果
AC  
実行時間 51 ms / 1,000 ms
コード長 4,115 bytes
コンパイル時間 2,256 ms
コンパイル使用メモリ 79,040 KB
実行使用メモリ 37,296 KB
最終ジャッジ日時 2024-06-30 15:02:35
合計ジャッジ時間 3,979 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 30;
	static int MOD = 1000000007;
	static int[] mh4 = { 0, -1, 1, 0 };
	static int[] mw4 = { -1, 0, 0, 1 };
	static int[] mh8 = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] mw8 = { -1, 0, 1, -1, 1, -1, 0, 1 };

	static class TaskX {

		char[] s;
		long[][][] memo1;
		long[][][] memo2;
		long[][][][] memo3;

		public void solve(int testNumber, InputReader in, PrintWriter out) {

			StringBuffer tmp = new StringBuffer();
			tmp.append("1");
			int p = in.nextInt();
			for (int i = 0; i < p; i++) {
				tmp.append("0");
			}
			s = tmp.toString().toCharArray();
			int len = s.length+1;

			// 3の倍数
			memo1 = new long[len+1][3][2];
			for (int i = 0; i < len+1; i++) {
				for (int j = 0; j < 3; j++) {
					Arrays.fill(memo1[i][j], -1);
				}
			}
			long n1 = dfs1(0, 0, 1)-1;

			// 3を含む数
			memo2 = new long[len+1][2][2];
			for (int i = 0; i < len+1; i++) {
				for (int j = 0; j < 2; j++) {
					Arrays.fill(memo2[i][j], -1);
				}
			}
			long n2 = dfs2(0, 0, 1);

			// 3の倍数かつ3を含む数
			memo3 = new long[len+1][3][2][2];
			for (int i = 0; i < len+1; i++) {
				for (int j = 0; j < 3; j++) {
					for (int k = 0; k < 2; k++) {
						Arrays.fill(memo3[i][j][k], -1);
					}
				}
			}
			long n3 = dfs3(0, 0, 0, 1);

			out.println(n1+n2-n3);

		}

		long dfs1(int i, int sum, int tight) {

			if (memo1[i][sum][tight] >= 0) {
				return memo1[i][sum][tight];
			}
			if (i == s.length) return sum % 3 == 0 ? 1 : 0;

			int d = s[i]-'0';
			long ret = 0;
			for (int e = 0; e <= (tight == 1 ? d : 9); e++) {
				ret += dfs1(i+1, (sum+e)%3, tight == 1 && d == e ? 1 : 0);
			}

			return memo1[i][sum][tight] = ret;
		}

		long dfs2(int i,int mul, int tight) {

			if (memo2[i][mul][tight] >= 0) {
				return memo2[i][mul][tight];
			}
			if (i == s.length) return mul == 1 ? 1 : 0;

			long ret = 0;
			int d = s[i]-'0';
			for (int e = 0; e <= (tight == 1 ? d : 9); e++) {
				ret += dfs2(i+1, e == 3 || mul == 1 ? 1 : 0, tight == 1 && d == e ? 1 : 0);
			}

			return memo2[i][mul][tight] = ret;
		}

		long dfs3(int i, int sum, int mul, int tight) {

			if (memo3[i][sum][mul][tight] >= 0) {
				return memo3[i][sum][mul][tight];
			}
			if (i == s.length) return sum % 3 == 0 && mul == 1 ? 1 : 0;

			long ret = 0;
			int d = s[i]-'0';
			for (int e = 0; e <= (tight == 1 ? d : 9); e++) {
				ret += dfs3(i+1, (sum+e)%3, e == 3 || mul == 1 ? 1 : 0, tight == 1 && d == e ? 1 : 0);
			}

			return memo3[i][sum][mul][tight] = ret;
		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextString());
		}

		public long nextLong() {
			return Long.parseLong(nextString());
		}

		public double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}
	}

}
0