#python #python_3x #олимпиада
Система проверки сайта не принимает решение, пожалуйста подскажите где ошибка.
Собственно задача:
1002.Телефонные номера
Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
В современном мире вы встречаетесь с огромным количеством телефонных номеров,
которые со временем становятся всё длиннее и длиннее. И вам приходится
запоминать эти номера. Одним из простых способов запоминания является сопоставление
букв каждой цифре, как показано на следующем рисунке:
1 ij 2 abc 3 def
4 gh 5 kl 6 mn
7 prs 8 tuv 9 wxy
0 oqz
Таким образом, каждому слову или группе слов может быть сопоставлен уникальный номер,
так что можно запоминать слова вместо телефонных номеров. Очевидно, есть особый шарм
в том,
чтобы найти простую взаимосвязь между словом, используемым для запоминания телефонного
номера,
и владельцем этого номера. Так, телефонный номер 941837296 вашего друга, играющего
в шахматы,
может быть прочитан как WHITEPAWN (белая пешка), а номер 2855304 Вашего любимого учителя
может быть прочитан как BULLDOG (бульдог).
Напишите программу, находящую самую короткую последовательность слов
(имеющую наименьшее количество слов), которая соответствует заданному номеру телефона и
заданному списку слов. Соответствие описано на рисунке выше.
Исходные данные
Ввод состоит из набора тестов. Первая строка каждого теста содержит номер телефона,
к которому нужно подобрать мнемонику. Номер состоит не более чем из 100 цифр.
Вторая строка содержит общее количество слов в словаре (максимум 50 000).
Каждая из оставшихся строк содержит одно слово,
состоящее не более чем из 50 строчных латинских букв.
Общий размер ввода не превосходит 300 килобайт.
Последняя строка ввода содержит число −1.
Результат
Каждая строка вывода должна содержать кратчайшую последовательность слов, найденную
вашей программой.
Слова должны быть разделены одиночными пробелами. Если для входных данных нет решения,
соответствующая
строка вывода должна содержать текст No solution..
Если существует несколько решений, имеющих одинаковое количество слов, можете выбрать
любое из них.
Ввод и вывод данные авторами для примера:
7325189087
5
it
your
reality
real
our
4294967296
5
it
your
reality
real
our
-1
# Ожидаемый результат
reality our
No solution.
Мои вводные для теста:
2272583262772
11
ba
ra
ku
k
ss
u
ma
da
m
a
ssa
-1
По логике ответ должен быть
ba ra ku da ma ssa
Но это решение почему-то в список возможных не попадает.
Причем если ma расположить после da то это решение находится.
Вот список решений из которых идет выбор оптимального:
['ba', 'ra', 'ku', 'da', 'm', 'a', 'ss', 'a']
['a', 'a', 'ra', 'ku', 'da', 'm', 'a', 'ss', 'a']
И соответственно оптимальным код считает:
ba ra ku da m a ss a
Ну и соответственно валидатор не принимает это решение.
Подскажите пожалуйста где косяк
Мое решение:
keyboard = {'1': 'ij', '2': 'abc', '3': 'def',
'4': 'gh', '5': 'kl', '6': 'mn',
'7': 'prs', '8': 'tuv', '9': 'wxy',
'0': 'oqz'}
while True:
phone_num = input()
solutions = []
if phone_num == '-1':
break
phone_len = len(phone_num)
words = [input() for _ in range(int(input()))]
collector = []
for word in words:
if len(word) > phone_len:
continue
solution = []
for i in range(len(word)):
if word[i] not in keyboard[phone_num[i]]:
break
else:
solution.append(word)
test_solution = []
while test_solution != solution:
test_solution = solution.copy()
raw_solution = ''.join(solution)
len_solution = len(raw_solution)
new_words = [item for item in words if len(item) <= phone_len - len_solution]
if new_words:
for item in new_words:
raw_solution = ''.join(solution)
len_solution = len(raw_solution)
test_string = raw_solution + item
len_test_string = len(test_string)
if len_test_string > phone_len:
continue
for s in range(len_solution, len_test_string):
if test_string[s] not in keyboard[phone_num[s]]:
break
else:
solution.append(item)
solutions.append(solution)
if solutions:
solutions.sort(key=lambda g: len(g))
print(*solutions[0])
else:
print('No solution.')
Ответы
Ответ 1
Общий принцип решения: Пусть N – длина телефонного номера. Словарь представим как список из M слов. Все слова словаря можно сразу переписать как последовательности чисел номера. Затем создаём квадратную матрицу размерности N+1 x N+1 (Я предполагаю, что индексы везде начинаются с 0). Каждая ячейка (i,j) = k матрицы означает, что у нас есть слово под номером k из словаря такое, что оно совпадает с частью i .. j-1 цифр телефона. Заполним все её ячейки значением -1. Это будет обозначать, что у нас нет такого слова. Затем в цикле по всем словам проверяем, к какой части телефонного номера они подходят и заполняем матрицу. Затем поиском в ширину находим путь в нашей матрице из 0 в N. Если путь найден, слова из словаря под значениями ячеек пути будут решением задачи, иначе "No solution." Время заполнения матрицы O(NxM). Время поиска в ширину O(NxN). Не самый оптимальный способ: n = len(phone_num) m = int(input()) words = [input() for _ in range(m)] # Создаём матрицу (n+1) x (n+1) a = [[-1] * (n+1) for i in range(n+1)] wordNumbers = [convertToNumber(words[i]) for i in range(m)] # Заполняем матрицу переходов # перебираем слова и проверяем, что они совпадают с частью номера телефона for i in range(n): for k in range(m): number = wordNumbers[k] number_length = len(number) if (phone_num[i:i+number_length] == number): a[i][i+number_length]=k #Поиск в ширину # Сюда будем записывать вершины пути # (вес, откуда пришли, куда идём) # По вершине на каждую цифру номера vertex = [(10000000,-1,-1)] * (n+1) stack = [] stack.append(0) vertex[0]=(0, 0, 0) while(stack): top = stack.pop() ver = vertex[top] new_weight = ver[0] + 1 for j in range(top+1, n+1): k = a[top][j] if k > -1: v = vertex[j] if v[0]>new_weight: if v[1] == -1: stack.append(j) vertex[j] = (new_weight, top, k) # Извлечение пути rver = vertex[n] if rver[1] == -1: #Мы не достигли конца print('No solution.') else: way = [] pos = n while pos != 0: v = vertex[pos] way.insert(0,words[v[2]]) pos = v[1] print(' '.join(way)) Остальное вам, наверное, понятно.Ответ 2
Еще одно решение. Проходит все тесты. # Класс, описывающий структуру вершин графа class Vertex(object): def __init__(self, value, predecessor): # Слово self.value = value # Список вершин-наследников = вершина предка + длина слова self.successor = predecessor + len(value) # Метка посещения вершины self.is_explored = False def __eq__(self, other): return self.successor == other.successor # Функция перевода слова в его цифровое представление def get_number(value): letters = { 'i': '1', 'j': '1', 'a': '2', 'b': '2', 'c': '2', 'd': '3', 'e': '3', 'f': '3', 'g': '4', 'h': '4', 'k': '5', 'l': '5', 'm': '6', 'n': '6', 'p': '7', 'r': '7', 's': '7', 't': '8', 'u': '8', 'v': '8', 'w': '9', 'x': '9', 'y': '9', 'o': '0', 'q': '0', 'z': '0' } return ''.join([letters[ch] for ch in value]) # Возвращает список всех возможных вершин слова def get_vertex(edge, path): start = 0 while True: try: vertex = path.index(edge, start) yield (vertex) start = vertex + 1 except ValueError: break # Функция нахождения кратчайшего пути методом поиска в глубину (BFS) def bfs_shortest_path(graph, start, goal): queue = [[vertex] for vertex in graph[start]] while queue: path = queue.pop(0) node = path[-1] if node.is_explored: continue try: neighbours = graph[node.successor] for neighbour in neighbours: new_path = list(path) new_path.append(neighbour) queue.append(new_path) if neighbour.successor == goal: return new_path except KeyError: pass node.is_explored = True return None if __name__ == '__main__': while True: phone = input() if phone == '-1': break # Метка существования слова, с которого начинается номер is_start = False # Метка существования возможного результата is_result = False result = '' # Граф dictionary = {} for _ in range(int(input())): word = input() if is_result: continue number = get_number(word) if number == phone: is_result = True result = word else: for position in get_vertex(number, phone): if position == 0: is_start = True vertex_word = Vertex(word, position) try: if any(map(lambda w: w == vertex_word, dictionary[position])): continue dictionary[position] += [vertex_word] except KeyError: dictionary[position] = [vertex_word] if is_result: print(result) continue if is_start: result = bfs_shortest_path(dictionary, 0, len(phone)) if result: print(' '.join([word.value for word in result])) continue print('No solution.') else: print('No solution.')
Комментариев нет:
Отправить комментарий