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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
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 = [];繰り返す (k = 0; k <= MAXLEN; k++){ ways.追加(新リスト(MAXS + 1, 0));}ways[0][0] = 1;繰り返す (k = 1; k <= MAXLEN; k++){ 繰り返す (s = 0; s <= MAXS; s++) { もし (ways[k - 1][s] != 0) { 繰り返す (d = 0; d < 10; d++) { ways[k][s + SEG[d]] += ways[k - 1][s]; } } }}// 뒤에 숫자 k개가 남았고 막대를 s개 더 켜야 할 때의 경우의 수뒤(k, s){ もし (s < 0 || s > MAXS) { 返す 0; } 返す ways[k][s];}// 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수세기(n, S){ もし (n < 0) { 返す 0; } total = 0; もし (S == SEG[0]) { total = 1; } もし (n == 0) { 返す total; } digits = "" + n; len = digits.長さ; // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 繰り返す (k = 1; k < len; k++) { 繰り返す (d = 1; d <= 9; d++) { total += 뒤(k - 1, S - SEG[d]); } } // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 rest = S; 繰り返す (i = 0; i < len; i++) { c = digits[i].数に(); 시작 = 0; もし (i == 0) { 시작 = 1; } 繰り返す (d = 시작; d < c; d++) { total += 뒤(len - 1 - i, rest - SEG[d]); } rest -= SEG[c]; } もし (rest == 0) { total += 1; } 返す total;}q = コンソール.行読み().空白除去().数に();繰り返す (i = 0; i < q; i++){ p = コンソール.数読み(); コンソール.書く(세기(p[1], p[2]) - 세기(p[0] - 1, p[2]));}