Set en code ophalen: VOORBEREIDINGSTEST

(14 december 2020)

PROBLEEMCODE: MATH88

In dit artikel gaan we zien hoe we het probleem kunnen oplossen VOORBEREIDINGSTEST van de wedstrijd GET SET AND CODE.

Probleem link:

Wedstrijdpagina | CodeChef

CodeChef – Een platform voor aspirant-programmeurs CodeChef is gemaakt als een platform om programmeurs te helpen groot te worden in …

www.codechef.com

Moeilijkheidsgraad- Moeilijk

Vereisten – Backtracking, verbale rekenkunde, DFS

Probleembeschrijving:

Twee vrienden David en Rojer waren zich aan het voorbereiden op hun wekelijkse klassikale test. Ze bereiden zich voor op de wiskundetest, maar door het continu toevoegen van grote gehele getallen en het oplossen van vergelijkingen raakten ze uitgeput. Ze besloten een pauze te nemen en een spelletje te spelen. Ze spelen een spel dat hen bij beide zal helpen (om plezier te hebben en ook om zich voor te bereiden op de wiskundetest). Er zijn N woorden en ze moeten RESULTAAT vinden met behulp van deze woorden (net zoals ze N gehele getallen hebben en ze integer RESULT = som van N gehele getallen moeten vinden). Omdat ze dit spel voor het eerst spelen! Daar zijn ze niet zo goed in. Help ze bij het vinden van het weer of hun RESULTAAT correct is of niet.

OPMERKING: – Het totale aantal unieke tekens in N-woorden is niet groter dan 10. Alle ingevoerde woorden en RESULTAAT zijn alleen in HOOFDLETTERS !

Invoer:

  • Eerste regel bestaat uit een geheel getal N (totaal aantal woorden).
  • Volgende N-regel bevat woorden waarmee ze RESULTAAT moeten vinden.
  • Laatste regel bestaat uit het RESULTAAT dat ze hebben gevonden.

Uitvoer:

Als RESULTAAT correct is, print “ true ”else print“ false ”.

Voorbeeldinvoer:

3THIS
IS
TOO
FUNNY

Voorbeelduitvoer:

true

Beperkingen

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

Snel begrip van het probleem:

Er zullen N-woorden en een resultaatwoord zijn. We moeten elk karakter toewijzen aan een getal (1 tot 9) en de karakters van N-woorden en resultaatwoorden vervangen door overeenkomstige nummers. Als de som van het aantal N woorden gelijk is aan het resultaatwoordnummer , druk dan Waar af.

UITLEG:

Stel dat we een vergelijking hebben; uitdrukkingen worden weergegeven door woorden aan de linkerkant en het resultaat aan de rechterkant. We moeten controleren of de vergelijking oplosbaar is onder de volgende regels of niet –
• Elk teken wordt gedecodeerd als één cijfer (0 tot 9).
• Elk paar verschillende tekens moet worden toegewezen aan verschillende cijfers.
• Elk woord [i] en resultaat worden gedecodeerd als een getal waar geen voorloopnullen aanwezig zijn.
• De som van de getallen aan de linkerkant is gelijk aan het getal aan de rechterkant.
• We zullen controleren of de vergelijking is oplosbaar of niet.
Dus, als de invoer is als woorden = [“VERZENDEN”, ​​”MEER”], resultaat = “GELD”,
Dan zal de uitvoer Waar zijn, zoals wanneer we de letters als volgt:

Kaart S -> 9, E -> 5, N -> 6, D -> 7, M -> 1, O -> 0, R -> 8, Y -> 2,
Dan is “SEND” + “MORE” = “MONEY” hetzelfde als 9567 + 1085 = 10652.
Voor meer details raadpleeg deze LINK

Oplossing:

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

}
}