Бирмингем Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт В Бирмингеме все номера телефонов имеют длину L и состоят только из цифр от 0 до 9 . Томас Шелби собрался позвонить своему брату Артуру, но понял, что не помнит его точный номер. У Томаса прекрасная память на цифры, так что он совершенно точно помнит все цифры номера Артура. Но в их порядке он совсем не уверен. Томас попытался составить из цифр, которые он помнит, номер Артура и записал его на листке бумаги. Он полагает, что мог перепутать позиции некоторых цифр, но таких цифр, которые стоят в его записи не на своих местах, не более K . Телефонные справочники в Бирмингеме содержат не настоящие имена жителей, а псевдонимы, которые сообщили владельцы номеров. К огорчению Томаса, он не знает, какой псевдоним принадлежит его брату. Поэтому Томас принял решение просмотреть все N номеров и выбрать те из них, которые могут оказаться номером Артура. Определите количество таких номеров. Формат входных данных В трёх строках вводятся три числа N , L , K (1≤N×L≤105 , 2≤K≤L ) — количество номеров в справочнике Томаса, длина всех номеров и максимальное количество цифр, стоящих не на своих местах в том номере, который помнит Томас. В четвёртой строке написан возможный номер Артура, записанный Томасом. В следующих N строках идут телефонные номера из телефонного справочника. Формат выходных данных В первой строке выведите одно целое число — количество номеров, которые могут оказаться номером Артура. Система оценки Решения, правильно работающие при L≤10 , K≤5 , будут оцениваться в 30 баллов. Решения, правильно работающие при условии, что в номерах телефонов встречаются только цифры 1 и 2 , будут оцениваться в 40 баллов. Замечание В первом примере Томас предполагает, что у Артура может быть номер 123 . Следовательно, именно из этих цифр и состоит настоящий номер Артура. Поскольку K=2 , то не более 2 цифр стоят не на своих местах. Под такое описание подходит только первый номер из телефонного справочника — 321 . Для получения этого номера в номере 123 нужно поменять местами первую и третью цифры. Во втором номере из телефонного справочника есть цифра 4 , которой в номере 123 нет, так что этот номер точно не подойдёт. Во втором примере также подходит только первый номер из телефонного справочника. Чтобы получить его из номера 1234 , нужно поменять местами вторую и четвёртую цифры. Второй номер из телефонного справочника также содержит все цифры из предполагаемого номера Артура. Но чтобы его получить, потребуется поменять местами все четыре цифры, что противоречит условию K=2<4.

Question 1

Задача Задача №2000811

А

Аноним

24 октября 2024 11:39 · публичный вопрос

А

Аноним 24 октября 2024 11:39

