Obter conjunto e código: PREPARAR TESTE

(14 de dezembro de 2020)

CÓDIGO DO PROBLEMA: MATH88

Neste artigo, veremos como resolver o problema TESTE DE PREPARAÇÃO do concurso GET SET AND CODE.

Link do problema:

Página do concurso | CodeChef

CodeChef – Uma plataforma para aspirantes a programadores CodeChef foi criado como uma plataforma para ajudar os programadores a se tornarem grandes em…

www.codechef.com

Dificuldade- Difícil

Pré-requisitos – Retrocesso, aritmética verbal, DFS

Descrição do problema:

Dois amigos David e Rojer estavam se preparando para seu teste semanal. Eles estão se preparando para o teste de matemática, mas por causa da adição contínua de números inteiros grandes e da resolução de equações, eles ficam exaustos. Eles decidiram fazer uma pausa e jogar um jogo. Eles jogam um jogo que os ajudará em ambos (para se divertir e também ajudará a se preparar para a prova de matemática). Existem N palavras e eles têm que encontrar RESULT com a ajuda dessas palavras (assim como eles têm N inteiros e eles têm que encontrar um inteiro RESULT = soma de N inteiros). Já que eles estão jogando este jogo pela primeira vez! Eles não são muito bons nisso. Ajude-os a descobrir se seu RESULTADO está correto ou não.

NOTA: – O número total de caracteres únicos em N palavras não é maior que 10. Todas as palavras de entrada e RESULTADO estão em MAIÚSCULAS apenas !

Entrada:

  • A primeira linha consiste em um inteiro N (número total de palavras).
  • A próxima linha N contém palavras com o qual eles devem encontrar o RESULTADO.
  • A última linha consiste no RESULTADO que eles encontraram.

Resultado:

Se o RESULTADO estiver correto, imprima “ true ”senão imprime“ false ”.

Amostra de entrada:

3THIS
IS
TOO
FUNNY

Amostra de saída:

true

Restrições

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

Compreensão rápida do problema:

Haverá N-palavras e uma palavra resultante. Temos que atribuir cada caractere a um número (1 a 9) e substituir os caracteres de N palavras e palavras de resultado por números correspondentes. Se a soma dos números de N palavras for igual ao número da palavra resultante , imprima True.

EXPLICAÇÃO:

Suponha que temos uma equação; expressões são representadas por palavras no lado esquerdo e o resultado no lado direito. Temos que verificar se a equação pode ser resolvida de acordo com as seguintes regras ou não –
• Cada caractere é decodificado como um dígito (0 a 9).
• Cada par de caracteres diferentes deve ser mapeado para dígitos diferentes.
• Cada palavra [i] e resultado são decodificados como um número onde não há zeros à esquerda.
• A soma dos números no lado esquerdo será igual ao número no lado direito.
• Verificaremos se a equação pode ser resolvida ou não.
Então, se a entrada for como palavras = [“ENVIAR”, “MAIS”], resultado = “DINHEIRO”,
Então a saída será Verdadeira, como quando mapeamos o letras da seguinte forma:

Mapear S -> 9, E -> 5, N -> 6, D -> 7, M -> 1, O -> 0, R -> 8, Y -> 2,
Então “ENVIAR” + “MAIS” = “DINHEIRO” é o mesmo que 9567 + 1085 = 10652.
Para mais detalhes consulte esta LINK

Solução:

Complexidade de tempo – 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");
}

}
}