Få satt og kode: FORBEREDELSESTEST

(14. des 2020)

PROBLEMKODE: MATH88

I denne artikkelen skal vi se hvordan vi kan løse problemet FORBEREDELSESTEST av GET SET AND CODE-konkurranse.

Problemlenke:

Konkurranseside | CodeChef

CodeChef – En plattform for aspirerende programmerere CodeChef ble opprettet som en plattform for å hjelpe programmerere med å gjøre det stort i …

www.codechef.com

Vanskelighets- Hard

Forutsetninger – Backtracking, Verbal Arithmetic, DFS

Problembeskrivelse:

To venner David og Rojer forberedte seg på den ukentlige klassetesten. De forbereder seg på matematikkprøven, men på grunn av kontinuerlig å legge til store heltall og løse ligninger ble de oppbrukt. De bestemte seg for å ta pause og spille et spill. De spiller et spill som vil hjelpe dem i begge deler (for å ha det gøy og også vil bidra til å forberede seg på matteprøven). Det er N-ord, og de må finne RESULTAT ved hjelp av disse ordene (akkurat som de har N-heltall og de må finne heltall RESULTAT = summen av N-heltall). Siden de spiller dette spillet for første gang! De er ikke så gode i dette. Hjelp dem med å finne vær, deres RESULTAT er riktig eller ikke.

MERKNAD: – Totalt antall unike tegn i N ord er ikke større enn 10. Alle inngangsord og RESULTAT er kun i STORE bokstaver !

Inngang:

  • Første linje består av et helt tall N (totalt antall ord).
  • Neste N-linje inneholder ord som de må finne RESULTAT med.
  • Siste linje består av RESULTATET de fant.

Output:

Hvis RESULTAT er riktig, skriv ut “ true ”ellers skriver ut” false ”.

Eksempelinngang:

3THIS
IS
TOO
FUNNY

Eksempeloutput:

true

Begrensninger

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

Rask forståelse av problemet:

Det vil være N-ord og et resultatord. Vi må tilordne hvert tegn til et tall (1 til 9) og erstatte tegnene i N-ord og resultatord med tilsvarende tall. Hvis summen av N-ord er lik resultatet ordnummer , så skriv ut True.

FORKLARING:

Anta at vi har en ligning; uttrykk er representert med ord på venstre side og resultatet på høyre side. Vi må sjekke om ligningen er løst i henhold til følgende regler eller ikke –
• Hvert tegn blir dekodet som ett siffer (0 til 9).
• Hvert par forskjellige tegn må tilordnes til forskjellige sifre.
• Hvert ord [i] og resultat blir dekodet som et tall der ingen ledende nuller er tilstede.
• Summen av tall på venstre side vil være lik tallet på høyre side.
• Vi vil sjekke om ligningen er løst eller ikke.
Så hvis inngangen er som ord = [“SEND”, “MER”], resultat = “PENGER”,
Så vil utgangen være sann, som når vi kartlegger bokstaver som følger:

Kart S -> 9, E -> 5, N -> 6, D -> 7, M -> 1, O -> 0, R -> 8, Y -> 2,
Så er “SEND” + “MORE” = “PENGER” det samme som 9567 + 1085 = 10652.
For mer informasjon vennligst 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");
}

}
}