Algorithm

B. Long Number
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/1157/problem/B
input
standard input
output
standard output

You are given a long decimal number a� consisting of n� digits from 11 to 99. You also have a function f� that maps every digit from 11 to 99 to some (possibly the same) digit from 11 to 99.

You can perform the following operation no more than once: choose a non-empty contiguous subsegment of digits in a�, and replace each digit x� from this segment with f(x)�(�). For example, if a=1337�=1337, f(1)=1�(1)=1, f(3)=5�(3)=5, f(7)=3�(7)=3, and you choose the segment consisting of three rightmost digits, you get 15531553 as the result.

What is the maximum possible number you can obtain applying this operation no more than once?

Input

The first line contains one integer n� (1≤n≤2⋅1051≤�≤2⋅105) — the number of digits in a�.

The second line contains a string of n� characters, denoting the number a�. Each character is a decimal digit from 11 to 99.

The third line contains exactly 99 integers f(1)�(1), f(2)�(2), ..., f(9)�(9) (1≤f(i)≤91≤�(�)≤9).

Output

Print the maximum number you can get after applying the operation described in the statement no more than once.

Examples
input
Copy
4
1337
1 2 5 4 6 6 3 1 9
output
Copy
1557
input
Copy
5
11111
9 8 7 6 5 4 3 2 1
output
Copy
99999
input
Copy
2
33
1 1 1 1 1 1 1 1 1
output
Copy
33

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 10;
int n, f[10];
char s[N];

int main() {
  scanf("%d\n%s", &n, s);
  for(int i = 1; i <= 9; ++i)
    scanf("%d", f + i);

  bool conv = false;
  for(int i = 0; s[i] != '\0'; ++i) {
    if((conv && f[s[i] - '0'] >= s[i] - '0') || (!conv && f[s[i] - '0'] > s[i] - '0'))
      conv = true;
    if(conv && f[s[i] - '0'] < s[i] - '0')
      break;
    if(conv)
      s[i] = f[s[i] - '0'] + '0';
  }

  puts(s);

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
4
1337
1 2 5 4 6 6 3 1 9

Output

x
–
+
cmd
1557
Advertisements

Demonstration

Codeforces Solution Long Number, B. Long Number-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+