Set und Code abrufen: VORBEREITUNGSTEST

(14. Dezember 2020)

PROBLEMCODE: MATH88

In diesem Artikel erfahren Sie, wie Sie das Problem lösen können VORBEREITUNGSTEST des GET SET AND CODE-Wettbewerbs.

Problemlink:

Wettbewerbsseite | CodeChef

CodeChef – Eine Plattform für angehende Programmierer CodeChef wurde als Plattform entwickelt, um Programmierern dabei zu helfen, in…

www.codechef.com

Schwierigkeitsgrad- Schwer

Voraussetzungen – Rückverfolgung, verbale Arithmetik, DFS

Problembeschreibung:

Zwei Freunde, David und Rojer, bereiteten sich auf ihren wöchentlichen Klassentest vor. Sie bereiten sich auf den Mathe-Test vor, aber weil sie ständig große ganze Zahlen hinzufügen und Gleichungen lösen, sind sie erschöpft. Sie beschlossen, eine Pause einzulegen und ein Spiel zu spielen. Sie spielen ein Spiel, das ihnen in beiden Fällen hilft (um Spaß zu haben und sich auf den Mathe-Test vorzubereiten). Es gibt N Wörter und sie müssen mit Hilfe dieser Wörter das ERGEBNIS finden (genau wie sie N ganze Zahlen haben und sie müssen die ganze Zahl ERGEBNIS = Summe von N ganzen Zahlen finden). Da spielen sie dieses Spiel zum ersten Mal! Sie sind nicht so gut darin. Helfen Sie ihnen, das Wetter zu finden, bei dem ihr ERGEBNIS korrekt ist oder nicht.

HINWEIS: – Die Gesamtzahl der eindeutigen Zeichen in N Wörtern ist nicht größer als 10. Alle eingegebenen Wörter und ERGEBNISSE sind nur in Großbuchstaben !

Eingabe:

  • Die erste Zeile besteht aus einer Ganzzahl N (Gesamtzahl der Wörter).
  • Die nächste N-Zeile enthält Wörter mit denen sie ERGEBNIS finden müssen.
  • Die letzte Zeile besteht aus dem ERGEBNIS, das sie gefunden haben.

Ausgabe:

Wenn ERGEBNIS korrekt ist, drucken Sie “ true ”else print“ false ”.

Beispieleingabe:

3THIS
IS
TOO
FUNNY

Beispielausgabe:

true

Einschränkungen

  • 2 ≤ N ≤ 102 ≤ N ≤ 10
  • 1 ≤ Länge des Wortes ≤ 101 ≤ Länge des Wortes ≤ 10
  • 1 ≤ Länge des Ergebnisses ≤ 11

Schnelles Verständnis des Problems:

Es gibt N-Wörter und ein Ergebniswort. Wir müssen jedes Zeichen einer Zahl (1 bis 9) zuweisen und die Zeichen von N-Wörtern und Ergebniswörtern durch ersetzen entsprechende Nummern. Wenn die Summe der Zahlen von N Wörtern gleich der Ergebniswortnummer ist, drucken Sie True.

ERKLÄRUNG:

Angenommen, wir haben eine Gleichung; Ausdrücke werden durch Wörter auf der linken Seite und das Ergebnis auf der rechten Seite dargestellt. Wir müssen prüfen, ob die Gleichung nach den folgenden Regeln lösbar ist oder nicht –
• Jedes Zeichen wird als eine Ziffer (0 bis 9) dekodiert.
• Jedes Paar verschiedener Zeichen muss unterschiedlichen Ziffern zugeordnet werden.
• Jedes Wort [i] und jedes Ergebnis wird als Zahl dekodiert, bei der keine führenden Nullen vorhanden sind.
• Die Summe der Zahlen auf der linken Seite entspricht der Zahl auf der rechten Seite.
• Wir prüfen, ob Die Gleichung ist lösbar oder nicht.
Wenn also die Eingabe wie Wörter = [„SENDEN“, ​​“MEHR“], Ergebnis = „GELD“ ist,
dann ist die Ausgabe wahr, wie wenn wir die abbilden Buchstaben wie folgt:

Karte S -> 9, E -> 5, N -> 6, D -> 7, M -> 1, O -> 0, R -> 8, Y -> 2,
Dann ist „SENDEN“ + „MEHR“ = „GELD“ dasselbe wie 9567 + 1085 = 10652.
Weitere Informationen Bitte beziehen Sie sich auf diese LINK

Lösung:

Zeitkomplexität – O (n!).

Java-Code:

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

}
}