PROBLEM LINK:
Practice
Contest
Author: Soumy Jain
Tester: Divyank Goyal
Editorialist: Anugya Jain
DIFFICULTY:
EASY
PREREQUISITES:
Basic knowledge of any programming language.
PROBLEM:
You have given a number N and an array containing the value of each number fun(1) to fun(9). You can change all the digits of a non-empty contiguous subsegment according to the function. if Y is the digit of the number N then change it to fun(Y).
NOTE: We can only choose only one subsegment .
EXPLANATION:
According to the question, we have to choose a subarray and apply the given operation on each digit of the subarray. We have to make sure the result will the greatest among all the possible numbers created.
Example 1:
N =2345
Arr=[1,2,5,4,7,6,8,9,3]
Output:2547
If we change the digit from left to right then we will make sure that the result will the greatest of all.
We have to choose a first digit (Y) from the left which is smaller than fun(Y) i.e Y<fun(Y). From this digit change all the digit that is smaller than or equal to fun(Y) untill we get any digit Y which is greater than fun(Y) i.e(Y>fun(Y)).
Now the question is why we are taking equal value after the first digit .
Example 2:
N =1234 and Arr=[1,4,3,5,2,6,7,8,9]
Y=2 =>fun(2)=4
Y=3=>fun(3)=3 // if here we break the loop then we get N=1434 which is smaller than 1435
Y=4=>fun(4)=5
SOLUTIONS:
Editorialist's Solution
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
string s;
cin>>s;
unordered_map<char,char>m;
char temp='1';
for(int i=1;i<10;i++)
{
char p;
cin>>p;
m[temp]=p;
temp++;
}
int flag=0;
char r='#';
int n=s.length();
for(int i=0;i<n;)
{
if(m[s[i]]>s[i])
{
s[i]=m[s[i]];
i++;
for(int j=i;j<n;j++)
{
if(m[s[j]]>=s[j])
{
s[j]=m[s[j]];
}
else break;
}
break;
}
i++;
}
cout<<s;
return 0;
}