Бирмингем Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт В Бирмингеме все номера телефонов имеют длину L и состоят только из цифр от 0 до 9 . Томас Шелби собрался позвонить своему брату Артуру, но понял, что не помнит его точный номер. У Томаса прекрасная память на цифры, так что он совершенно точно помнит все цифры номера Артура. Но в их порядке он совсем не уверен. Томас попытался составить из цифр, которые он помнит, номер Артура и записал его на листке бумаги. Он полагает, что мог перепутать позиции некоторых цифр, но таких цифр, которые стоят в его записи не на своих местах, не более K . Телефонные справочники в Бирмингеме содержат не настоящие имена жителей, а псевдонимы, которые сообщили владельцы номеров. К огорчению Томаса, он не знает, какой псевдоним принадлежит его брату. Поэтому Томас принял решение просмотреть все N номеров и выбрать те из них, которые могут оказаться номером Артура. Определите количество таких номеров. Формат входных данных В трёх строках вводятся три числа N , L , K (1≤N×L≤105 , 2≤K≤L ) — количество номеров в справочнике Томаса, длина всех номеров и максимальное количество цифр, стоящих не на своих местах в том номере, который помнит Томас. В четвёртой строке написан возможный номер Артура, записанный Томасом. В следующих N строках идут телефонные номера из телефонного справочника. Формат выходных данных В первой строке выведите одно целое число — количество номеров, которые могут оказаться номером Артура. Система оценки Решения, правильно работающие при L≤10 , K≤5 , будут оцениваться в 30 баллов. Решения, правильно работающие при условии, что в номерах телефонов встречаются только цифры 1 и 2 , будут оцениваться в 40 баллов. Замечание В первом примере Томас предполагает, что у Артура может быть номер 123 . Следовательно, именно из этих цифр и состоит настоящий номер Артура. Поскольку K=2 , то не более 2 цифр стоят не на своих местах. Под такое описание подходит только первый номер из телефонного справочника — 321 . Для получения этого номера в номере 123 нужно поменять местами первую и третью цифры. Во втором номере из телефонного справочника есть цифра 4 , которой в номере 123 нет, так что этот номер точно не подойдёт. Во втором примере также подходит только первый номер из телефонного справочника. Чтобы получить его из номера 1234 , нужно поменять местами вторую и четвёртую цифры. Второй номер из телефонного справочника также содержит все цифры из предполагаемого номера Артура. Но чтобы его получить, потребуется поменять местами все четыре цифры, что противоречит условию K=2<4.

Answer

Для решения этой задачи, давайте разберем ситуацию более подробно.

Алгоритм решения

Ввод данных:
- Сначала считываем значения N, L, K.
- Затем считываем номер, который запомнил Томас, и последующие N номеров из телефонного справочника.
Проверка соответствия номеров:
- Для каждого номера из телефонного справочника необходимо проверить, можно ли получить его из запомненного номера Томасом с учетом ограничения K.
- Это предполагает, что два номера должны состоять из одних и тех же цифр, но с возможностью, что некоторые цифры могут находиться не на своих местах (максимум K).
Метод проверки соответствия:
- Сначала проверять, равны ли по длине запомненный номер и номер из справочника.
- Затем можно создать два списка: один для цифр на тех же позициях, другой — для тех, что на разных позициях.
- Если количество не совпадающих цифр меньше или равно K, то номер потенциально подходит.

Пример реализации

Теперь представим решение с использованием приведенного алгоритма:

N = int(input())
L = int(input())
K = int(input())
number_tomas = input().strip()

count = 0

for _ in range(N):
    number_directory = input().strip()
    
    if len(number_directory) != L:
        continue  # Пропускаем номер, если длина не совпадает
    
    misplaced_count = sum(1 for i in range(L) if number_tomas[i] != number_directory[i])
    
    if misplaced_count <= K:
        count += 1

print(count)

Объяснение кода:

Мы считываем количество номеров в справочнике, длину номера и максимальное количество цифр, которые могут быть не на своих местах.
Затем считываем номер, который запомнил Томас.
Для каждого номера из справочника:
- Сравниваем его длину с длиной запомненного номера. Если длины не совпадают, переходим к следующему номеру.
- Считаем количество цифр, которые стоят не на своих местах.
- Если количество таких цифр меньше или равно K, счетчик подходящих номеров увеличивается.
В конце выводим количество подходящих номеров.

Таким образом, мы можем легко определить, сколько номеров из справочника могут быть номером Артура, основываясь на памяти Томаса.

Question 2

