CNUMBER - Editorial

PROBLEM LINK:

Practice
Contest

Author: Srinjoy Ray
Tester: Ankur Kayal
Editorialist: Srinjoy Ray

DIFFICULTY:

MEDIUM

PREREQUISITES:

Binary Search

PROBLEM:

A number is called Claus number is it has an even number of digits and the alternate digits of the number are same. We are given a number N, we have to find the closest Claus number to N.

EXPLANATION:

The main observation here is that the total number of Claus numbers less then 10^{18} is just 810.

The first digit of the number has 9 options [1-9] and the second digit has 10 options [0-9]. So there are 90 different starting combinations. Using each starting combination, we can have 9 Claus numbers ( no of digits = 2,4,6,8,10,12,14,16,18). So the total number of Claus numbers less than 10^{18} is 90×9 = 810.

We can store all the Claus numbers in a set and use lower bound and upper bound functions to find the closest Claus number.

Time Complexity : O(log(logN)) per test case.

ALTERNATE EXPLANATION:

When no of digits of N is odd : If N is less than 10,then answer will be 10. Otherwise, we have just 2 potential answers. They are the Claus number starting with 99 and having 1 digit less than N and the Claus number starting with 10 and having 1 digit more than N. We can just compare the differences of each of these Claus numbers with N and print the Claus number which has the minimum absolute difference with N.

When no of digits of N is even : The answer in this case will always have the same number of digits as N. If N starts with 10, then the potential answers are the Claus numbers starting with 10 and 11. If N starts with 99, then the answer must be among the Claus numbers starting with 99 or 98. If N starts with any other number (let it be S), then the potential answers start with S-1, S and S+1 . We can compute the difference of each of these potential answers and find our final answer.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

set<ll> special_nos;
const ll inf = INT64_MAX;

void solve(){
    int i,j;
    
    ll num,ans,temp,mn=inf,value;
    
    cin>>num;
   
    if(special_nos.lower_bound(num)!= special_nos.end()){
        value = (*special_nos.lower_bound(num));
        temp = value-num;
        
        if(temp<mn){
            mn=temp;
            ans=value;
        }
    }
    if(*special_nos.begin()<num){
        value = *(--special_nos.upper_bound(num));
        temp = num - value;
       
        if(temp<mn){
            mn=temp;
            ans=value;
        }
    }

    cout<<ans<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t,i,j,k;
    
    string base,temp;
    for(int i=10;i<=99;i++){
        temp="";
        base=to_string(i);            
        for(j=1;j<=9;j++){
            temp+=base;
            special_nos.insert(stoll(temp));
        }
        
    }

    cin>>t;
    while(t--){
        solve();
    }
    
}


Setter's Alternate Solution
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e6+10;

const ll inf = 1e15;
ll no_of_digits(ll num){
    ll count=0;
    while(num){
        count++;
        num/=10;
    }
    return count;
}
ll make(ll start,ll digits){
    ll num = start;
    for(int i=2;i<digits;i+=2){
        num = (num*100) + start;
    }
    return num;
}
ll get_start(ll num){
    while(num>=100){
        num/=10;
    }
    return num;
}
void solve(){
    int i,j;
    
    ll num,digits;
    cin>>num;
    digits = no_of_digits(num);

    if(digits%2==1){
        ll low,high;
        if(digits==1){
            cout<<"10\n";
            return;
        }
        
        low = make(99,digits-1);
        high = make(10,digits+1);

        if(abs(num-low)<= abs(num-high)){
            cout<<low<<'\n';
        }
        else{
            cout<<high<<'\n';
        }
    }
    else{
        ll low,same,high,start;

        start = get_start(num);

        if(start == 10){
            same = make(start,digits);
            high = make(start+1,digits);

            if(abs(num-same)<=abs(num-high)){
                cout<<same<<'\n';
            }
            else{
                cout<<high<<'\n';
            }
        }
        else if(start == 99){
            low = make(start-1,digits);
            same = make(start,digits);

            if(abs(num-low)<=abs(num-same)){
                cout<<low<<'\n';
            }
            else{
                cout<<same<<'\n';
            }
        }
        else{
            low = make(start-1,digits);
            same = make(start,digits);
            high = make(start+1,digits);

            if(abs(num-low) <= abs(num-same) && abs(num-low) <= abs(num-high)){
                cout<<low<<'\n';
            }
            else if(abs(num-same) <= abs(num-low) && abs(num-same) <= abs(num-high)){
                cout<<same<<'\n';
            }
            else{
                cout<<high<<'\n';
            }
        }
    }

}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}


Tester's Solution
#include <algorithm>
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;


//----------------------------------- DEBUG -----------------------------------
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }

//----------------------------------- END DEBUG --------------------------------

#define nl '\n'

vector<int64_t> claus;

void compute() {
    for(int digits = 2; digits <= 18; digits += 2) {
        for(int first = 1; first <= 9; first++) {
            for(int second = 0; second <= 9; second++) {
                string number = "";
                for(int times = 0; times < digits; times++) {
                    if(times & 1) {
                        number += to_string(second);
                    } else {
                        number += to_string(first);
                    }
                }
                claus.push_back(stoll(number));
            }
        }
    }

    sort(claus.begin(), claus.end());
}

void run_cases() {
    int64_t N;
    cin >> N;

    int64_t min_difference = LLONG_MAX;

    int64_t ans = -1;

    int l = 0, r = claus.size();

    while(r > l + 1) {
        int m = (l + r) / 2;

        if(claus[m] < N) {
            l = m;
        } else {
            r = m;
        }
    }

    for(int i = l; i < min(l + 2, int(claus.size())); i++) {
        if(abs(claus[i] - N) < min_difference) {
            ans = claus[i];
            min_difference = abs(claus[i] - N);
        }
    } 

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr);

    compute();

    // debug() << imie(claus);

    int tests = 1;
    cin >> tests;

    for(int test = 1;test <= tests;test++) {
        run_cases();
    }
}
1 Like