InMy.Live

Étant donné deux entiers à N chiffres X et Oui, la tâche consiste à minimiser produit de X et Oui en effectuant l’opération suivante un nombre quelconque de fois où l’on peut choisir un entier i tel que 1≤ je ≤ N et échange moi^e chiffres les plus bas de X et Y.

Exemples:

Saisir : N = 2, X = 13, Y = 22
Sortir: 276
Explication: En effectuant l’opération une fois, avec i = 1, nous obtenons X = 12 et Y = 23 (en échangeant les chiffres les plus à droite de X et Y). Maintenant X*Y serait 276. Il n’est pas possible de rendre X*Y inférieur à 276, d’où la réponse est 276.

Saisir : N = 8, X = 20220122, Y = 21002300
Sortir: 54558365

Approche: L’idée pour résoudre le problème ci-dessus est:

Laisser un_je et b_je est-ce que je^e chiffres les plus bas de X et Y.

X*Y = ∑∑a_jeb_jdix^je+j(les sommations vont de i = 0 à N – 1 et j = 0 à N – 1)

= ∑ ∑a_jeb_jedix²ⁱ + ∑ ∑(une_jeb_j+ un_jb_je)dix^je+j

Notez que peu importe ce que ∑ ∑a_jeb_jedix²ⁱ reste constant. Donc, nous devons minimiser ∑ ∑(a_jeb_j + un_jb_je)dix^je+j

Si un_je – un_j et B_je – b_j avoir le même signe qu’un_jeb_j + un_jb_je est plus petit, sinon un_jeb_je + un_jb_j est plus petit. Ainsi, X*Y peut être minimisé en prenant le plus petit d’un_je et B_je comme un_je et plus grand que b_je.

Les étapes suivantes peuvent être utilisées pour résoudre le problème :

• Par souci de simplicité, stockez X et Y dans des chaînes (disons x et y).
• Initialisez deux variables (disons newX et newY) qui stockent les valeurs mises à jour (après avoir effectué les permutations requises) de X et Y.
• Itérer sur tous les chiffres de x et y.
• Dans l’itération courante, si le chiffre courant de x est supérieur à celui de y, appliquez l’opération d’échange.
• Pendant l’itération, continuez à mettre à jour les valeurs de newX et newY.
• À la fin de l’itération, calculez le produit de newX et newY modulo 998244353 et renvoyez-le comme réponse.

Voici le code basé sur l’approche ci-dessus :

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998244353;

// Function to Minimize product of two
// integers by swapping any number
// of their digits
int minProduct(int N, int X, int Y)
{

    // Storing both integers in strings
    string x = to_string(X);
    string y = to_string(Y);

    // Initializing two variables to store
    // the updated values of X and Y such
    // that the product is minimized
    int newX = 0, newY = 0;

    // Iterating through all the
    // digits of x and y
    for (int i = 0; i < N; ++i) {

        // If current digit of x is greater
        // than that of y, we apply
        // the operation
        if (x[i] > y[i])
            swap(x[i], y[i]);

        // Update the values of
        // newX and newY
        newX = (newX * 10 + (x[i] - '0')) % MOD;
        newY = (newY * 10 + (y[i] - '0')) % MOD;
    }

    // Compute the product of newX
    // and newY modulo MOD
    int ans = newX * newY % MOD;

    // Return the product
    return ans;
}

// Driver code
int32_t main()
{
    int N = 2, X = 13, Y = 22;

    // Function call
    int answer = minProduct(N, X, Y);
    cout << answer;
    return 0;
}

Complexité temporelle : SUR)
Espace Auxiliaire : O(1)