Beecrowd 2035 50% 错误我的代码无法处理大输入

Question

背景：

阿根廷橄榄球目前正处于有史以来最好的时刻之一。 最近，U-18 和 U-21 国家队获得了晋级资格 相应的世界杯，所以两支球队的教练都要求 令人难以置信的服装生产委员会 (ICPC) 提供 这些活动的 T 恤。每支队伍由N名队员组成，但是 因为两届世界杯不是同时举行 同意 ICPC 仅提供 N 件 T 恤，供双方使用 团队。

因此，T 恤必须是适用于双方的有效服装。 团队。橄榄球世界杯的规则规定，每位球员必须 穿着印有唯一编号的 T 恤前往野外， 以玩家姓氏为前缀，不一定是唯一的。这 包括边界情况，例如没有姓氏前缀的 T 恤（即 即，长度为 0) 的前缀和带有完整姓氏的 T 恤。

ICPC的专家立即意识到他们可以简单地 提供N件T恤，上面只有数字，没有姓氏，每件 其中任何一个都将是一件有效的 T 恤，可供任何球员使用 两队。然而，教练们更愿意穿T恤 具有尽可能长的前缀，当然不违反世界 杯赛规则，因为这样他们更容易识别 比赛进行期间的球员。

你的任务是帮助ICPC找到最大数量的字母 可以印在一套N件T恤上，所以这一套是 两队均有效的服装套装。例如，如果我们有 N = 3 18岁以下队由“PEREZ”、“GONZALEZ”和 “LOPEZ”，而21岁以下队伍则由“GARCIA”、“PERALTA”组成 和“RODRIGUEZ”，最佳选择是拥有一件 T 恤 带有 1 个字母的前缀“G”（由“GONZALEZ”和“GARCIA”使用）， 另一个带有 3 个字母前缀“PER”（由“PEREZ”和 “PERALTA”），以及第三件带有 0 字母前缀的 T 恤（将用于 由“洛佩兹”和“罗德里格斯”）。这样一来，本例的答案就是 1+3+0=4。

输入

每个测试用例都用三行描述。第一行包含 单个整数 N，表示每个游戏中的玩家数量 两队 (1 ≤ N ≤ 104)。第二行包含姓氏 18岁以下队伍中的N名球员，而第三行包含 21岁以下球队中N名球员的姓氏。每个姓氏都是一个 最多 100 个大写字母的非空字符串。在每个测试用例中 2N个姓氏中的字符总数最多为105个，并且 同一队或不同队的两名或多名球员可能有相同的 姓氏。

输入的结束由包含数字-1的行表示。

输出

对于每个测试用例，您应该打印一行包含 整数，表示最多可以包含的字母数 印在一组 N 件有效 T 恤上，供两队使用 在问题陈述中进行了解释。

我的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    int N;
    
    while (scanf("%d", &N) && N != -1) {
        int total_letters = 0;

        // Dynamically allocating an array of strings for the teams
        char ***teams = (char ***)malloc(2 * sizeof(char **));
        for (int i = 0; i < 2; i++) {
            teams[i] = (char **)malloc(N * sizeof(char *));
            for (int j = 0; j < N; j++) {
                teams[i][j] = (char *)malloc(101 * sizeof(char)); // Allocates 101 characters for each name
            }
        }

        
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < N; j++) {
                scanf("%100s", teams[i][j]); 
            }
        }

        // Comparison between players of team 0 and players of team 1
        for (int i = 0; i < N; i++) {
            int max_prefix = 0; 

            // Compare player i of team 0 with all players of team 1
            for (int j = 0; j < N; j++) {
                int current_prefix = 0; 
                
                // Compare character by character
                for (int k = 0; teams[0][i][k] != '\0' && teams[1][j][k] != '\0'; k++) {
                    if (teams[0][i][k] == teams[1][j][k]) {
                        current_prefix++; // Increment the length of the prefix
                    } else {
                        break; // Stop when a difference is found
                    }
                }

                // Update the longest common prefix found for player i of team 0
                if (current_prefix > max_prefix) {
                    max_prefix = current_prefix;
                }
            }

            // Accumulate the longest prefix found for player i
            total_letters += max_prefix;
        }

        // Print the total number of letters that can be printed on the shirts
        printf("%d\n", total_letters);

        // Free the allocated memory
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < N; j++) {
                free(teams[i][j]); // Free each string
            }
            free(teams[i]); // Free the array of strings
        }
        free(teams); // Free the main array
    }

    return 0;
}

