結果

問題 No.2032 Let's Write Multiples!!
ユーザー ygussanyygussany
提出日時 2022-07-24 15:04:18
言語 C
(gcc 12.3.0)
結果
TLE  
実行時間 -
コード長 1,754 bytes
コンパイル時間 1,075 ms
コンパイル使用メモリ 31,468 KB
実行使用メモリ 8,860 KB
最終ジャッジ日時 2024-07-19 02:14:11
合計ジャッジ時間 7,036 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 22 ms
5,376 KB
testcase_02 AC 20 ms
5,376 KB
testcase_03 AC 20 ms
5,376 KB
testcase_04 AC 25 ms
5,376 KB
testcase_05 TLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

int solve_enumerate(int L, int R, int K, int C)
{
	int X, Y, ans = 0;
	for (X = (L + K - 1) / K * K; X <= R; X += K) for (Y = X; Y > 0; Y /= 10) if (Y % 10 == C) ans++;
	return ans;
}

const int dig[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

int solve_DP(int R, int K, int C)
{
	static int dp[2][32001], r[10];
	int d, i, j, k, RR, cur, prev, ans = 0;
	for (d = 0, RR = R; RR > 0; d++, RR /= 10) r[d] = RR % 10;
	for (k = 0; k < K; k++) {
		dp[0][k] = 0;
		dp[1][k] = 0;
	}
	for (d--, cur = 1, prev = 0; d >= 0; d--, cur ^= 1, prev ^= 1) {
		for (k = 0; k < K; k++) dp[cur][k] = 0;
		for (k = 0; k < K; k++) {
			if (dp[prev][k] == 0) continue;
			for (i = 0, j = k * 10 % K; i <= 9; i++, j++) {
				if (j == K) j = 0;
				dp[cur][j] += dp[prev][k];
				if (i == C) {
					if (j * dig[d] % K != 0) ans += dp[prev][k] * ((dig[d] - 1 + j * dig[d] % K) / K);
					else ans += dp[prev][k] * ((dig[d] - 1 + K) / K);
				}
			}
			dp[prev][k] = 0;
		}
		for (i = 0, j = RR * 10 % K; i < r[d]; i++, j++) {
			if (j == K) j = 0;
			dp[cur][j]++;
			if (i == C) {
				if (j * dig[d] % K != 0) ans += (dig[d] - 1 + j * dig[d] % K) / K;
				else ans += (dig[d] - 1 + K) / K;
			}
		}
		if (j == K) j = 0;
		RR = j;
		if (r[d] == C) {
			if (j * dig[d] % K != 0) ans += (R % dig[d] + j * dig[d] % K) / K;
			else ans += (R % dig[d] + K) / K;
		}
	}
	return ans;
}

int main()
{
	int T, L, R, K, C;
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d %d", &L, &R, &K, &C);
		if ((R - L) / K <= 32000) printf("%d\n", solve_enumerate(L, R, K, C));
		else printf("%d\n", solve_DP(R, K, C) - solve_DP(L - 1, K, C));
	}
	fflush(stdout);
	return 0;
}
0