Aseta ja koodi: TESTIN VALMISTELU

(14. joulukuuta 2020)

ONGELMAKOODI: MATH88

Tässä artikkelissa tarkastellaan ongelman ratkaisemista TESTIN VALMISTELU GET SET and CODE -kilpailussa.

Ongelma:

Kilpailusivu | CodeChef

CodeChef – alusta pyrkiville ohjelmoijille CodeChef luotiin alustana, joka auttaa ohjelmoijia tekemään siitä ison…

www.codechef.com

Vaikeus- Kova

Edellytykset – taaksepäin palaaminen, sanallinen aritmeettisuus, DFS

Ongelman kuvaus:

Kaksi ystävää David ja Rojer valmistautuivat viikoittaiseen luokkatestiinsä. Ne valmistautuvat matematiikkakokeeseen, mutta koska he lisäsivät jatkuvasti suuria kokonaislukuja ja ratkaisivat yhtälöitä, he uupuivat. He päättivät pitää tauon ja pelata peliä. He pelaavat peliä, joka auttaa heitä molemmissa (pitää hauskaa ja auttaa myös valmistautumaan matematiikkatestiin). Sanoja on N ja heidän on löydettävä TULOS näiden sanojen avulla (aivan kuten heillä on N kokonaislukua ja heidän on löydettävä kokonaisluku TULOS = N kokonaislukun summa). Koska he pelaavat tätä peliä ensimmäistä kertaa! He eivät ole liian hyviä tässä. Auta heitä löytämään sää, joiden TULOS on oikea vai ei.

HUOMAUTUS: – Yksittäisten merkkien kokonaismäärä N sanassa ei ole suurempi kuin 10. Kaikki syötetyt sanat ja TULOS ovat vain YLIMÄÄRÄISSÄ !

Syöttö:

  • Ensimmäinen rivi koostuu kokonaisluvusta N (sanojen kokonaismäärä).
  • Seuraava N rivi sisältää sanoja joiden avulla heidän on löydettävä TULOS.
  • Viimeinen rivi koostuu löytämästään TULOKSESTA.

Tulos:

Jos TULOS on oikea, tulosta ” true ”muuten tulosta” false ”.

Näytesyöttö:

3THIS
IS
TOO
FUNNY

Esimerkkilähtö:

true

Rajoitukset

  • 2≤N≤102≤N≤10
  • 1≤Theword≤101≤Theword≤10
  • 1≤Lisätuloksen ≤11 pituus

Ongelman nopea ymmärtäminen:

Tulee N-sanaa ja tulos sanaa. Jokainen -merkki on määritettävä numerolle (1-9) ja korvattava N-sanojen ja tulos sanojen merkit vastaavat numerot. Jos N sanan numeroiden summa on yhtä suuri kuin tulos sanan numero , tulosta sitten True.

SELITYS:

Oletetaan, että meillä on yhtälö; ilmaisuja edustavat sanat vasemmalla puolella ja tulos oikealla puolella. Meidän on tarkistettava, onko yhtälö ratkaistavissa seuraavien sääntöjen mukaan vai ei –
• Jokainen merkki dekoodataan yhtenä numerona (0–9).
• Jokaisen eri merkkiparin on kartoitettava eri numeroihin.
• Jokainen sana [i] ja tulos dekoodataan lukuna, jossa ei ole etunollia.
• Vasemmalla puolella olevien numeroiden summa on yhtä suuri kuin oikean puolen numero.
• Tarkistamme yhtälö on ratkeava tai ei.
Joten, jos syötteen muoto on kuin sanat = [”LÄHETÄ”, ”LISÄÄ”], tulos = ”RAHA”,
Tulos on tosi, kuten kun kartoitamme kirjaimet seuraavasti:

Kartta S -> 9, E -> 5, N -> 6, D -> 7, M -> 1, O -> 0, R -> 8, Y -> 2,
Sitten ”LÄHETÄ” + ”LISÄÄ” = ”RAHA” on sama kuin 9567 + 1085 = 10652.
Lisätietoja katso tämä LINK

Ratkaisu:

Ajan monimutkaisuus – O (n!).

Java-koodi:

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

}
}