Submission #2753885


Source Code Expand

Copy
lines = $stdin.read
array = lines.split("\n")
A,B = array[0].split(" ")

def calc_digit_sum(a)
  n = a.length

  dp = Array.new(18+2).map do
    Array.new(2).map do
      Array.new(2,0)
    end
  end # pos, less, has4

  #dp[0][0][0][0] = 1
  dp[0][0][0] = 1

  for i in 0...n
    for j in 0...2
      for k in 0...2
        #for l in 0...2
          lim = j.zero? ? a[i] : 9
          for d in 0...lim+1
            less,has4or9 = 0,0

            less = 1 if not j.zero? or d < lim
            has4or9 = 1 if not k.zero? or (d == 4 or d == 9)
            dp[i+1][less][has4or9] += dp[i][j][k]
          end
        #end
      end
    end
  end

  ans = 0
  for j in 0...2
    ans += dp[n][j][1]
  end
  ans
end

a = (A.to_i-1).to_s.split("").map(&:to_i).to_a
b = B.split("").map(&:to_i).to_a

# puts calc_digit_sum(b)
# puts calc_digit_sum(a)
puts calc_digit_sum(b) - calc_digit_sum(a)

Submission Info

Submission Time
Task D - 禁止された数字
User hiroyuking
Language Ruby (2.3.3)
Score 100
Code Size 932 Byte
Status
Exec Time 8 ms
Memory 3836 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask0_sample04.txt
Subtask1 30 / 30 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
Subtask2 70 / 70 subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask0_sample04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt
Case Name Status Exec Time Memory
subtask0_sample01.txt 7 ms 1788 KB
subtask0_sample02.txt 7 ms 1788 KB
subtask0_sample03.txt 7 ms 1788 KB
subtask0_sample04.txt 7 ms 1788 KB
subtask1_01.txt 7 ms 1788 KB
subtask1_02.txt 7 ms 1788 KB
subtask1_03.txt 7 ms 1788 KB
subtask1_04.txt 7 ms 1788 KB
subtask1_05.txt 7 ms 1788 KB
subtask1_06.txt 7 ms 1788 KB
subtask1_07.txt 7 ms 1788 KB
subtask1_08.txt 7 ms 1788 KB
subtask1_09.txt 7 ms 1788 KB
subtask1_10.txt 7 ms 1788 KB
subtask1_11.txt 7 ms 1788 KB
subtask1_12.txt 7 ms 1788 KB
subtask1_13.txt 7 ms 1788 KB
subtask2_01.txt 7 ms 1788 KB
subtask2_02.txt 7 ms 1788 KB
subtask2_03.txt 8 ms 1788 KB
subtask2_04.txt 8 ms 1788 KB
subtask2_05.txt 8 ms 1788 KB
subtask2_06.txt 8 ms 1788 KB
subtask2_07.txt 8 ms 1788 KB
subtask2_08.txt 8 ms 1788 KB
subtask2_09.txt 8 ms 1788 KB
subtask2_10.txt 7 ms 1788 KB
subtask2_11.txt 8 ms 3836 KB
subtask2_12.txt 8 ms 1788 KB
subtask2_13.txt 8 ms 1788 KB
subtask2_14.txt 8 ms 1788 KB
subtask2_15.txt 8 ms 1788 KB
subtask2_16.txt 8 ms 1788 KB
subtask2_17.txt 8 ms 1788 KB
subtask2_18.txt 8 ms 1788 KB
subtask2_19.txt 8 ms 1788 KB
subtask2_20.txt 8 ms 1788 KB
subtask2_21.txt 8 ms 1788 KB
subtask2_22.txt 8 ms 1788 KB