cppAcademy
FROM LEARNING TO COMPETING

Real problems.
Your next challenge.

Explore the Group C Olympiad archive.
Choose a topic. Find a challenge. Build your solution.

213 tasks across the Municipal, Regional, and National rounds (2009–2026), plus 4 previously featured problems. 146 tasks have independently written English summaries, analyses, and C++17 solutions; the remaining entries link to Arena. Topic tags are from Arena or our reviewed explanations. Difficulty labels are learning estimates, not official ratings.
GROUP C2022 · MediumDigit Dp

Seven-Segment Number Labels

National Olympiad — Regional round

Submission name: elmcnt.cpp

Solve in Editor →

Problem summary

Label N consecutive computers with the decimal integers S,S+1,…,S+N−1. Digits use standard seven-segment displays: costs for 0 through 9 are 6,2,5,5,4,5,6,3,7,6. Count all segments required. Leading zeroes are not displayed; the number zero itself uses six segments.

Input

N S.

Output

Total segment count.

Constraints

0 ≤ N ≤ 10^17; 0 ≤ S ≤ 10^10. Archive metadata places this in the Regional round; the linked statement header says Municipal round, 5 February 2022.

Worked example

An independently prepared example for this explanation.

Input

2 0

Output

8

Solution analysis

  1. Define F(x) as the segment count for integers 0 through x; answer F(S+N−1)−F(S−1).
  2. Digit DP tracks whether the prefix is tight and whether a nonzero digit has started the number. Each state returns both the number of completions and their segment sum.
  3. A digit adds its cost times the number of suffix completions. At the end, a never-started number is zero and contributes six. Use 128-bit arithmetic for totals.

Why it works

Each number has exactly one padded digit representation in the DP. Leading padding contributes nothing; all displayed digits contribute once. Subtracting prefix totals leaves exactly the requested interval.

Complexity: O(log(S+N)) states with 10 transitions each; O(log(S+N)) space.

Watch out. The total can exceed signed 64-bit. N=0 must return zero without forming an invalid unsigned endpoint.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: Each number has exactly one padded digit representation in the DP. Leading padding
// contributes nothing; all displayed digits contribute once.
#include<iostream>
#include<string>
#include<utility>
#include<functional>
using namespace std;
using I=__int128_t;
int cost[10]={6,2,5,5,4,5,6,3,7,6};
I prefix(long long x){
    if(x<0){
        return 0;
    }
    string s=to_string(x);
    pair<I,I>memo[20][2];
    bool used[20][2]={};
    function<pair<I,I>(int,bool,bool)>go=[&](int p,bool tight,bool started)->pair<I,I>{
        if(p==(int)s.size()){
            return {1,started?0:6};
        }
        if(!tight&&used[p][started]){
            return memo[p][started];
        }
        I cnt=0,sum=0;
        int lim=tight?s[p]-'0':9;
        for(int d=0;d<=lim;d++){
            bool ns=started||d;
            auto[c,v]=go(p+1,tight&&d==lim,ns);
            cnt+=c;
            sum+=v+c*(ns?cost[d]:0);
        }
        pair<I,I>res={cnt,sum};
        if(!tight){
            used[p][started]=true;
            memo[p][started]=res;
        }
        return res;
    };
    return go(0,true,false).second;
}
void print(I x){
    if(x>=10){
        print(x/10);
    }
    cout<<char('0'+x%10);
}
int main(){
    long long n,s;
    cin>>n>>s;
    print(n?prefix(s+n-1)-prefix(s-1):0);
    cout<<'\n';
}

Source: Arena Olimpiici ↗