Få sæt og kode: FORBEREDELSESTEST

(14. december 2020)

PROBLEMKODE: MATH88

I denne artikel skal vi se, hvordan man løser problemet FORBEREDELSE AF TEST af GET SET AND CODE-konkurrence.

Problemlink:

Konkurrenceside | CodeChef

CodeChef – En platform for håbefulde programmører CodeChef blev oprettet som en platform til at hjælpe programmører med at gøre det stort i …

www.codechef.com

Sværhedsgrad- Hårdt

Forudsætninger – Backtracking, verbal aritmetik, DFS

Problembeskrivelse:

To venner David og Rojer forberedte sig på deres ugentlige klassetest. De forbereder sig på matematikprøven, men på grund af kontinuerligt at tilføje store heltal og løse ligninger blev de opbrugte. De besluttede at tage pause og spille et spil. De spiller et spil, som vil hjælpe dem i begge dele (for at have det sjovt og også hjælpe med at forberede sig på matematikprøven). Der er N-ord, og de skal finde RESULTAT ved hjælp af disse ord (ligesom de har N-heltal, og de skal finde heltal RESULTAT = summen af ​​N-heltal). Da de spiller dette spil for første gang! De er ikke så gode til dette. Hjælp dem med at finde vejr, deres RESULTAT er korrekt eller ej.

BEMÆRK: – Samlet antal unikke tegn i N ord er ikke større end 10. Alle indtastningsord og RESULTAT er kun i OPPER-CASE !

Input:

  • Første linje består af et heltal N (samlet antal ord).
  • Næste N-linje indeholder ord som de skal finde RESULTAT med.
  • Sidste linje består af det RESULTAT, de fandt.

Output:

Hvis RESULTAT er korrekt, skal du udskrive “ sandt “ellers udskriver” falsk “.

Eksempelindgang:

3THIS
IS
TOO
FUNNY

Eksempeloutput:

true

Begrænsninger

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

Hurtig forståelse af problem:

Der vil være N-ord og et resultatord. Vi er nødt til at tildele hvert tegn til et tal (1 til 9) og erstatte tegnene i N-ord og resultere ord med tilsvarende numre. Hvis summen af ​​antallet af N-ord er lig med det resulterende ordnummer , skal du udskrive True.

FORKLARING:

Antag, at vi har en ligning; udtryk er repræsenteret af ord på venstre side og resultatet på højre side. Vi er nødt til at kontrollere, om ligningen kan løses under følgende regler eller ej –
• Hvert tegn afkodes som et ciffer (0 til 9).
• Hvert par af forskellige tegn skal kortlægges til forskellige cifre.
• Hvert ord [i] og resultat afkodes som et tal, hvor der ikke findes nogen nuller.
• Summen af ​​tal på venstre side svarer til tallet på højre side.
• Vi kontrollerer, om ligningen er løselig eller ej.
Så hvis input er som ord = [“SEND”, “MERE”], resultat = “PENGE”,
Så vil output være sandt, som når vi kortlægger bogstaver som følger:

Kort S -> 9, E -> 5, N -> 6, D -> 7, M -> 1, O -> 0, R -> 8, Y -> 2,
Så er “SEND” + “MORE” = “PENGE” det samme som 9567 + 1085 = 10652.
For flere detaljer se denne LINK

Løsning:

Tidskompleksitet – O (n!).

Java-kode:

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

}
}