PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Daanish Mahajan
Tester: Felipe Mota
Editorialist: Aman Dwivedi
DIFFICULTY
Cakewalk
PREREQUISITES
Observation
PROBLEM:
Chef’s friend gave him a wrong number W containing N+1 digits and said that the actual number A is the largest possible number that can be obtained from deleting exactly one digit of W. The chef was able to find A but forgot W.
Given A, find the smallest possible number W of length N+1 without leading 0's that is consistent with the story above. We can show that there is always at least one such W consistent with the story.
EXPLANATION:
We have a number A consisting of N digits. Our goal is to find the smallest number W of length N+1 by inserting a single digit on A.
Depending on the first digit of A there can be two cases, which are:
Case 1: The first digit of A is greater than 1
-
Best Position to Insert a Digit
Let us see which is the best position to insert a new digit on the number A. Since the newly formed number will always consist of N+1 digits, irrespective of where we insert a digit. Hence we can say the smallest number is also lexicographically smallest too.
Since the first digit of a number is greater than 1, then if we don’t insert a new digit at the beginning, we will always end up with a number W with the first digit same as that of A.
As the first digit of the number A is greater than 1, that means we always have a choice to obtain a number W such that whose first digit is smaller than that of A. That is only possible when we insert a new digit at the beginning.
Hence the best position to insert a digit, in this case, is at beginning of the number A.
-
Best Digit to Insert
Since we are inserting a digit at the beginning then we can’t insert 0 as we don’t want leading zeroes. As the next smaller digit is 1, we would insert 1 at the beginning in this case.
Case 2: The first digit of A is 1
-
Best Position to Insert a Digit
As the first digit is already 1, then it is not optimal to insert the new digit at the beginning. Remember the number is lexicographically smaller than the other when the first digit where it differs is less in that number.
Hence we will find the digit which is greater than 0 in the given number A (excluding the first digit of number A). If we find such a digit then we will insert a digit 0 before that digit making it lexicographically smallest.
If there exists no such digit then we would be obtaining a number in the form of 10^{N+1}, which is a smaller number possible in N+1 digits.
-
Best Digit to Insert
Since we are not inserting a digit at the beginning hence we can insert 0, which is the minimum possible digit.
TIME COMPLEXITY:
O(1) per test case
SOLUTIONS:
Setter
Tester
Editorialist
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
string s;
cin>>s;
if(s[0]=='1')
s[0]='0';
cout<<1<<s<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}