Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2015-2016‎ > ‎

2. alkalom

Az előző órai feladat elemzése. Az alábbi kód egy rutinos Code Jam versenyző (Mystic) megoldásán alapul.

import java.util.*;
import java.io.*;

public class Magicka {
    public static void solve(Scanner sc, PrintWriter pw) throws Exception {
        
            int combCnt = sc.nextInt();
            boolean[][] isComb = new boolean[26][26];
            char[][] comb = new char[26][26];
            for (int i=0; i < combCnt; i++) {
                String s = sc.next();
                isComb[s.charAt(0) - 'A'][s.charAt(1) - 'A'] = true;
                isComb[s.charAt(1) - 'A'][s.charAt(0) - 'A'] = true;
                comb[s.charAt(0) - 'A'][s.charAt(1) - 'A'] = s.charAt(2);
                comb[s.charAt(1) - 'A'][s.charAt(0) - 'A'] = s.charAt(2);
            }
            
            int oppCnt = sc.nextInt();
            boolean[][] isOpp = new boolean[26][26];
            for (int i=0; i < oppCnt; i++) {
                String s = sc.next();
                isOpp[s.charAt(0) - 'A'][s.charAt(1) - 'A'] = true;
                isOpp[s.charAt(1) - 'A'][s.charAt(0) - 'A'] = true;
            }
            
            int N = sc.nextInt();           
            String s = sc.next();
            Stack<Character> stack = new Stack<Character>();
            
            for (char c : s.toCharArray()) {
                if (stack.size() == 0) {
                    stack.push(c);
                } else {
                    char p = stack.peek();
                    if (isComb[p-'A'][c-'A']) {
                        stack.pop();
                        stack.push(comb[p-'A'][c-'A']);
                    } else {
                        boolean in = false;
                        for (char x : stack) {
                            if (isOpp[x-'A'][c-'A']) {
                                in = true;
                                break;
                            }
                        }
                        if( in ) {
                            stack = new Stack<Character>();
                        } else {
                            stack.push(c);
                        }
                    }
                }
            }
            
            
            ArrayList<Character> list = new ArrayList();
            for(char x : stack) {
                list.add(0,x);
            }
            
            pw.print("[");
            for (int i=0; i < list.size(); i++) {
                if (i >= 1) pw.print(", ");
                pw.print(list.get(i));
            }
            pw.println("]");
        
    }
    
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(new FileReader("large.in"));
        PrintWriter pw = new PrintWriter(new FileWriter("large.out"));
        int caseCnt = sc.nextInt();
        for (int caseNum = 0; caseNum < caseCnt; caseNum++) {
            pw.print("Case #" + (caseNum + 1) + ": ");
            solve(sc,pw);
            }
        pw.flush();
        pw.close();
        sc.close();
    }
}



Feladat