Преобразования слов

@Bibo · Регистрация: 27.08.2020

Добрый день, нужна ваша помощь!
Нужно решить, задачку с данными условиями:

Ограничение времени, с 1
Ограничение памяти, МБ 64
Общее число попыток отправки 15

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

- участвуют только буквы русского алфавита а-я;
- все буквы в нижнем регистре;
- за один шаг можно преобразовать все вхождения одной буквы в другую.

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

Выходные данные
В качестве ответа в стандартный вывод программа должна выводить 1 (если превратить можно) или 0 (если превратить нельзя).

Пример 1
Входные данные: привет прикол
Выходные данные: 1
Преобразования (выводить не нужно):
в ⇒ к (прикет)
е ⇒ о (прикот)
т ⇒ л (прикол)

Пример 2
Входные данные: ааббдд ддббаа
Выходные данные: 1
Преобразования (выводить не нужно):
д ⇒ я (ааббяя)
а ⇒ д (ддббяя)
я ⇒ а (ддббаа)

Пример 3
Входные данные: абаб ааах
Выходные данные: 0
Преобразовать нельзя, так как 'б' не сможет оказаться одновременно 'а' и 'х'.

@u235 · 27.08.2020, 20:45

Bibo, приведите полный код с проверкой.

Добавлено через 3 минуты
кстати, какой должен быть ответ, если слова будут одинаковые...?

@eaa · 27.08.2020, 20:54

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def f(s, t):
    d = {}
    if len(s) != len(t):
        return 0
    if s == t:
        return 1
    for k, v in zip(s, t):
        if k not in d:
            d[k] = v
        else:
            if d[k] != v:
                return 0
    if len(d) >= 33:
        return 0
    return 1
 
 
s, t = input().split()
print(f(s, t))

не уверен, но пробуй)

@Gdez · 27.08.2020, 21:20

как вариант:
После всех проверок на длины строк, кол-во символов (< 33) :
Символы через множества - если длина равная, то 1, иначе 0

Добавлено через 2 минуты
Перед этим удалить одинаковые символы на одинаковых индексах

@u235 · 27.08.2020, 21:27

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

как вариант:
После всех проверок на длины строк, кол-во символов (< 33) :
Символы через множества - если длина равная, то 1, иначе 0

Нет, длины строк могут содержать сколько угодно символов, но не более 32-х уникальных.
Множество символов в конечной строке вполне может быть меньше: 'абв' -> 'ааа'

@Gdez · 27.08.2020, 23:28

Да
Ошибся
Тогда еще:
При создании словаря значения ключей - количество в строке одинаковых символов
Одинаковые значения в обоих словарях убираются (а: 2 и р: 2 например. 2 в первом и 2 во втором)
Оставшиеся значения ключей должны подчинятся правилу : число во втором словаре может быть только(!) суммой нескольких чисел из первого словаря

Добавлено через 14 минут
По идее вроде так - если минимум второго словаря (после удаления одинаковых чисел) меньше минимума первого и (или) максимум первого больше максимума второго, то "0"
В остальных случаях частичные суммы первого можно преобразовать в числа второго

Добавлено через 1 час 35 минут

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def f(s, t):
    if len(s) != len(t):
        return 0
    if s == t:
        return 1
    ds = {key : s.count(key) for key in set(s)}
    dt = {key : t.count(key) for key in set(t)}
    if len(dt) >= 33 or len(dt) > len(ds) :
        return 0                
    num_s = sorted(list(ds.values()))
    num_t = sorted(list(dt.values()))
    for i in range(len(num_t)) :
        if num_t[i] > num_s[i] :
            break
        elif num_t[i] < num_s[i] :
            return 0
    for i in range(len(num_t)) :
        if num_t[len(num_t) - 1 - i]  > num_s[len(num_s) - 1 - i] :
            break
        if num_t[len(num_t) - 1 - i]  < num_s[len(num_s) - 1 - i] :
            return 0
    return 1
 
 
s, t = input().split()
print(f(s, t))

@Kelta · 29.08.2020, 13:41

- участвуют только буквы русского алфавита а-я;
из этого следует что проверка словаря излишне

@Gdez · 29.08.2020, 13:45

Если длина второго словаря = 33 и словари не равны друг другу, то решения нет - менять нечем

@Kelta · 01.09.2020, 02:42

Python
1
2
3
4
5
6
7
8
9
10
11
12
a, s = input('').split()
if len(a) != len(s):
    print('0')
x= {}
if len(a) == len(s):
    mapping = str.maketrans(a, s)
    t = a.translate(mapping)
    if str(t) == str(s):
     x ltn() = sttr()
        print('1')
    if str(t) != str(s):
        print('0')

вроде решение правильное но нет! походу задание понять не могу или с кодом косяк исключая. есть добрые люди кто подскажет (не кодом а советом) где не там свернул

зелёный в питоне я совсем

@Gdez · 01.09.2020, 05:20

После первого условия нужно "перестроить" слова в порядке возрастания (убывания) частоты входящих в них символов. Например, "рекрут" -> "ррекут" или "екутрр"

