A number display board shows each digit with 7 bars.
The number of bars lit for each digit is: 0 lights 6, 1 lights 2, 2 lights 5, 3 lights 5, 4 lights 4, 5 lights 5, 6 lights 6, 7 lights 3, 8 lights 7, 9 lights 6.
When an integer x is shown, the digits of x written in decimal without leading zeros are lit.
0 is shown as the single digit 0.
The bar count of x is the sum of the bar counts of its lit digits.
For example, the bar count of 108 is 2 + 6 + 7 = 15, and the bar count of 7 is 3.
For each question, print how many integers from L to R inclusive have a bar count of exactly S.
If there are none, print 0.
Input
The first line has the number of questions Q, and each of the next Q lines has a question "L R S" separated by single spaces. 1 ≤ Q ≤ 2,000, 0 ≤ L ≤ R ≤ 10^15 (1,000,000,000,000,000), 1 ≤ S ≤ 200. All are integers
Output
Q lines: one count per question (plain digits, no commas)
Example 1 · stdin
3
1 20 5
0 9 6
100 200 15
stdout
4
3
6
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
R goes up to 10^15, so you cannot count one by one. Use digit DP: ways[k][s] = the number of ways to arrange any k digits so their bar counts sum to s (k = 16 and s ≤ 112 are enough). Write count(n) = 'how many numbers from 0 to n have bar count S', and the answer is count(R) − count(L − 1). count(n) has three parts: ① 0 itself (6 bars) ② numbers with fewer digits than n — the first digit is 1 to 9 and the other k − 1 digits come from ways ③ numbers with as many digits as n — follow n's digits from the front, and when you first pick a smaller digit d at position i, the rest is ways[digits left][bars left] (the first position starts at 1). Count n itself too when you follow it to the end. Example: from 1 to 20 the numbers with 5 bars are 2, 3, 5 and 17 (2 + 3), so 4. Trap one: counting short numbers padded with leading zeros to the same length, as the common digit-sum solution does, is wrong — for digit sums a 0 adds nothing, but here every leading 0 counts as 6 lit bars. Count each length separately, or put 'have we started writing digits yet' in the state. Trap two: forgetting 0 itself leaves a question with L = 0 and S = 6 one short. Trap three: subtracting count(R) − count(L) drops L itself. Trap four: some displays draw 7 with 4 bars and 6 and 9 with 5 — use this problem's table (7 has 3, 6 and 9 have 6). Trap five: answers come close to 10^15, past a 32-bit int (about 2.1 billion). C and C++ need long long, Java and C# long (in Java, += of a long into an int compiles and silently truncates because compound assignment casts for you; in C# it is a compile error), and read the input with Long.parseLong, long.Parse or %lld. Python integers have no limit, and JavaScript, TypeScript and Craykon numbers are doubles, exact up to 2^53 (about 9×10^15), so they work as they are. Turning a number into digits: Python str(n), JS/TS String(n), Java Long.toString(n), C# n.ToString(), C snprintf(buf, size, "%lld", n), C++ std::to_string(n), Craykon "" + n (10^15 is written without an exponent) and digits[i].ToNumber().
Pythonmain.py · 53 lines
import sysSEG = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6] # 숫자 0~9를 띄울 때 켜지는 막대 수MAXLEN = 16 # 10^15는 16자리MAXS = 7 * MAXLEN# ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수ways = [[0] * (MAXS + 1) for _ in range(MAXLEN + 1)]ways[0][0] = 1for k in range(1, MAXLEN + 1): for s in range(MAXS + 1): if ways[k - 1][s]: for d in range(10): ways[k][s + SEG[d]] += ways[k - 1][s]def tail(k, s): """뒤에 숫자 k개가 남았고 막대를 s개 더 켜야 할 때의 경우의 수""" return ways[k][s] if 0 <= s <= MAXS else 0def count_upto(n, S): """0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수""" if n < 0: return 0 total = 1 if S == SEG[0] else 0 # 0은 숫자 0 하나로 띄운다 if n == 0: return total digits = str(n) length = len(digits) # n보다 자릿수가 적은 수: 첫 숫자는 1~9(앞에 0을 붙이지 않는다), 나머지는 아무 숫자 for k in range(1, length): for d in range(1, 10): total += tail(k - 1, S - SEG[d]) # n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 rest = S for i, ch in enumerate(digits): c = int(ch) for d in range(1 if i == 0 else 0, c): total += tail(length - 1 - i, rest - SEG[d]) rest -= SEG[c] if rest == 0: total += 1 # n 자신 return totaldata = sys.stdin.read().split()q = int(data[0])out = []for i in range(q): lo, hi, s = int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i]) out.append(str(count_upto(hi, s) - count_upto(lo - 1, s)))print("\n".join(out))
JavaScriptmain.js · 50 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const SEG = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]; // 숫자 0~9를 띄울 때 켜지는 막대 수const MAXLEN = 16; // 10^15는 16자리const MAXS = 7 * MAXLEN;// ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수// 가장 큰 값도 10^15쯤이라 number(2^53까지 정확)로 충분하다const ways = Array.from({ length: MAXLEN + 1 }, () => new Array(MAXS + 1).fill(0));ways[0][0] = 1;for (let k = 1; k <= MAXLEN; k++) { for (let s = 0; s <= MAXS; s++) { if (ways[k - 1][s] === 0) continue; for (let d = 0; d < 10; d++) ways[k][s + SEG[d]] += ways[k - 1][s]; }}const tail = (k, s) => (s >= 0 && s <= MAXS ? ways[k][s] : 0);// 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수function countUpto(n, S) { if (n < 0) return 0; let total = S === SEG[0] ? 1 : 0; // 0은 숫자 0 하나로 띄운다 if (n === 0) return total; const digits = String(n); const len = digits.length; // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (let k = 1; k < len; k++) { for (let d = 1; d <= 9; d++) total += tail(k - 1, S - SEG[d]); } // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 let rest = S; for (let i = 0; i < len; i++) { const c = digits.charCodeAt(i) - 48; for (let d = i === 0 ? 1 : 0; d < c; d++) total += tail(len - 1 - i, rest - SEG[d]); rest -= SEG[c]; } if (rest === 0) total += 1; // n 자신 return total;}const q = Number(data[0]);const out = [];for (let i = 0; i < q; i++) { const lo = Number(data[1 + 3 * i]); const hi = Number(data[2 + 3 * i]); const s = Number(data[3 + 3 * i]); out.push(countUpto(hi, s) - countUpto(lo - 1, s));}console.log(out.join("\n"));
TypeScriptmain.ts · 54 lines
import { readFileSync } from "node:fs";const data: string[] = readFileSync(0, "utf8").trim().split(/\s+/);const SEG: readonly number[] = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]; // 숫자 0~9를 띄울 때 켜지는 막대 수const MAXLEN = 16; // 10^15는 16자리const MAXS = 7 * MAXLEN;// ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수// 가장 큰 값도 10^15쯤이라 number(2^53까지 정확)로 충분하다const ways: number[][] = Array.from({ length: MAXLEN + 1 }, () => new Array<number>(MAXS + 1).fill(0));ways[0][0] = 1;for (let k = 1; k <= MAXLEN; k++) { for (let s = 0; s <= MAXS; s++) { if (ways[k - 1][s] === 0) continue; for (let d = 0; d < 10; d++) ways[k][s + SEG[d]] += ways[k - 1][s]; }}function tail(k: number, s: number): number { return s >= 0 && s <= MAXS ? ways[k][s] : 0;}// 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수function countUpto(n: number, S: number): number { if (n < 0) return 0; let total = S === SEG[0] ? 1 : 0; // 0은 숫자 0 하나로 띄운다 if (n === 0) return total; const digits = String(n); const len = digits.length; // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (let k = 1; k < len; k++) { for (let d = 1; d <= 9; d++) total += tail(k - 1, S - SEG[d]); } // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 let rest = S; for (let i = 0; i < len; i++) { const c = digits.charCodeAt(i) - 48; for (let d = i === 0 ? 1 : 0; d < c; d++) total += tail(len - 1 - i, rest - SEG[d]); rest -= SEG[c]; } if (rest === 0) total += 1; // n 자신 return total;}const q = Number(data[0]);const out: number[] = [];for (let i = 0; i < q; i++) { const lo = Number(data[1 + 3 * i]); const hi = Number(data[2 + 3 * i]); const s = Number(data[3 + 3 * i]); out.push(countUpto(hi, s) - countUpto(lo - 1, s));}console.log(out.join("\n"));
JavaMain.java · 55 lines
import java.io.*;import java.util.*;public class Main { static final int[] SEG = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // 숫자 0~9를 띄울 때 켜지는 막대 수 static final int MAXLEN = 16; // 10^15는 16자리 static final int MAXS = 7 * MAXLEN; // ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수 static final long[][] ways = new long[MAXLEN + 1][MAXS + 1]; static long tail(int k, int s) { return s >= 0 && s <= MAXS ? ways[k][s] : 0; } // 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수(답이 10^15까지 가서 long) static long countUpto(long n, int S) { if (n < 0) return 0; long total = S == SEG[0] ? 1 : 0; // 0은 숫자 0 하나로 띄운다 if (n == 0) return total; String digits = Long.toString(n); int len = digits.length(); // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (int k = 1; k < len; k++) for (int d = 1; d <= 9; d++) total += tail(k - 1, S - SEG[d]); // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 int rest = S; for (int i = 0; i < len; i++) { int c = digits.charAt(i) - '0'; for (int d = i == 0 ? 1 : 0; d < c; d++) total += tail(len - 1 - i, rest - SEG[d]); rest -= SEG[c]; } if (rest == 0) total++; // n 자신 return total; } public static void main(String[] args) throws IOException { ways[0][0] = 1; for (int k = 1; k <= MAXLEN; k++) for (int s = 0; s <= MAXS; s++) if (ways[k - 1][s] != 0) for (int d = 0; d < 10; d++) ways[k][s + SEG[d]] += ways[k - 1][s]; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(br.readLine().trim()); StringBuilder sb = new StringBuilder(); for (int i = 0; i < q; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); long lo = Long.parseLong(st.nextToken()); long hi = Long.parseLong(st.nextToken()); int s = Integer.parseInt(st.nextToken()); sb.append(countUpto(hi, s) - countUpto(lo - 1, s)).append('\n'); } System.out.print(sb); }}
C#Main.cs · 57 lines
using System;using System.Text;class Program{ static readonly int[] Seg = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 }; // 숫자 0~9를 띄울 때 켜지는 막대 수 const int MaxLen = 16; // 10^15는 16자리 const int MaxS = 7 * MaxLen; // ways[k, s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수 static readonly long[,] Ways = new long[MaxLen + 1, MaxS + 1]; static long Tail(int k, int s) => s >= 0 && s <= MaxS ? Ways[k, s] : 0; // 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수(답이 10^15까지 가서 long) static long CountUpto(long n, int S) { if (n < 0) return 0; long total = S == Seg[0] ? 1 : 0; // 0은 숫자 0 하나로 띄운다 if (n == 0) return total; string digits = n.ToString(); int len = digits.Length; // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (int k = 1; k < len; k++) for (int d = 1; d <= 9; d++) total += Tail(k - 1, S - Seg[d]); // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 int rest = S; for (int i = 0; i < len; i++) { int c = digits[i] - '0'; for (int d = i == 0 ? 1 : 0; d < c; d++) total += Tail(len - 1 - i, rest - Seg[d]); rest -= Seg[c]; } if (rest == 0) total++; // n 자신 return total; } static void Main() { Ways[0, 0] = 1; for (int k = 1; k <= MaxLen; k++) for (int s = 0; s <= MaxS; s++) if (Ways[k - 1, s] != 0) for (int d = 0; d < 10; d++) Ways[k, s + Seg[d]] += Ways[k - 1, s]; int q = int.Parse(Console.ReadLine()!.Trim()); var sb = new StringBuilder(); for (int i = 0; i < q; i++) { var p = Console.ReadLine()!.Split(' ', StringSplitOptions.RemoveEmptyEntries); long lo = long.Parse(p[0]); long hi = long.Parse(p[1]); int s = int.Parse(p[2]); sb.Append(CountUpto(hi, s) - CountUpto(lo - 1, s)).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 52 lines
#include <array>#include <iostream>#include <string>constexpr int MAXLEN = 16; // 10^15는 16자리constexpr int MAXS = 7 * MAXLEN;constexpr std::array<int, 10> SEG = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // 숫자 0~9를 띄울 때 켜지는 막대 수// ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수std::array<std::array<long long, MAXS + 1>, MAXLEN + 1> ways{};long long tail(int k, int s) { return s >= 0 && s <= MAXS ? ways[k][s] : 0; }// 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수(답이 10^15까지 가서 long long)long long countUpto(long long n, int S) { if (n < 0) return 0; long long total = S == SEG[0] ? 1 : 0; // 0은 숫자 0 하나로 띄운다 if (n == 0) return total; const std::string digits = std::to_string(n); const int len = static_cast<int>(digits.size()); // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (int k = 1; k < len; k++) for (int d = 1; d <= 9; d++) total += tail(k - 1, S - SEG[d]); // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 int rest = S; for (int i = 0; i < len; i++) { int c = digits[i] - '0'; for (int d = i == 0 ? 1 : 0; d < c; d++) total += tail(len - 1 - i, rest - SEG[d]); rest -= SEG[c]; } if (rest == 0) total++; // n 자신 return total;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); ways[0][0] = 1; for (int k = 1; k <= MAXLEN; k++) for (int s = 0; s <= MAXS; s++) if (ways[k - 1][s]) for (int d = 0; d < 10; d++) ways[k][s + SEG[d]] += ways[k - 1][s]; int q; std::cin >> q; for (int i = 0; i < q; i++) { long long lo, hi; int s; std::cin >> lo >> hi >> s; std::cout << countUpto(hi, s) - countUpto(lo - 1, s) << '\n'; }}
Cmain.c · 49 lines
#include <stdio.h>#define MAXLEN 16 /* 10^15는 16자리 */#define MAXS (7 * MAXLEN)static const int SEG[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; /* 숫자 0~9를 띄울 때 켜지는 막대 수 *//* ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수 */static long long ways[MAXLEN + 1][MAXS + 1];static long long tail(int k, int s) { return s >= 0 && s <= MAXS ? ways[k][s] : 0; }/* 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수(답이 10^15까지 가서 long long) */static long long count_upto(long long n, int S) { if (n < 0) return 0; long long total = S == SEG[0] ? 1 : 0; /* 0은 숫자 0 하나로 띄운다 */ if (n == 0) return total; char digits[24]; int len = snprintf(digits, sizeof digits, "%lld", n); /* n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 */ for (int k = 1; k < len; k++) for (int d = 1; d <= 9; d++) total += tail(k - 1, S - SEG[d]); /* n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 */ int rest = S; for (int i = 0; i < len; i++) { int c = digits[i] - '0'; for (int d = i == 0 ? 1 : 0; d < c; d++) total += tail(len - 1 - i, rest - SEG[d]); rest -= SEG[c]; } if (rest == 0) total++; /* n 자신 */ return total;}int main(void) { ways[0][0] = 1; for (int k = 1; k <= MAXLEN; k++) for (int s = 0; s <= MAXS; s++) if (ways[k - 1][s]) for (int d = 0; d < 10; d++) ways[k][s + SEG[d]] += ways[k - 1][s]; int q; if (scanf("%d", &q) != 1) return 0; for (int i = 0; i < q; i++) { long long lo, hi; int s; scanf("%lld %lld %d", &lo, &hi, &s); printf("%lld\n", count_upto(hi, s) - count_upto(lo - 1, s)); } return 0;}
Craykonmain.cray · 90 lines
SEG = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]; // 숫자 0~9를 띄울 때 켜지는 막대 수MAXLEN = 16; // 10^15는 16자리MAXS = 7 * MAXLEN;// ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수ways = [];for (k = 0; k <= MAXLEN; k++){ ways.Add(NewList(MAXS + 1, 0));}ways[0][0] = 1;for (k = 1; k <= MAXLEN; k++){ for (s = 0; s <= MAXS; s++) { if (ways[k - 1][s] != 0) { for (d = 0; d < 10; d++) { ways[k][s + SEG[d]] += ways[k - 1][s]; } } }}// 뒤에 숫자 k개가 남았고 막대를 s개 더 켜야 할 때의 경우의 수뒤(k, s){ if (s < 0 || s > MAXS) { return 0; } return ways[k][s];}// 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수세기(n, S){ if (n < 0) { return 0; } total = 0; if (S == SEG[0]) { total = 1; } if (n == 0) { return total; } digits = "" + n; len = digits.Length; // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (k = 1; k < len; k++) { for (d = 1; d <= 9; d++) { total += 뒤(k - 1, S - SEG[d]); } } // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 rest = S; for (i = 0; i < len; i++) { c = digits[i].ToNumber(); 시작 = 0; if (i == 0) { 시작 = 1; } for (d = 시작; d < c; d++) { total += 뒤(len - 1 - i, rest - SEG[d]); } rest -= SEG[c]; } if (rest == 0) { total += 1; } return total;}q = Console.ReadLine().Trim().ToNumber();for (i = 0; i < q; i++){ p = Console.ReadNumbers(); Console.WriteLine(세기(p[1], p[2]) - 세기(p[0] - 1, p[2]));}