Long Multiplication (Codeforces 1954C)
Tags: Greedy, number theory

You are given two integers $$$x$$$ and $$$y$$$ of the same length, consisting of digits from $$$1$$$ to $$$9$$$.You can perform the following operation any number of times (possibly zero): swap the $$$i$$$-th digit in $$$x$$$ and the $$$i$$$-th digit in $$$y$$$.For example, if $$$x=73$$$ and $$$y=31$$$, you can swap the $$$2$$$-nd digits and get $$$x=71$$$ and $$$y=33$$$.Your task is to maximize the product of $$$x$$$ and $$$y$$$ using the aforementioned operation any number of times. If there are multiple answers, print any of them.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.The first line of each test case contains a single integer $$$x$$$ ($$$1 \le x < 10^{100}$$$).The second line of each test case contains a single integer $$$y$$$ ($$$1 \le y < 10^{100}$$$).Additional constraint on input: the integers $$$x$$$ and $$$y$$$ consist only of digits from $$$1$$$ to $$$9$$$.

Output: For each test case, print two lines — the first line should contain the number $$$x$$$ after performing the operations; similarly, the second line should contain the number $$$y$$$ after performing the operations. If there are multiple answers, print any of them.


Sample Inputs:
3
73
31
2
5
3516
3982

Sample Outputs:
71
33
5
2
3912
3586

Solution (Python):
def answer():
    a = input()
    b = input()
    if a < b:
        (a, b) = (b, a)
    yes = False
    a = list(a)
    b = list(b)
    for i in range(len(a)):
        if a[i] > b[i] and yes:
            (a[i], b[i]) = (b[i], a[i])
        if a[i] != b[i]:
            yes = True
    print(''.join(a))
    print(''.join(b))
t = int(input())
for _ in range(t):
    answer()

Solution (Python):
import heapq, math
from itertools import *
from bisect import *
from collections import *
from sys import stdin, stdout

def pr(out):
    return stdout.write(f'{out}\n')

def input():
    return stdin.readline().rstrip()

def int_inp():
    return int(input())

def inp_int_l():
    return list(map(int, stdin.readline().split()))

def inp_l():
    return stdin.readline().split()

def solve():
    (x, y) = (list(input()), list(input()))
    flag = False
    for i in range(len(x)):
        if not flag and x[i] != y[i]:
            if y[i] > x[i]:
                (y[i], x[i]) = (x[i], y[i])
                flag = True
        elif flag and x[i] != y[i]:
            if x[i] > y[i]:
                (y[i], x[i]) = (x[i], y[i])
                flag = False
        if x[i] != y[i]:
            flag = True
    print(''.join(x))
    print(''.join(y))
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solve()

Solution (Python):
def maximize_product(x, y):
    x = list(x)
    y = list(y)
    n = len(x)
    diff = False
    for i in range(n):
        if x[i] == y[i]:
            continue
        if x[i] > y[i]:
            if diff:
                (x[i], y[i]) = (y[i], x[i])
        elif not diff:
            (x[i], y[i]) = (y[i], x[i])
        diff = True
    return (''.join(x), ''.join(y))
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        x = str(input())
        y = str(input())
        (max_x, max_y) = maximize_product(x, y)
        print(max_x)
        print(max_y)