Рус № 4 Бирмингем Ограничение по времени: 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

Задача Задача №2000902

А

Аноним

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

А

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

Рус № 4 Бирмингем Ограничение по времени: 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

Для решения данной задачи нам необходимо определить, сколько из телефонов в базе данных могут быть возможным номером Артура, основываясь на том, что Томас помнит все цифры, но может перепутать их позиции, не более чем на K мест.

Шаги решения:

Чтение данных: Сначала прочитаем значения N (количество номеров), L (длина каждого номера) и K (максимальное количество неправильно расположенных цифр). Затем запишем предполагаемый номер Артура и все номера из телефонного справочника.
Сравнение номеров: Для каждого номера из справочника будем сравнивать его с предполагаемым номером Артура и подсчитывать количество неправильно расположенных цифр.

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

Пример кода на Python:

# Ввод данных
N, L, K = map(int, input().strip().split())
arthur_number = input().strip()
possible_numbers = [input().strip() for _ in range(N)]

# Счетчик подходящих номеров
count = 0

# Проходим по каждому номеру из справочника
for number in possible_numbers:
    # Проверяем количество несовпадающих позиций
    mismatch_count = 0
    for i in range(L):
        if number[i] != arthur_number[i]:
            mismatch_count += 1
            
    # Если количество несовпадений не больше K, увеличиваем счетчик
    if mismatch_count <= K:
        count += 1

# Выводим результат
print(count)

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

Мы используем input() для получения данных. Первые три числа считываются как параметры задачи, а последующие N строк идут на хранение возможных номеров.
Внутренний цикл проверяет каждый символ номера и номера Артура. Если символы не совпадают, увеличиваем счетчик mismatch_count.
После завершения проверки для каждого номера, если mismatch_count меньше или равно K, мы увеличиваем общий счетчик count.
Наконец, выводим общее количество подходящих номеров.

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

Question 2

Рус № 4 Бирмингем Ограничение по времени: 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

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