Instantly share code, notes, and snippets.

# showyou/gcj2019_1a_c.py Created Apr 13, 2019

 import copy T = int(input()) def calc_min_len(ws): min_len = 999999 for w in ws: l = len(w) if l < min_len: min_len = l return min_len def check_words_clear(words): for w in words: if w != "": return True return False def find_rhyme(words, used_suffix, num, min_len): #print("find_rhyme", num, min_len, words) if num > min_len: return 0 if not(check_words_clear(words)): return 0 lengths = [0] for i in range(len(words)): if words[i] == "" or words[i][-num:] in used_suffix: continue for j in range(i+1, len(words)): if words[j] == "": continue if words[i][-num:] == words[j][-num:]: #print("use", words[i], words[j]) words2 = copy.deepcopy(words) used_suffix2 = copy.deepcopy(used_suffix) used_suffix2.append(words[i][-num:]) words2[i] = "" words2[j] = "" len2 = 2 + find_rhyme(words2, used_suffix2, num, min_len) len2 += find_rhyme(words2, used_suffix2, num+1, min_len) lengths.append(len2) return max(lengths) for cnt in range(T): N = int(input()) words = [input() for _ in range(N)] print("Case #"+str(cnt+1)+":", str(find_rhyme(words, [], 1, calc_min_len(words))))
Owner Author

### showyou commented Apr 13, 2019

 Sampleは通りましたがWAです