結果

問題 No.260 世界のなんとか3
ユーザー t8m8⛄️t8m8⛄️
提出日時 2017-06-22 02:23:53
言語 Nim
(2.0.2)
結果
AC  
実行時間 388 ms / 2,000 ms
コード長 1,509 bytes
コンパイル時間 3,458 ms
コンパイル使用メモリ 73,440 KB
実行使用メモリ 30,592 KB
最終ジャッジ日時 2024-06-30 01:28:20
合計ジャッジ時間 8,947 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 312 ms
30,592 KB
testcase_04 AC 311 ms
30,464 KB
testcase_05 AC 60 ms
8,192 KB
testcase_06 AC 40 ms
6,400 KB
testcase_07 AC 211 ms
21,632 KB
testcase_08 AC 147 ms
15,872 KB
testcase_09 AC 83 ms
9,984 KB
testcase_10 AC 240 ms
23,936 KB
testcase_11 AC 224 ms
22,656 KB
testcase_12 AC 134 ms
14,720 KB
testcase_13 AC 39 ms
6,272 KB
testcase_14 AC 203 ms
20,840 KB
testcase_15 AC 54 ms
7,680 KB
testcase_16 AC 178 ms
18,560 KB
testcase_17 AC 139 ms
15,232 KB
testcase_18 AC 136 ms
14,848 KB
testcase_19 AC 175 ms
18,560 KB
testcase_20 AC 124 ms
13,824 KB
testcase_21 AC 111 ms
12,672 KB
testcase_22 AC 203 ms
20,840 KB
testcase_23 AC 20 ms
5,376 KB
testcase_24 AC 156 ms
16,768 KB
testcase_25 AC 195 ms
16,800 KB
testcase_26 AC 120 ms
16,768 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 316 ms
30,592 KB
testcase_29 AC 388 ms
30,464 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 49) Warning: Use the new 'sugar' module instead; future is deprecated [Deprecated]
/home/judge/data/code/Main.nim(1, 49) Warning: imported and not used: 'future' [UnusedImport]
/home/judge/data/code/Main.nim(1, 39) Warning: imported and not used: 'strscans' [UnusedImport]
/home/judge/data/code/Main.nim(1, 28) Warning: imported and not used: 'algorithm' [UnusedImport]

ソースコード

diff # 

import strutils, sequtils, algorithm, strscans, future

{.warning[SmallLshouldNotBeUsed]: off.}

const MOD = 1000000007

proc minus1(a: var string): string =
  for i in countDown(a.len-1, 0):
    if a[i] != '0':
      a[i] = ((a[i].int - '0'.int) - 1 + '0'.int).char
      break
    else:
      a[i] = '9'
  while a.len > 1 and a[0] == '0':
    a = a[1..a.len-1]
  result = a

proc solve(a: string, dp: var seq[seq[seq[seq[seq[int]]]]]): int =
  dp[0][0][0][0][0] = 1

  for i in 0..<a.len:
    for j in 0..1:
      for k in 0..1:
        for l in 0..2:
          for m in 0..7:
            for n in 0..9:
              if j == 0 and n > (a[i].int - '0'.int): break
              var
                p = if n < (a[i].int - '0'.int): 1 else: j
                q = if n == 3: 1 else: k
              dp[i+1][p][q][(n + l*10) mod 3][(n + m*10) mod 8] =
                  (dp[i+1][p][q][(n + l*10) mod 3][(n + m*10) mod 8] + dp[i][j][k][l][m]) mod MOD
  for j in 0..1:
    for k in 0..1:
      for l in 0..2:
        for m in 0..7:
          if (k == 1 or l == 0) and m != 0:
            result = (result + dp[a.len][j][k][l][m]) mod MOD

when isMainModule:
  var
    input = stdin.readLine.split
    (a, b) = (input[0].minus1, input[1])
    dpA = newSeqWith(a.len+1, newSeqWith(2, newSeqWith(2, newSeqWith(3, newSeq[int](8)))))
    dpB = newSeqWith(b.len+1, newSeqWith(2, newSeqWith(2, newSeqWith(3, newSeq[int](8)))))

  var
    ansA = solve(a, dpA)
    ansB = solve(b, dpB)

  echo((ansB - ansA + MOD) mod MOD)
0