제출 #1205610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205610		ay136416	Vlak (COCI20_vlak)	Java	0 / 70	158 ms	30860 KiB

Main

/// read all the words into a trie, marking who has what word
// minimax like strategy

import java.util.Scanner;
import java.util.StringJoiner;

class Main {
    static class Trie {
        TrieNode head;
        public void add(char[] s, boolean belongsToNina) {
            TrieNode cur = head;
            int i = 0;
            while (i < s.length) {
                if (cur.leaves[s[i]-'a'] == null) {
                    cur.leaves[s[i]-'a'] = new TrieNode();
                }
                if (belongsToNina) {
                    cur.num_ninaswords_below++;
                } else {
                    cur.num_emiljaswords_below++;
                }
                cur = cur.leaves[s[i]-'a'];
                i++;
            }
            if (belongsToNina) {
                    cur.num_ninaswords_below++;
                } else {
                    cur.num_emiljaswords_below++;
                }
        }
        public Trie() {
            head = new TrieNode();
        }
        public String toString() {
            return this.head.toString();
        }
    }
    static class TrieNode {
        int num_ninaswords_below;
        int num_emiljaswords_below;
        //boolean belongsToNina;
        TrieNode[] leaves;
        public TrieNode() {
            num_emiljaswords_below=0;
            num_ninaswords_below=0;
            //this.belongsToNina = belongsToNina;
            leaves = new TrieNode[26];
        }
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("<TrieNode nina="+num_ninaswords_below+" emilja="+num_emiljaswords_below+" leaves=[");
            StringJoiner sj = new StringJoiner(", ");
            for (int i = 0; i<26; i++) {
                if (leaves[i]!=null) {
                    sj.add((char) (i+'a') + ": " + leaves[i].toString());
                }
            }
            sb.append(sj.toString());
            sb.append("]>");
            return new String(sb);
        }
        public boolean isLeaf() {
            for (int i = 0; i<leaves.length; i++) {
                if (leaves[i] != null) return false;
            }
            return true;
        }
    }
    public static void main(String[] args) {
        System.err.println("I am ready");
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Trie trie = new Trie();
        for (int i = 0; i<n; i++) {
            trie.add(sc.next().toCharArray(), true);
        }
        int m = sc.nextInt();
        for (int i = 0; i<m; i++) {
            trie.add(sc.next().toCharArray(), false);
        }
       // System.out.println("THIS IS MY TRIE: " + trie + "\n\n\n");

        boolean ans = minimax(trie.head, true);
        System.out.println(ans ? "Nina" : "Emilja");
    }

    public static boolean minimax(TrieNode node, boolean maximizingPlayer) { // returns whether i win
        if (node==null) return false;
        if (maximizingPlayer && node.num_ninaswords_below == 0) return false;
        if (!maximizingPlayer && node.num_emiljaswords_below == 0) return false;
        /*boolean canMakeMove = false;
        for (int i = 0; i<node.leaves.length; i++) {
            if (node.leaves[i] != null) {
                if (
                    (maximizingPlayer && node.leaves[i].num_ninaswords_below>0)
                    ||(!maximizingPlayer && node.leaves[i].num_emiljaswords_below>0)) 
                    canMakeMove=true;
            }
        }
        if (!canMakeMove) return false;*/

        for (int i = 0; i<node.leaves.length; i++) {
            if (node.leaves[i] != null) {
                if (!minimax(node.leaves[i], !maximizingPlayer)) return true;
            }
        }
        return false;
    }

}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10