Добавлено через 2 минуты
Ну и проверка на количество различных символов во втором слове (<33) нужна - для промежуточной замены (по условию)

Новые блоги и статьи Все статьи Все блоги /
23. что сделано за последнее время. anaschu 17.06.2026 • Эталон: Клиника НИИ питания РАМН, Москва — централизованный пищеблок, 225 коек, 180 пациентов • Git: репозиторий med2, ветка абсентеизм. Рабочий файл: СРесурсами1_v4. alp • Смежный проект:. . .	22. Подключение слоя системной динамики (потоковые диффуры): экономические метрики модели anaschu 17.06.2026 Апдейт модели: финансовый контур, разделение затрат Продолжаю развивать модель рабочего коллектива на AnyLogic. В этот раз работа шла над агентом Экономика — финансовым SD-слоем модели. Задача:. . .	[golang] Insert Delete GetRandom O(1) (Leetcode: 380) alhaos 16.06.2026 Insert Delete GetRandom O(1) Сложность: Medium Источник: LeetCode 380 Задача Реализовать структуру данных RandomizedSet, которая поддерживает следующие операции за O(1) в среднем:	Свет в конце тоннеля kumehtar 16.06.2026 Поймал себя на одной мысли. Раньше мне всегда казалось неправильным жить без чёткого понимания, куда всё идёт. Будто я иду по дороге судьбы, но не знаю, куда она ведёт. А раз не знаю — значит,. . .
[golang] Реализация стека с поддержкой получения минимального элемента за O(1) alhaos 16.06.2026 Min Stack Сложность: Medium Источник: LeetCode 155 Задача: Реализовать стек который поддерживает push, pop, top и получение минимального элемента за O(1). Методы:	[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. alhaos 10.06.2026 Задача Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. Сигнатура func Fetch(urls string, maxConcurrent int) Result Пример urls :=. . .	[golang] Состояние гонки (race condition) alhaos 10.06.2026 Состояние гонки (race condition) Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .	Взрослые отношения, и почему они не получаются kumehtar 09.06.2026 Когда в детстве ребёнок не получает от родителей чего-то важного, он лишается не просто приятных переживаний, а основы для формирования определённых внутренних качеств и навыков. Если ребёнок не. . .

@Bibo 0 / 0 / 0 Регистрация: 27.08.2020 Сообщений: 7

	Преобразования слов 27.08.2020, 15:57. Показов 6395. Ответов 28 Метки python, для начинающих, Задачи, решения (Все метки) Добрый день, нужна ваша помощь! Нужно решить, задачку с данными условиями: Ограничение времени, с 1 Ограничение памяти, МБ 64 Общее число попыток отправки 15 На вход подается 2 строки. Нужно определить, можно ли превратить первую строку во вторую, заменяя одни буквы на другие, с учетом следующих правил: - участвуют только буквы русского алфавита а-я; - все буквы в нижнем регистре; - за один шаг можно преобразовать все вхождения одной буквы в другую. Входные данные Входная информация поступает из стандартного ввода в виде одной строки. В этой строке содержатся две подстроки, разделенные пробелом. Ваше решение должно учитывать вариант, когда на вход поданы строки разной длины. Некорректные данные на вход не поступают, дополнительные проверки не требуются. Выходные данные В качестве ответа в стандартный вывод программа должна выводить 1 (если превратить можно) или 0 (если превратить нельзя). Пример 1 Входные данные: привет прикол Выходные данные: 1 Преобразования (выводить не нужно): в ⇒ к (прикет) е ⇒ о (прикот) т ⇒ л (прикол) Пример 2 Входные данные: ааббдд ддббаа Выходные данные: 1 Преобразования (выводить не нужно): д ⇒ я (ааббяя) а ⇒ д (ддббяя) я ⇒ а (ддббаа) Пример 3 Входные данные: абаб ааах Выходные данные: 0 Преобразовать нельзя, так как 'б' не сможет оказаться одновременно 'а' и 'х'. 0

@u235 5526 / 2879 / 572 Регистрация: 07.11.2019 Сообщений: 4,774
	27.08.2020, 20:45
	Bibo, приведите полный код с проверкой. Добавлено через 3 минуты кстати, какой должен быть ответ, если слова будут одинаковые...? 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,319
	27.08.2020, 21:20
	как вариант: После всех проверок на длины строк, кол-во символов (< 33) : Символы через множества - если длина равная, то 1, иначе 0 Добавлено через 2 минуты Перед этим удалить одинаковые символы на одинаковых индексах 0

@Kelta 0 / 0 / 0 Регистрация: 29.08.2020 Сообщений: 2
	29.08.2020, 13:41
	- участвуют только буквы русского алфавита а-я; из этого следует что проверка словаря излишне 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,319
	29.08.2020, 13:45
	Если длина второго словаря = 33 и словари не равны друг другу, то решения нет - менять нечем 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,319
	01.09.2020, 05:20
	После первого условия нужно "перестроить" слова в порядке возрастания (убывания) частоты входящих в них символов. Например, "рекрут" -> "ррекут" или "екутрр" Добавлено через 2 минуты Ну и проверка на количество различных символов во втором слове (<33) нужна - для промежуточной замены (по условию) 0