PROBLEM LINK:
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();
}
}