Obțineți setul și codul: PREPARAREA TESTULUI

(14 dec.2020)

CODUL PROBLEMEI: MATH88

În acest articol vom vedea cum să rezolvăm problema PREGĂTIREA TESTULUI al concursului GET SET AND CODE.

Legătură problemă:

Pagina concursului | CodeChef

CodeChef – O platformă pentru programatori aspiranți CodeChef a fost creat ca o platformă pentru a ajuta programatorii să o facă mare în …

www.codechef.com

Dificultate- Hard

Cerințe preliminare – Backtracking, Arithmetic verbal, DFS

Descrierea problemei:

Doi prieteni David și Rojer se pregăteau pentru testul săptămânal de clasă. Se pregătesc pentru testul de matematică, dar din cauza adăugării continue de numere întregi mari și a rezolvării ecuațiilor s-au epuizat. Au decis să facă pauză și să joace un joc. Ei joacă un joc care îi va ajuta în ambele (pentru a se distra și, de asemenea, va ajuta la pregătirea pentru testul de matematică). Există N cuvinte și trebuie să găsească REZULTAT cu ajutorul acestor cuvinte (la fel cum au N numere întregi și trebuie să găsească REZULTAT întreg = suma a N numere întregi). Din moment ce joacă acest joc pentru prima dată! Nu sunt prea buni în asta. Ajutați-i să găsească vremea REZULTATUL lor este corect sau nu.

NOTĂ: – Numărul total de caractere unice în N cuvinte nu este mai mare de 10. Toate cuvintele de intrare și REZULTAT sunt numai în MAJUSCU !

Introducere:

  • Prima linie constă dintr-un număr întreg N (numărul total de cuvinte).
  • N-ul rândului următor conține cuvinte cu care trebuie să găsească REZULTAT.
  • Ultima linie constă în REZULTATUL pe care l-au găsit.

Ieșire:

Dacă REZULTATUL este corect, tipăriți „ adevărat ”else print“ false ”.

Introducere eșantion:

3THIS
IS
TOO
FUNNY

Eșantion de ieșire:

true

Constrângeri

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

Înțelegere rapidă a problemei:

Vor exista N-cuvinte și un cuvânt rezultat. Trebuie să atribuim fiecărui caracter unui număr (de la 1 la 9) și să înlocuim caracterele N-cuvintelor și cuvintelor rezultate cu numerele corespunzătoare. Dacă suma numerelor de N cuvinte este egală cu numărul cuvântului rezultat , atunci tipăriți True.

EXPLICAȚIE:

Să presupunem că avem o ecuație; expresiile sunt reprezentate de cuvinte pe partea stângă și rezultatul pe partea dreaptă. Trebuie să verificăm dacă ecuația este rezolvabilă în conformitate cu următoarele reguli sau nu –
• Fiecare caracter este decodat ca o singură cifră (0-9).
• Fiecare pereche de caractere diferite trebuie să se asocieze la cifre diferite. > • Fiecare cuvânt [i] și rezultat sunt decodate ca un număr în care nu sunt prezente zero-uri.
• Suma numerelor din partea stângă va fi egală cu numărul din partea dreaptă.
• Vom verifica dacă ecuația este rezolvabilă sau nu.
Deci, dacă intrarea este ca cuvinte = [„TRIMITE”, „MAI MULTE”], rezultat = „BANI”,
Atunci ieșirea va fi Adevărată, ca atunci când mapăm litere după cum urmează:

Harta „S” -> 9, „E” -> 5, „N” -> 6, „D” -> 7, „M” -> 1, „O” -> 0, R -> 8, Y -> 2,
Apoi „SEND” + „MORE” = „BANI” este același ca 9567 + 1085 = 10652.
Pentru mai multe detalii vă rugăm să consultați acest LINK

Soluție:

Complexitatea timpului – O (n!).

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

}
}