Телефонные номера

@rebirth · Регистрация: 19.01.2017

Студворк — интернет-сервис помощи студентам

Вот задание, если хотите даю ссылку на задание http://acm.timus.ru/problem.aspx?space=1&num=1002

В современном мире вы встречаетесь с огромным количеством телефонных номеров, которые со временем становятся всё длиннее и длиннее. И вам приходится запоминать эти номера. Одним из простых способов запоминания является сопоставление букв каждой цифре, как показано на следующем рисунке:

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.

Помогите это сделать. Вот мой код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
letters = ['oqz', 'ij', 'abc', 'def', 'gh', 'kl', 'mn', 'prs', 'tuv', 'wxy']
while 1:
    a = input()
    if a == '-1':
        break
    result = {}
    for i in range(int(input())):
        word = input()
        c = ''.join([str(k) for value in word for k in range(10) if value in letters[k]])
        if c in a:
            result[word] = c
    result = [[key, k] for key, value in result.items() for k, v in result.items() if value + v == a]
    if not result:
        print('No solution.')
    else:
        print(*sorted(result)[0])

Но на сайте пишет, что ответ не верный. Подумал, что результат должен быть после того, как считает все входные данные и немного поправил код, но всё равно ответ не верный.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
letters = ['oqz', 'ij', 'abc', 'def', 'gh', 'kl', 'mn', 'prs', 'tuv', 'wxy']
r = []
while 1:
    a = input()
    if a == '-1':
        break
    result = {}
    for i in range(int(input())):
        word = input()
        c = ''.join([str(k) for value in word for k in range(10) if value in letters[k]])
        if c in a:
            result[word] = c
    result = [[key, k] for key, value in result.items() for k, v in result.items() if value + v == a]
    if not result:
        r.append('No solution.')
    else:
        r.append(' '.join(sorted(result)[0]))
print(*r, sep = '\n')

Помогите это решить(без модулей) или укажите, где ошибка.

Добавлено через 16 минут
Я понял свою ошибку. Как закончу скину сюда.

Добавлено через 26 минут
Написал такой код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
letters = ['oqz', 'ij', 'abc', 'def', 'gh', 'kl', 'mn', 'prs', 'tuv', 'wxy']
r = []
while 1:
    a = input()
    if a == '-1':
        break
    len_r = len(r)
    words = {}
    for i in range(int(input())):
        word = input()
        c = ''.join([str(k) for value in word for k in range(10) if value in letters[k]])
        if c in a:
            words[word] = c
    result = words.items()
    for i in range(len(result)):
        for j in result:
            if j[1] == a:
                r.append(j[0])
        result = [[key+' '+k, value+v] for key, value in result for k, v in words.items()]
    if len(r) == len_r:
        r.append('No solution.')
print(*r, sep = '\n')

Ввёл такие данные(сразу, всё скопировал и вставил):
7325189087
5
it
your
reality
real
our
4294967296
5
it
your
reality
real
our
213456
12
id
a
h
lm
aid
aidhlm
hl
m
dhlm
ai
aid
hlm
2017697240238123468420176972402381234684 2017697240238123468420176972402381234684 20176972402381234684
7
azipmwpbgqadtjafhmth
azipmwpbgqadtjafhmth
azipmwpbgqadtjafhmth
azipmwpbgqadtjafhmth
azipmwpbgqadtja
azipmwpbgqadtjafhmthazipmwpbgqadtjafhmth azipmwpbgqadtjafhmthazipmwpbgqadtjafhmth
fhmth
27386428376
0
97854668689678768
3
dfgdfhjghjdggzash
dfgkjt
nkhhdfsge
11111111111
5
ij
jj
ji
j
i
1234567890
5
bdh
txo
bdhkmp
i
kmp
-1
Выполнение должно было прекратиться, но не прекратилось, даже результата не дало. Ввёл ещё "-1" и возникла ошибка. Теперь мне интересно, что это такое?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
IDLE internal error in runcode()
Traceback (most recent call last):
  File "C:\Users\sprit\AppData\Local\Programs\Python\Python35-32\lib\idlelib\rpc.py", line 339, in putmessage
    r, w, x = select.select([], [self.sock], [])
TypeError: argument must be an int, or have a fileno() method.
 
During handling of the above exception, another exception occurred:
 
Traceback (most recent call last):
  File "C:\Users\sprit\AppData\Local\Programs\Python\Python35-32\lib\idlelib\rpc.py", line 240, in asyncqueue
    self.putmessage((seq, request))
  File "C:\Users\sprit\AppData\Local\Programs\Python\Python35-32\lib\idlelib\rpc.py", line 342, in putmessage
    raise OSError("socket no longer exists")
OSError: socket no longer exists

Код вроде должен работать. Теперь код вообще не запускается.

@ujif · 04.02.2025, 04:56

Сообщение от rebirth

Код вроде должен работать. Теперь код вообще не запускаетс

а я прочитал, и вообще не пойму, что вы ищете и по какой системе,
и то что 1 ij 2 abc 3 def и т.д. это вообще не понятно,
и из скольки цифр может состоять номер , и почему цифра 5 не проходит , вопросы сплошные

YuS_2 · 04.02.2025, 08:55

Сообщение от ujif

что вы ищете и по какой системе

думаю, что ТС уже давно нашел то, что искал и вряд ли ответит
А если хочется решить, то там есть ссылка на исходную задачу.

@ujif · 04.02.2025, 16:23

Сообщение от YuS_2

то там есть ссылка на исходную задачу

в исходной задаче написано тоже что и здесь, наверно перевод был с американского
у них воще ничего не понятно, другие люди

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .