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

@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

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

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

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита табличной части. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем