Ottieni set e codice: PREPARAZIONE DEL TEST

(14 dicembre 2020)

CODICE PROBLEMA: MATH88

In questo articolo, vedremo come risolvere il problema PREPARAZIONE DEL TEST del concorso GET SET AND CODE.

Collegamento al problema:

Pagina del concorso | CodeChef

CodeChef – Una piattaforma per aspiranti programmatori CodeChef è stata creata come piattaforma per aiutare i programmatori a diventare grandi in …

www.codechef.com

Difficoltà- Difficile

Prerequisiti – Backtracking, Verbal Arithmetic, DFS

Descrizione del problema:

Due amici David e Rojer si stavano preparando per il loro test settimanale in classe. Si stanno preparando per il test di matematica, ma a causa dellaggiunta continua di grandi numeri interi e della risoluzione di equazioni si sono esauriti. Hanno deciso di prendersi una pausa e fare un gioco. Fanno un gioco che li aiuterà in entrambi (per divertirsi e aiuterà anche a prepararsi per il test di matematica). Ci sono N parole e devono trovare RISULTATO con laiuto di queste parole (proprio come hanno N numeri interi e devono trovare un intero RISULTATO = somma di N numeri interi). Dal momento che stanno giocando a questo gioco per la prima volta! Non sono troppo bravi in ​​questo. Aiutali a trovare il tempo il loro RISULTATO è corretto o meno.

NOTA: – Il numero totale di caratteri univoci in N parole non è maggiore di 10. Tutte le parole di input e RISULTATO sono solo in MAIUSCOLO !

Input:

  • La prima riga è composta da un intero N (numero totale di parole).
  • La riga successiva N contiene parole con cui devono trovare RISULTATO.
  • Lultima riga è costituita dal RISULTATO che hanno trovato.

Risultato:

Se RISULTATO è corretto stampare ” true “else print” false “.

Input di esempio:

3THIS
IS
TOO
FUNNY

Output di esempio:

true

Vincoli

  • 2≤N≤102≤N≤10
  • 1≤Lunghezza della parola≤101≤Lunghezza della parola≤10
  • 1≤LengthofTheResult≤11

Rapida comprensione del problema:

Ci saranno N-parole e una parola di risultato. Dobbiamo assegnare ogni carattere a un numero (da 1 a 9) e sostituire i caratteri delle N parole e le parole dei risultati con numeri corrispondenti. Se la somma dei numeri di N parole è uguale al numero della parola risultante , scrivi True.

SPIEGAZIONE:

Supponiamo di avere unequazione; le espressioni sono rappresentate da parole sul lato sinistro e il risultato sul lato destro. Dobbiamo verificare se lequazione è risolvibile secondo le seguenti regole o meno:
• Ogni carattere è decodificato come una cifra (da 0 a 9).
• Ogni coppia di caratteri diversi deve mappare a cifre diverse.
• Ogni parola [i] e il risultato vengono decodificati come un numero in cui non sono presenti zeri iniziali.
• La somma dei numeri sul lato sinistro sarà uguale al numero sul lato destro.
• Verificheremo se lequazione è risolvibile o meno.
Quindi, se linput è come le parole = [“SEND”, “MORE”], result = “MONEY”,
Loutput sarà True, come quando mappiamo il lettere come segue:

Mappa S -> 9, E -> 5, N -> 6, D -> 7, M -> 1, O -> 0, “R” -> 8, “Y” -> “2”,
Allora “SEND” + “MORE” = “MONEY” equivale a 9567 + 1085 = 10652.
Per ulteriori dettagli consulta questo LINK

Soluzione:

Complessità temporale – O (n!).

Codice 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");
}

}
}