Informatika gyűjtemény

Egy szinttel feljebb fg_Vasut.java

2004050607080910

<<  22. óra  >>

<<  Vasút  >>

NézetNyomtat

fg_Vasut.java (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 4 KB
package vasut;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;

/**
 * http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0910/22ora/vasut
 * Írta: Fehér Gábor, 2010-03-17
 *
 * Ez a megoldás a lehetséges állapotok halmazát tartja nyilván, sorban
 * veszi a B vágányon lévő vagonokat és mindegyik után frissíti az
 * állapothalmazt.
 * -A vagonok 1..4 helyett 0..3 vannak számozva.
 * -Az A,C,D által leírt állapotok nem 3-dimenziós, hanem 1-dimenziós tömbben
 *  vannak tárolva.
 */
public class Vasut {
    /**
     * A legnagyobb lehetséges kódolt állomás-állapot + 1.
     */
    final static int MAXCODE = 1024;

    /* A két állapothalmaz. states[0] az egyik, states[1] a másik.
     */
    boolean states[][];

    int cur, prev; // az aktuális és előző állapothalmazt jelölik ki

    String strCode0(int j, int nn) {
        String res = "";
        while (j != 0) {
            if (j % 2 == 1) res = "1"+res;
            else res = "0"+res;
            nn--;
            j = j/2;
        }
        while (nn > 0) {
            res = "0"+res;
            nn--;
        }
        return res;
    }

    /**
     * Kiírja egy állapot tartalmát, szépen.
     */
    String strCode(int stateACD) {
        return strCode0(stateACD % 4, 2)
                +" "+strCode0((stateACD / 4) % 16, 4)
                +" "+strCode0((stateACD / 64) % 16, 4);
    }

    int code(int A, int C, int D) {
        return A+(C<<2)+(D<<6);
    }

    /**
     * @return A legkisebb helyiértékű bitjének sorszáma.
     */
    int minStack(int A) {
        int min = 0;
        //                A[min] == false
        while (min < 4 && (A>>min & 1) == 0) {
            min++;
        }
        return min;
    }

    /**
     * Hozzáadja a stateACD állapotból egy vagon számú vagon
     * hozzáadásával kapható állapotokat a states[cur][] állapothalmazhoz.
     */
    void nextStates(int stateACD, int vagon) {
        int A, C, D;
        A = stateACD % 4;
        stateACD = stateACD >> 2;
        C = stateACD % 16;
        stateACD = stateACD >> 4;
        D = stateACD % 16;
        stateACD = stateACD >> 4;
        if (stateACD > 0) throw new RuntimeException("eeeeeeeeeee");

        for (int flush = A; flush < 4; flush++) {
            if (((C|D) & 1<<flush) != 0) {
                // a flush számú kocsik mozgatása A-ba, C-ből és D-ből is
                C = C & ~(1<<flush);
                D = D & ~(1<<flush);
                A = flush;
            }

            if (vagon >= A) {
                // 1.eset: a következő vagon az A vágányra megy
                states[cur][ code(vagon,C,D) ] = true;
            
                // 2.eset: a következő vagon a C vágányra megy
                if (minStack(C) >= vagon) {
                    states[cur][ code(A, C | 1<<vagon, D) ] = true;
                }
                // 3.eset: a következő vagon a D vágányra megy
                if (minStack(D) >= vagon) {
                    states[cur][ code(A, C, D | 1<<vagon) ] = true;
                }
            }
        }
    }

    /**
     * @return Igaz, ha az s-ben lévő vagonsorozat rendezhető.
     */
    boolean solve(String s) {
        states = new boolean[2][MAXCODE];
        cur = 0;
        prev = 1;
        states[prev][code(0, 0, 0)] = true;

        for (int i = 0; i < s.length(); i++) {
            int ch = s.charAt(i);
            if (ch < '1' || ch > '4') continue;
            ch = ch-'1';

            for (int j = 0; j < MAXCODE; j++) {
                if (states[prev][j]) {
                    nextStates(j, ch);
                }
                states[prev][j] = false;
            }

            cur = 1-cur; prev = 1-prev; // a két halmaz cseréje
        }

        for (int i = 0; i < MAXCODE; i++) {
            if (states[prev][i]) return true;
        }
        return false;
    }

    /**
     * Beolvassa és megoldja az id. számú tesztesetet.
     */
    void run(int id) throws IOException {
        PrintWriter pw = new PrintWriter("vasut2.ki"+id);
        BufferedReader br =
                new BufferedReader(new FileReader("vasut.be"+id));
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            boolean res = solve(br.readLine());
            if (res) pw.println("IGEN");
            else pw.println("NEM");
        }
        br.close();
        pw.close();
    }
    void run_all() throws IOException {
        for (int i = 1; i <= 8; i++) {
            run(i);
        }
    }
    public static void main(String[] args) throws IOException {
        new Vasut().run_all();
    }
}
(Vissza)