Get Set and Code: PREPARING TEST

(14 décembre 2020)

CODE DU PROBLÈME: MATH88

Dans cet article, nous allons voir comment résoudre le problème PREPARING TEST du concours GET SET AND CODE.

Lien du problème:

Page du concours | CodeChef

CodeChef – Une plate-forme pour les programmeurs en herbe CodeChef a été créé en tant que plate-forme pour aider les programmeurs à réussir en…

www.codechef.com

Difficulté – Difficile

Prérequis – Retour en arrière, arithmétique verbale, DFS

Description du problème:

Deux amis David et Rojer se préparaient pour leur test hebdomadaire. Ils se préparent pour le test de mathématiques, mais en raison de lajout continu de grands nombres entiers et de la résolution déquations, ils se sont épuisés. Ils ont décidé de faire une pause et de jouer à un jeu. Ils jouent à un jeu qui les aidera dans les deux (pour samuser et aidera également à se préparer au test de mathématiques). Il y a N mots et ils doivent trouver RESULT à laide de ces mots (tout comme ils ont N entiers et ils doivent trouver un entier RESULT = somme de N entiers). Depuis quils jouent à ce jeu pour la première fois! Ils ne sont pas trop bons dans ce domaine. Aidez-les à trouver la météo que leur RESULTAT est correct ou non.

REMARQUE: – Le nombre total de caractères uniques dans N mots nest pas supérieur à 10. Tous les mots dentrée et RESULTAT sont uniquement en MAJUSCULES !

Entrée:

  • La première ligne est constituée dun entier N (nombre total de mots).
  • La ligne N suivante contient des mots avec lequel ils doivent trouver RESULT.
  • La dernière ligne se compose du RESULTAT quils ont trouvé.

Résultat:

Si RESULT est correct, imprimer  » true « else print » false « .

Exemple dentrée:

3THIS
IS
TOO
FUNNY

Exemple de sortie:

true

Contraintes

  • 2≤N≤102≤N≤10
  • 1≤LengthofTheword≤101≤LengthofTheword≤10
  • 1≤LengthofTheResult≤11

Compréhension rapide du problème:

Il y aura N-mots et un mot de résultat. Nous devons attribuer à chaque caractère un nombre (1 à 9) et remplacer les caractères de N-mots et mots de résultat par numéros correspondants. Si la somme des nombres de N mots est égale au numéro de mot de résultat alors imprimez True.

EXPLICATION:

Supposons que nous ayons une équation; les expressions sont représentées par des mots sur le côté gauche et le résultat sur le côté droit. Nous devons vérifier si léquation peut être résolue selon les règles suivantes ou non –
• Chaque caractère est décodé comme un chiffre (0 à 9).
• Chaque paire de caractères différents doit correspondre à des chiffres différents.
• Chaque mot [i] et résultat sont décodés comme un nombre sans zéros non significatifs.
• La somme des nombres sur le côté gauche sera égale au nombre sur le côté droit.
• Nous vérifierons si léquation est résoluble ou non.
Donc, si lentrée est comme mots = [« ENVOYER », « PLUS »], résultat = « MONEY »,
Alors la sortie sera Vrai, comme lorsque nous mappons le lettres comme suit:

Carte S -> 9, E -> 5, N -> 6, D -> 7, M -> 1, O -> 0, R -> 8, Y -> 2,
Alors «SEND» + «MORE» = «MONEY» équivaut à 9567 + 1085 = 10652.
Pour plus de détails veuillez vous référer à cette LINK

Solution:

Complexité temporelle – O (n!).

Code Java:

import java.*;
import java.util.*;class Solution {
public boolean isSolvable(String[] words, String result) {
reverseWords(words);
result = new StringBuilder(result).reverse().toString();
return isSolvable(words, result, new HashMap(),
new HashSet(), 0, 0, 0);
}private void reverseWords(String[] words) {
for (int i = 0; i < words.length; i++) {
words[i] = new StringBuilder(words[i]).reverse().toString();
}
}private boolean isSolvable(String[] words, String result, Map map, Set used, int i, int j, int sum) {
if (i >= result.length()) {
return sum == 0;
}

if (j >= words.length) {
if (map.containsKey(result.charAt(i))) {
if (map.get(result.charAt(i)) != sum \% 10) {
return false;
}

if (i + 1 == result.length() && map.get(result.charAt(i)) == 0) {
return false;
}

return isSolvable(words, result, map, used, i + 1, 0, sum / 10);
}
else if (!used.contains(sum \% 10) && !(i + 1 == result.length() && sum \% 10 == 0)) {
map.put(result.charAt(i), sum \% 10);
used.add(sum \% 10);

if (isSolvable(words, result, map, used, i + 1, 0, sum / 10)) {
return true;
}
used.remove(sum \% 10);
map.remove(result.charAt(i));
}
return false;
}
if (i >= words[j].length()) {
return isSolvable(words, result, map, used, i, j + 1, sum);
}
if (map.containsKey(words[j].charAt(i))) {
if (i + 1 == words[j].length() && map.get(words[j].charAt(i)) == 0) {
return false;
}
return isSolvable(words, result, map, used, i, j + 1, sum + map.get(words[j].charAt(i)));
}
for (int g = 0; g < 10; g++) {
if (used.contains(g)) {
continue;
}
if (g == 0 && i + 1 == words[j].length()) {
continue;
}
map.put(words[j].charAt(i), g);
used.add(g);
if (isSolvable(words, result, map, used, i, j + 1, sum + g)) {
return true;
}
used.remove(g);
map.remove(words[j].charAt(i));
}

return false;
}
}
class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n;
n=sc.nextInt();
String vec[]=new String[n];
for(int i=0;i vec[i]=sc.next();
}
String result;
result=sc.next();
Solution sol=new Solution();
if(sol.isSolvable(vec,result)){
System.out.println("true");
}
else{
System.out.println("false");
}

}
}