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 C2011 · MediumNumeral Systems

Numbers containing only 0 and 6

National Olympiad — Municipal round

Submission name: round.cpp

Solve in Editor →

Problem summary

List nonnegative integers whose decimal digits belong to {0,6} in increasing order, beginning with 0. Find the K-th number, using 1-based positions.

Input

K.

Output

The requested decimal number.

Constraints

1 ≤ K ≤ 1000.

Worked example

An independently prepared example for this explanation.

Input

8

Output

666

Solution analysis

  1. Write K−1 in binary.
  2. Replace each binary 1 with 6; retain each 0. Handle K=1 as 0.

Why it works

Binary order and the order of decimal strings over {0,6} agree: shorter positive strings come first, then lexicographic order within each length.

Complexity: O(log K) time and space.

Watch out. The initial zero occupies position 1; do not convert K itself.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: Binary order and the order of decimal strings over {0,6} agree: shorter positive strings
// come first, then lexicographic order within each length.
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    int k;
    cin>>k;
    --k;
    string s;
    do{
        s+=k%2?'6':'0';
        k/=2;
    }
    while(k);
    reverse(s.begin(),s.end());
    cout<<s<<'\n';
}

Source: Arena Olimpiici ↗