Largest Seven-Segment Number
National Olympiad — Municipal round
Submission name: maxnum.cpp
Problem summary
Using N light segments of a conventional seven-segment display, construct the largest positive decimal integer.
Input
N.
Output
The largest number, or −1 when no digit can be formed.
Constraints
0 ≤ N ≤ 10⁷. Standard segment counts for digits 0…9 are 6,2,5,5,4,5,6,3,7,6.
Worked example
An independently prepared example for this explanation.
Input
7
Output
711
Solution analysis
- Maximize digit count first: digit 1 uses only two segments.
- For odd N≥3, put a 7 first and use 1 for every remaining pair. For even N use only 1.
Why it works
No digit costs fewer than two segments. At maximal length an even budget leaves no spare segment, while an odd budget leaves exactly one, best spent turning the leading 1 into 7.
Complexity: O(N) output time, O(1) auxiliary space.
Watch out. The answer may contain five million digits; stream it instead of parsing it numerically.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: No digit costs fewer than two segments. At maximal length an even budget leaves no spare
// segment, while an odd budget leaves exactly one, best spent turning the leading 1 into 7.
#include<iostream>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
if(n<2){
cout<<-1<<'\n';
return 0;
}
if(n%2){
cout<<7;
n-=3;
}
while(n){
cout<<1;
n-=2;
}
cout<<'\n';
}