Limit: 3s

Je potřeba vytvořit grafovou (orientovanou) strukturu a tu pak do hloubky procházet od uzlu, který nemá rodiče (nepatří pod žádný jiný uzel, takovému se říká KOŘEN). Aby se to lépe provádělo, je asi lepší vytvářet vazby přesně opačně, než jak je znázorněno na obrázku v zadání. Při průchodu do hloubky je nutné při sestupu (před zanořením rekurze) určit identifikátor registru, který použije dané hradlo (takové to T1, T3, R3 …).

Pokud známe hodnoty uzlů pod tím aktuálním (pod = všech, co jsou navázané na tento uzel ), známe i hodnotu aktuálního (známe hodnotu = byl již vytištěn příkaz, který tu hodnotu vypočte - např. „AND T3,R1,R3;“). Je dobré si u uzlu pamatovat, zda je již známá jeho hodnota (ulehčí to práci).

Při vynořování (na konci té funkce, která je rekurzivní) vypíšeme příkaz a nastavíme uzel na známý.

Doufám, že to je alespoň trochu pochopitelný postup. Kdyžtak se ptejte, budu to tu sledovat a odpovídat.

Další možnost je uspořádat uzly do topologického uspořádání pomocí odebírání kořenů. Algoritmus je popsaný např. zde. Takto uspořadané uzly můžeme převést na odpovídající příkazy assembleru. Algoritmus je ale výpočetně náročnější (a zhruba 3x pomalejší) než procházení do hloubky zmíněné výše, takže se asi nevyplatí.

Dejte bacha na to, že čísla R1-Rx v kódu assembleru nejsou libovolná, ale odpovídají pozici uzlu ve vstupu.

Úloha se nezdá být tak složitá jak vypadá na první pohled. Řešit se dá pomocí prohedávání do hloubky. Nejprve ale musíme graf nějak uložit, abychom ho mohli dobře zpracovat. Reprezentace grafu mohou být různé. Nabízí se reprezentace pomocí spojového seznamu, maticí. (Já použil spojový seznam.)

reprezentace grafu spojovým seznamem

Když máme uloženu reprezentaci grafu, můžeme začít procházet graf. Postupně projdeme graf do hloubky (DFS) ze všech vrcholů (registrů R). V každém uzlu (instrukci) si ukládáme vstupní parametry, což je předchůdce respektive jeho výsledek (registr R nebo T). U NOT nám stačí jeden parametr u AND a OR samozrejmě dva. Pokud při průchodu máme všechny potřebné parametry, pošleme instrukci na výstup, pokud ještě parametry nemáme, dostaneme je v některém z dalších průchodů. Po posledním průchodu máme na výstupu všechny požadované instrukce.

Pokud byste našli nějakou chybu, nepřesnost, nebo se vám bude zdát řešení špatné - doplňte, opravte, smažte.

btw. zatim i moje reseni ma chybku (9/10 bodu)…

základní fragmenty kódu (cpp):

class CNode{
public:
	CNode **children;                // seznam potomku
	CNode *parent;                   // odkaz na rodice                     
	bool known;                      // je hodnota jiz znama
	string type;                     // typ uzlu [AND, OR, NOT, REG]
	string regId;                    // identifikator pridruzeneho registru (např. T3)
	/* konstruktor, destruktor */
	void link(CNode *node);          // provazani s dalsim uzlem
	void print();                    // vypise prikaz vypocitavajici hodnotu tohoto uzlu
	void compute();                  // rekurzivni fce. prirazuje regId uzlum a vypisuje je ve spravnem poradi
};

void CNode::compute(){
        // ziskat id
	if (this->type!=REG){
                // uzel neni registrem [REG], vytvari pomocny registr Tx [x je cislo]
		ostringstream oss;
		oss << "T" << lastRegID;
		lastRegID++;
		this->regId=oss.str();
	}
	// vytisknout vsechny, co jsou pod...
	for (int i=0; i<this->chNum; i++){             // chNum udava, kolim ma akt uzel potomku
		if (!children[i]->known){
			children[i]->compute();
		}
	}
	this->known=true;
	this->print();
}

Pak staci nalezt v hlavnim programu uzel, ktery nema parent (je korenem):

uzel->parent==NULL

a na nem zavolat:

uzel->compute();

by exander

package pal;
 
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
 
abstract class Node {
    public ArrayList<Node> childs = new ArrayList<Node>();
    public ArrayList<Node> parents = new ArrayList<Node>();
    public abstract String output();
}
 
