Configuración y código: PREPARACIÓN DE LA PRUEBA

(14 de diciembre de 2020)

CÓDIGO DEL PROBLEMA: MATH88

En este artículo, veremos cómo resolver el problema. PREPARANDO PRUEBA del concurso GET SET AND CODE.

Enlace del problema:

Página del concurso | CodeChef

CodeChef: una plataforma para aspirantes a programadores CodeChef se creó como una plataforma para ayudar a los programadores a triunfar en…

www.codechef.com

Dificultad- Difícil

Requisitos previos – Retroceso, aritmética verbal, DFS

Descripción del problema:

Dos amigos, David y Rojer, se estaban preparando para su prueba de clase semanal. Se están preparando para el examen de matemáticas, pero debido a que continuamente suman números enteros grandes y resuelven ecuaciones, se agotaron. Decidieron tomar un descanso y jugar un juego. Juegan un juego que les ayudará en ambos (para divertirse y también les ayudará a prepararse para el examen de matemáticas). Hay N palabras y tienen que encontrar RESULTADO con la ayuda de estas palabras (al igual que tienen N enteros y tienen que encontrar entero RESULT = suma de N enteros). ¡Ya que están jugando a este juego por primera vez! No son demasiado buenos en esto. Ayúdelos a encontrar si su RESULTADO es correcto o no.

NOTA: – El número total de caracteres únicos en N palabras no es mayor que 10. Todas las palabras de entrada y el RESULTADO están solo en MAYÚSCULAS !

Entrada:

  • La primera línea consta de un número entero N (número total de palabras).
  • La siguiente línea N contiene palabras con el que tienen que encontrar el RESULTADO.
  • La última línea consta del RESULTADO que encontraron.

Salida:

Si el RESULTADO es correcto, imprima » true ”si no imprime“ false ”.

Entrada de muestra:

3THIS
IS
TOO
FUNNY

Salida de muestra:

true

Restricciones

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

Comprensión rápida del problema:

Habrá N palabras y una palabra de resultado. Tenemos que asignar cada carácter a un número (1 a 9) y reemplazar los caracteres de N palabras y palabras de resultado con números correspondientes. Si la suma del número de N palabras es igual al número de la palabra resultante , imprima True.

EXPLICACIÓN:

Supongamos que tenemos una ecuación; las expresiones están representadas por palabras en el lado izquierdo y el resultado en el lado derecho. Tenemos que verificar si la ecuación se puede resolver bajo las siguientes reglas o no –
• Cada carácter se decodifica como un dígito (0 a 9).
• Cada par de caracteres diferentes debe asignarse a dígitos diferentes.
• Cada palabra [i] y el resultado se decodifican como un número donde no hay ceros a la izquierda.
• La suma de los números del lado izquierdo será igual al número del lado derecho.
• Comprobaremos si la ecuación se puede resolver o no.
Entonces, si la entrada es como palabras = [«ENVIAR», «MÁS»], resultado = «DINERO»,
Entonces la salida será Verdadera, como cuando mapeamos el letras de la siguiente manera:

Mapa S -> 9, E -> 5, N -> 6, D -> 7, M -> 1, O -> 0, R -> 8, Y -> 2,
Luego, «ENVIAR» + «MÁS» = «DINERO» es lo mismo que 9567 + 1085 = 10652.
Para obtener más detalles consulte este LINK

Solución:

Complejidad de tiempo – O (n!).

Código 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");
}

}
}