好吧，我的代码按照预期的方式运行，输入较低，例如：

Input:3
PEREZ GONZALEZ LOPEZ
GARCIA PERALTA RODRIGUEZ
Output:4

根据 Beecrowd 网站，此输出是正确的。

但是，当输入较大时，它会变得混乱并失去精度。

Input:11
BABBABAABAABBAABABBBBAABABBAAAABABBBBBBBAAAABAA ABB BBBBBABAABAABBAABBAAABBABBBBABBBBBBBBBAABAAAABABABAABAABBBABBBAABABBAAAABBAABABBABABBBAB BABBAAABBBBABAAAABBBBBBBABAAAAABBABBAAAAAABBAABAAABABBBBAAAAABAABAAABBABBABAABA BABBBBBBBABBBAAAABBAAABABABABBAAAAABBAABAABABABAABABBABAAAABBBBBAB BBBBAAABBBBA BBBB ABBABBABABAAAAABAABABBABABBBBBAABABAABBAAABABBAABAAABBBAAABBABBBBAAABAAABAAABB BAABAABAAAAAABBABBAAABABBABAABBBABABABABBBABAAAABABBBAAAABBABAABBBBBABAAAABABABBABBB ABBBBAAABABABABBAABBAAABBBAABABBAABABABABBBABBABABA ABBBAABBBABBAAABAABBBABAAAAAAAAAAAABBAAAABBBABBBBBAAAAABAABA
BBABABBBAABABBAABBBBAABBAAABABAB BABAAABBBAAABABBABBBBAAAAABBAAABAAAABBBAABAABBBAABAABA AAAAAAAAAAABBAABBBBABBABABBAAABAABBBBBBABBABBABAABABBAABBBAAAABBABAAABABABBABBBABAAAABBAAB BAAAAAABAABBABBABAAAAAAABAABBBBAABABAAAAAABABABBAABABBABAAAABAABAABBAABBAABABABAAABBAABBA BABBAAAAAAAAABABBBAABBBBAAABBABABAABABBBBABAABAABBABBBAAAAAABBABABBBABB AABABBABBABBBBABABBABABABBABABBBAAAAABBBBBBABBAAABAAABAAAAAABBBABABBBBABABBBBBBABABBABAAABABB BBABBAAABBAAABBBBABBBBBAAABABABAAABBABBBBBBABAAABABAAABAABABAAAABABAABABAAABA AABBBBABBAAABBABABABABABBBABBAABBBBABBBBBABBA AABABAAAABBABBAAAA AABBBBBBBBBBAAABBBABBBAABBBBBBBAABBBBBBABBB ABBABABABAABBBBBBABABBBABABA
Output:39

根据 Udebug 网站（Beecrowd 的调试站点），此输出不正确；应该是 25。我不知道为什么会发生这种情况。

Answer 1

考虑以下示例输入。

2
PERDOMO PEREZ
PERALTA RUIZ

您的程序输出 6，因为来自 0 队的两名球员 PERDOMO 和 PEREZ 与来自 1 队的一名球员（分别为 PERALTA）都有一个 3 个字符的公共前缀。 因此，您建议服装套装可以包含两件都标有 PER 的衬衫。 这对于 0 队来说没问题，但对于 1 队就不行了，因为 RUIZ 不能穿这两件衬衫。 正确答案是 3：一件带有

PER

的衬衫和一件空白的衬衫。

所以你的算法太简单了。 如果您要尝试将团队 0 中的每个玩家与团队 1 中具有共同前缀的玩家“匹配”，则必须确保两个团队 0 玩家不会同时与同一个团队 1 玩家匹配。

我把它留给你来制定一个正确解决问题的新算法，因为这毕竟是比赛的重点。