結果
問題 | No.315 世界のなんとか3.5 |
ユーザー | eitaho |
提出日時 | 2015-12-08 01:44:56 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 828 ms / 2,000 ms |
コード長 | 4,988 bytes |
コンパイル時間 | 1,079 ms |
コンパイル使用メモリ | 118,496 KB |
実行使用メモリ | 36,684 KB |
最終ジャッジ日時 | 2024-09-14 19:00:25 |
合計ジャッジ時間 | 13,233 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 32 ms
25,120 KB |
testcase_01 | AC | 31 ms
27,284 KB |
testcase_02 | AC | 58 ms
25,348 KB |
testcase_03 | AC | 32 ms
25,248 KB |
testcase_04 | AC | 33 ms
25,116 KB |
testcase_05 | AC | 33 ms
25,116 KB |
testcase_06 | AC | 39 ms
27,128 KB |
testcase_07 | AC | 34 ms
27,160 KB |
testcase_08 | AC | 32 ms
27,388 KB |
testcase_09 | AC | 32 ms
25,376 KB |
testcase_10 | AC | 32 ms
25,468 KB |
testcase_11 | AC | 32 ms
23,092 KB |
testcase_12 | AC | 235 ms
30,028 KB |
testcase_13 | AC | 236 ms
28,372 KB |
testcase_14 | AC | 397 ms
33,788 KB |
testcase_15 | AC | 396 ms
31,616 KB |
testcase_16 | AC | 402 ms
33,664 KB |
testcase_17 | AC | 395 ms
33,920 KB |
testcase_18 | AC | 234 ms
30,200 KB |
testcase_19 | AC | 233 ms
30,076 KB |
testcase_20 | AC | 232 ms
30,436 KB |
testcase_21 | AC | 228 ms
28,388 KB |
testcase_22 | AC | 397 ms
31,748 KB |
testcase_23 | AC | 390 ms
33,664 KB |
testcase_24 | AC | 392 ms
31,732 KB |
testcase_25 | AC | 392 ms
33,532 KB |
testcase_26 | AC | 388 ms
31,612 KB |
testcase_27 | AC | 391 ms
33,656 KB |
testcase_28 | AC | 389 ms
33,788 KB |
testcase_29 | AC | 734 ms
34,764 KB |
testcase_30 | AC | 736 ms
34,896 KB |
testcase_31 | AC | 736 ms
36,560 KB |
testcase_32 | AC | 755 ms
36,684 KB |
testcase_33 | AC | 401 ms
33,680 KB |
testcase_34 | AC | 828 ms
33,560 KB |
testcase_35 | AC | 784 ms
36,684 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.IO;using System.Linq;using System.Text;using System.Collections.Generic;using System.Diagnostics;using System.Numerics;using Enu = System.Linq.Enumerable;class Program{static readonly int Mod = (int)1e9 + 7;void Add(ref int a, int b) { if ((a += b) >= Mod) a -= Mod; }public void Solve(){string SA = Reader.String(), SB = Reader.String(), C = Reader.String();int[] B = SB.Select(c => c - '0').ToArray();int[] A = SA.Select(c => c - '0').ToArray();for (int i = A.Length - 1; i >= 0; i--){if (A[i]-- > 0) break;else A[i] = 9;}if (A[0] == 0 && A.Length > 1) A = A.Skip(1).ToArray();Console.WriteLine((Count(B, C) - Count(A, C) + Mod) % Mod);}private int Count(int[] A, string C){int res = 0;int tail = A.Length - C.Length - 2;if (tail <= 0){int N = 0;for (int i = 0; i < A.Length; i++) N = N * 10 + A[i];int X = int.Parse(C);for (int i = 0; i <= N; i++)if ((i % 3 == 0 || (i + "").IndexOf('3') >= 0) && i % X != 0)res++;return res;}var dp = DP(A, tail);var dp1 = dp.Item1;var dp2 = dp.Item2;string sub = "";for (int i = tail; i < tail + 3; i++)if (i >= 0) sub += A[i];int to = int.Parse(sub);for (int mod = 0; mod < 3; mod++)for (int has3 = 0; has3 < 2; has3++)for (int less = 0; less < 2; less++){if (mod == 0 || has3 == 1)Add(ref res, dp1[mod, has3, less]);for (int last = 0; last < 1000; last += 8){if (last > to && less == 0) break;if ((mod + last) % 3 == 0 || has3 == 1 || (last + "").IndexOf('3') >= 0)res = (res + Mod - dp2[mod, has3, less]) % Mod;}}return res;}private Tuple<int[, ,], int[, ,]> DP(int[] A, int tail){var dp = new int[3, 2, 2];var res2 = new int[3, 2, 2];dp[0, 0, 0] = 1;res2[0, 0, 0] = 1;for (int i = 0; i < A.Length; i++){if (i == tail) res2 = (int[, ,])dp.Clone();var nextdp = new int[3, 2, 2];for (int mod = 0; mod < 3; mod++)for (int has3 = 0; has3 < 2; has3++)for (int less = 0; less < 2; less++)if (dp[mod, has3, less] > 0)for (int d = 0; d <= 9; d++){if (less == 0 && d > A[i]) break;int nextmod = (mod + d) % 3;int nexthas3 = has3 | (d == 3 ? 1 : 0);int nextless = less | (d < A[i] ? 1 : 0);Add(ref nextdp[nextmod, nexthas3, nextless], dp[mod, has3, less]);}dp = nextdp;}return Tuple.Create(dp, res2);}}class Entry { static void Main() { new Program().Solve(); } }class Reader{private static TextReader reader = Console.In;private static readonly char[] separator = { ' ' };private static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;private static string[] A = new string[0];private static int i;private static void Init() { A = new string[0]; }public static void Set(TextReader r) { reader = r; Init(); }public static void Set(string file) { reader = new StreamReader(file); Init(); }public static bool HasNext() { return CheckNext(); }public static string String() { return Next(); }public static int Int() { return int.Parse(Next()); }public static long Long() { return long.Parse(Next()); }public static double Double() { return double.Parse(Next()); }public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }public static int[] IntArray(int N) { return Enu.Range(0, N).Select(i => Int()).ToArray(); }public static int[][] IntTable(int H) { return Enu.Range(0, H).Select(i => IntLine()).ToArray(); }public static string[] StringArray(int N) { return Enu.Range(0, N).Select(i => Next()).ToArray(); }public static string Line() { return reader.ReadLine().Trim(); }private static string[] Split(string s) { return s.Split(separator, op); }private static string Next() { CheckNext(); return A[i++]; }private static bool CheckNext(){if (i < A.Length) return true;string line = reader.ReadLine();if (line == null) return false;if (line == "") return CheckNext();A = Split(line);i = 0;return true;}}