Подойдет любой online judge.
Спасибо.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 160 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
8 | awoo | 154 |
10 | luogu_official | 151 |
Подойдет любой online judge.
Спасибо.
Задача:
Есть таблица некоторых критериев, которая имеет следующий вид:
A1 A2 ... A40
B1 B2 ... B40
...
Количество строк может быть около 40000.
Значение каждой ячейки -- произвольная строка (до 256 символов). Также есть специальное значение -- "*" (зведочка).
Теперь есть запрос:
Z1 Z2 ... Z40
Значения полей запроса аналогичны по структуре ячейкам таблицы, включая специальное значение.
Проверка запроса: надо найти среди строк исходной таблицы максимально совпадающую со значениями запроса. Специальное значение "*" либо в запросе, либо в таблице, означает совпадение в данной ячейке вне засимости от значения, с которым сравнивают.
Например:
XYZ GBP 123 * [все значения -- *] *
XYZ USD 123 * [все значения -- *] *
XYZ USD * * [все значения -- *] *
* * * * [все значения -- *] *
Запрос:
XYZ USD 567 * [все значения -- *] *
Ответом должна быть строка номер 3.
При банальном подходе можно просто заранее отсортировать строки таблицы по убыванию количества конкретных значений, и уже для каждого запроса проверять посрочно до первого удачного совпадения. Получается 40000*40 сравнений (не будем учитывать время сравнения самих ячеек).
Может тут как-то можно ускорить, используя результаты предыдущей строки? Например, обработав строку 2, мы знаем, что первые два поля уже совпадают, и может быть их можно уже не сравнивать... Можно индекс какой построить. Ограничения на память особых нет.
Можно даже сгенерить некий код-парсер, которых будет представлять логику конкретной исходной таблицы. Вот только вопрос, в чем должна быть идея этого парсера.
А было бы возможно подключить еще один язык - Go?
Название |
---|