Бирмингем Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт В Бирмингеме все номера телефонов имеют длину L и состоят только из цифр от 0 до 9 . Томас Шелби собрался позвонить своему брату Артуру, но понял, что не помнит его точный номер. У Томаса прекрасная память на цифры, так что он совершенно точно помнит все цифры номера Артура. Но в их порядке он совсем не уверен. Томас попытался составить из цифр, которые он помнит, номер Артура и записал его на листке бумаги. Он полагает, что мог перепутать позиции некоторых цифр, но таких цифр, которые стоят в его записи не на своих местах, не более K . Телефонные справочники в Бирмингеме содержат не настоящие имена жителей, а псевдонимы, которые сообщили владельцы номеров. К огорчению Томаса, он не знает, какой псевдоним принадлежит его брату. Поэтому Томас принял решение просмотреть все N номеров и выбрать те из них, которые могут оказаться номером Артура. Определите количество таких номеров. Формат входных данных В трёх строках вводятся три числа N , L , K (1≤N×L≤105 , 2≤K≤L ) — количество номеров в справочнике Томаса, длина всех номеров и максимальное количество цифр, стоящих не на своих местах в том номере, который помнит Томас. В четвёртой строке написан возможный номер Артура, записанный Томасом. В следующих N строках идут телефонные номера из телефонного справочника. Формат выходных данных В первой строке выведите одно целое число — количество номеров, которые могут оказаться номером Артура. Система оценки Решения, правильно работающие при L≤10 , K≤5 , будут оцениваться в 30 баллов. Решения, правильно работающие при условии, что в номерах телефонов встречаются только цифры 1 и 2 , будут оцениваться в 40 баллов. Замечание В первом примере Томас предполагает, что у Артура может быть номер 123 . Следовательно, именно из этих цифр и состоит настоящий номер Артура. Поскольку K=2 , то не более 2 цифр стоят не на своих местах. Под такое описание подходит только первый номер из телефонного справочника — 321 . Для получения этого номера в номере 123 нужно поменять местами первую и третью цифры. Во втором номере из телефонного справочника есть цифра 4 , которой в номере 123 нет, так что этот номер точно не подойдёт. Во втором примере также подходит только первый номер из телефонного справочника. Чтобы получить его из номера 1234 , нужно поменять местами вторую и четвёртую цифры. Второй номер из телефонного справочника также содержит все цифры из предполагаемого номера Артура. Но чтобы его получить, потребуется поменять местами все четыре цифры, что противоречит условию K=2<4.

Answer

Для решения этой задачи, давайте разберем ситуацию более подробно. ### Алгоритм решения 1. **Ввод данных**: - Сначала считываем значения `N`, `L`, `K`. - Затем считываем номер, который запомнил Томас, и последующие `N` номеров из телефонного справочника. 2. **Проверка соответствия номеров**: - Для каждого номера из телефонного справочника необходимо проверить, можно ли получить его из запомненного номера Томасом с учетом ограничения `K`. - Это предполагает, что два номера должны состоять из одних и тех же цифр, но с возможностью, что некоторые цифры могут находиться не на своих местах (максимум `K`). 3. **Метод проверки соответствия**: - Сначала проверять, равны ли по длине запомненный номер и номер из справочника. - Затем можно создать два списка: один для цифр на тех же позициях, другой — для тех, что на разных позициях. - Если количество не совпадающих цифр меньше или равно `K`, то номер потенциально подходит. ### Пример реализации Теперь представим решение с использованием приведенного алгоритма: ```python N = int(input()) L = int(input()) K = int(input()) number_tomas = input().strip() count = 0 for _ in range(N): number_directory = input().strip() if len(number_directory) != L: continue # Пропускаем номер, если длина не совпадает misplaced_count = sum(1 for i in range(L) if number_tomas[i] != number_directory[i]) if misplaced_count <= K: count += 1 print(count) ``` ### Объяснение кода: - Мы считываем количество номеров в справочнике, длину номера и максимальное количество цифр, которые могут быть не на своих местах. - Затем считываем номер, который запомнил Томас. - Для каждого номера из справочника: - Сравниваем его длину с длиной запомненного номера. Если длины не совпадают, переходим к следующему номеру. - Считаем количество цифр, которые стоят не на своих местах. - Если количество таких цифр меньше или равно `K`, счетчик подходящих номеров увеличивается. - В конце выводим количество подходящих номеров. Таким образом, мы можем легко определить, сколько номеров из справочника могут быть номером Артура, основываясь на памяти Томаса.