abstract class NodeOp extends Node {
    private static int tempCounter = 0;
    private int id = 0;
    public String output() {
        if (id == 0) doOutput(id = ++tempCounter);
        return "T" + id;
    }
    public abstract void doOutput(int id);
}
 
class NodeNot extends NodeOp {
    public void doOutput(int id) {
        Iterator<Node> it = childs.iterator();
        System.out.println("NOT " + "T" + id + "," + it.next().output());
    }
}
 
class NodeAnd extends NodeOp {
    public void doOutput(int id) {
        Iterator<Node> it = childs.iterator();
        System.out.println("AND " + "T" + id + "," + it.next().output() + "," + it.next().output());
    }
}
 
class NodeOr extends NodeOp {
    public void doOutput(int id) {
        Iterator<Node> it = childs.iterator();
        System.out.println("OR " + "T" + id + "," + it.next().output() + "," + it.next().output());
    }
}
 
class NodeReg extends Node {
    private static int varCounter = 0;
    private int id = ++varCounter;
    public String output() {
        return "R" + id;
    }
}
 
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
 
        int nodeCount = s.nextInt();
        Node[] nodeArray = new Node[nodeCount];
        for (int i = 0; i < nodeCount; i++) {
            String tempStr = s.next();
            if (tempStr.equalsIgnoreCase("R")) {
                nodeArray[i] = new NodeReg();
            } else if (tempStr.equalsIgnoreCase("N")) {
                nodeArray[i] = new NodeNot();
            } else if (tempStr.equalsIgnoreCase("O")) {
                nodeArray[i] = new NodeOr();
            } else if (tempStr.equalsIgnoreCase("A")) {
                nodeArray[i] = new NodeAnd();
            }
        }
 
        int edgeCount = s.nextInt();
        for (int i = 0; i < edgeCount; i++) {
            int from = s.nextInt() - 1;
            int to = s.nextInt() - 1;
            nodeArray[to].childs.add(nodeArray[from]);
            nodeArray[from].parents.add(nodeArray[to]);
        }
 
        Node rootNode = nodeArray[0];
        while (rootNode.parents.size() > 0) {
            rootNode = rootNode.parents.iterator().next();
        }
 
        rootNode.output();
    }
}

jedno ošklivé řešení na 9/10

package pal;
 
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
 
        Scanner s = new Scanner(System.in);
        int pocUzlu = s.nextInt();
        Uzel[] poleUzlu = new Uzel[pocUzlu];
        for (int i = 0; i < pocUzlu; i++) {
            poleUzlu[i] = new Uzel(s.next());
        }
 
        int pocHran = s.nextInt();
        boolean[] hledani = new boolean[pocUzlu];
        for (int i = 0; i < pocHran; i++) {
            int dite = s.nextInt();
            poleUzlu[(s.nextInt() - 1)].setDeti(dite - 1, poleUzlu);
            hledani[dite - 1] = true;
        }
 
        poleUzlu[dejKoren(hledani)].vypsat();
    }
 
    static int dejKoren(boolean[] hledani) {
        for (int i = 0; i < hledani.length; i++) {
            if (hledani[i] == false) {
                return i;
            }
        }
        return -1;
    }
}
 
class Uzel {
 
    static int poc = 1;
    int id = 1;
    static int idR = 1;
    int znam = 0;
    String typ = "";
    Uzel[] deti = new Uzel[2];
 
    Uzel(String t) {
        if (t.equals("R")) {
            typ = "R" + idR;
            idR++;
            znam = 1;
            return;
        } else if (t.equals("A")) {
            typ = "AND";
        } else if (t.equals("O")) {
            typ = "OR";
        } else if (t.equals("N")) {
            typ = "NOT";
        }
    }
 
    void setDeti(int dite, Uzel[] pole) {
        if (deti[0] == null) {
            deti[0] = pole[dite];
        } else {
            deti[1] = pole[dite];
        }
    }
 
    void vypsat() {
 
        if (typ.equals("NOT") || (typ.equals("OR") || typ.equals("AND"))) {
            id = poc++;
            if (deti[0].znam == 0) {
                deti[0].vypsat();
            }
            if (deti[1] != null && deti[1].znam == 0) {
                deti[1].vypsat();
            }
            String tisk = typ + " " + "T" + id + "," + deti[0].typ;
            if (!typ.equals("NOT")) {
                tisk = tisk + "," + deti[1].typ;
            }
            tisk = tisk + ";";
            znam = id;
            typ = "T" + id;
            System.out.println(tisk);
        }
    }
}