Решите братцы

[sk2wie]

 

[Mik00700kiM]

Здравствуй,
К сожалению, решение, лучше чем O(n*m) я придумать не смог
Так вот оно:

//считывание 1
a = []
s = input()
while (s!=""):
    a.append(s)
    s = input()

//считывание 2
n = int(input())
b = []
for i in range(n):
    b.append(input())

//сравнение
for i in range(len(a)):
    f = True
    for j in range(len(b)):
        if (a[i][0].lower()==b[j][0].lower() or a[i][-1].lower()==b[j][-1].lower()):
            if f:
                print(a[i].upper(), "#", b[j], end="", sep="")
                f = False
            else:
                print(",", b[j], end="", sep="")
    if (not f):
        print()

Вроде бы, условий по порядку вывода не было, должно сработать.

 

[Irval]

Если Вы действительно хотите достичь какого-то успеха в олимпиадах - советую пересесть на C++. Синтаксис плюсов гораздо лучше воспринимается, в отличие от того же Python, кроме того, скорость выполнения программ на C++ максимальна, что позволит выиграть драгоценные баллы, избежав TL.

Тривиальный алгоритм за O(N*M) может не являться полным на больших входных данных около 10^5. Если все равно интересно на него посмотреть - решение Mik00700kiM должно работать. Я же предлагаю воспользоваться предподсчетом для всех букв возможного алфавита (возьмем только нижний регистр латиницы -> 26 символов). Создадим двумерные массивы alph_start и alph_end, где для каждой из 26 букв будет храниться массив, каждый из элементов которого начинается/оканчивается на нее. При выводе достаточно для каждого элемента-предмета (вводятся в первых строчках) вывести все элементы alph_start[первый символ - 'A'] и alph_end[последний символ - 'A'].
Итоговая сложность составит O(N + M), что является хорошим результатом.

Код на C++:

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int main() {
    vector<vector<string>> alph_start = vector<vector<string>>(26);
    vector<vector<string>> alph_end = vector<vector<string>>(26);

    string s;
    vector<string> mas;
    while (getline(cin, s), s != "") {
        transform(s.begin(), s.end(), s.begin(), toupper);
        mas.push_back(s);
    }

    int count;
    cin >> count;
    getline(cin, s);
    for (int i = 0; i < count; i++) {
        getline(cin, s);
        if (s[0] >= 'a')
            alph_start[s[0] - 'a'].push_back(s);
        else
            alph_start[s[0] - 'A'].push_back(s);

        if (s[s.size() - 1] >= 'a')
            alph_end[s[s.size() - 1] - 'a'].push_back(s);
        else
            alph_end[s[s.size() - 1] - 'A'].push_back(s);
    }

    for (int i = 0; i < mas.size(); i++) {
        string output = mas[i] + "#";
        for (auto word : alph_start[mas[i][0] - 'A'])
            output += word + ",";
        for (auto word : alph_end[mas[i][mas[i].size() - 1] - 'A'])
            output += word + ",";
        if (output.size() != mas[i].size() + 1) {
            output.erase(output.size() - 1);
            cout << output << endl;
        }
    }
}