fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fastIO() ios::sync_with_stdio(false); cin.tie(nullptr);
  5.  
  6. void solve() {
  7.     int n;
  8.     cin >> n;
  9.  
  10.     string a, b;
  11.     cin >> a >> b;
  12.  
  13.     int pos = -1;
  14.  
  15.     // Find first position where going down is strictly better
  16.     for (int i = 0; i < n; i++) {
  17.         if (b[i] < a[i]) {
  18.             pos = i;
  19.             break;
  20.         }
  21.         if (b[i] > a[i]) {
  22.             break;
  23.         }
  24.     }
  25.  
  26.     if (pos == -1) pos = n - 1;
  27.  
  28.     // Construct lexicographically smallest string
  29.     string result = a.substr(0, pos + 1) + b.substr(pos);
  30.  
  31.     // Count number of valid paths
  32.     long long countPaths = 1;
  33.     for (int i = pos - 1; i >= 0; i--) {
  34.         if (a[i] == b[i])
  35.             countPaths++;
  36.         else
  37.             break;
  38.     }
  39.  
  40.     cout << result << "\n";
  41.     cout << countPaths << "\n";
  42. }
  43.  
  44. int main() {
  45.     fastIO();
  46.     int t;
  47.     cin >> t;
  48.     while (t--) solve();
  49.     return 0;
  50. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
3
2
00
00
4
1101
1100
8
00100111
11101101
stdout
copy 
000
2
11010
4
001001111
1
https://ideone.com/fMrSio
language:
C++14 (gcc 8.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!