import java.io.IOException; import java.io.InputStreamReader; import java.io.BufferedReader; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.StringTokenizer; public class Main { static int N, K; static HashSet required = new HashSet<>(Arrays.asList('a', 'n', 't', 'i', 'c')); static ArrayList words = new ArrayList<>(); static ArrayList possible = new ArrayList<>(); static boolean[] learned = new boolean[26]; static int answer = 0; public static void nonDuplicatedLetter() { HashSet nonDuplicated = new HashSet<>(); for (String word : words) { for(char ch : word.toCharArray()) { if (!required.contains(ch)) { nonDuplicated.add(ch); } } } possible.addAll(nonDuplicated);; } public static void dfs(int k, int index) { if (k == K-5) { int possibleCount = countPossibleWords(); answer = Math.max(answer, possibleCount); } else { for (int i = index; i < 26; i++) { if(!learned[i]){ learned[i] = true; dfs(k + 1, i + 1); learned[i] = false; } } } } public static int countPossibleWords() { int count = 0; for (String word : words) { boolean canRead = true; int wordsLen = word.length(); for (int j = 0; j < wordsLen; j++) { if (!learned[word.charAt(j) - 'a']) { canRead = false; break; } } if (canRead) { count++; } } return count; } public static void input() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); N = Integer.parseInt(st.nextToken()); K = Integer.parseInt(st.nextToken()); for (int i = 0; i < N; i++) { String temp = br.readLine(); if (K > 5) { words.add(temp.substring(4, temp.length() - 4)); } } learned['a' - 'a'] = true; learned['n' - 'a'] = true; learned['t' - 'a'] = true; learned['i' - 'a'] = true; learned['c' - 'a'] = true; } public static void main(String[] args) throws IOException { input(); if (K < 5) { System.out.print(0); } else if (K == 26) { System.out.print(N); } else { nonDuplicatedLetter(); dfs(0, 0); System.out.print(answer); } } }

제출 #18585

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: