Решения задач ЕГЭ (27) c сайта К. Полякова (http://kpolyakov.spb.ru)

keys.py

# -*- coding: utf-8 -*-

# Демонстрация альтернативных способов решения задач ЕГЭ (27) на языке Python 3
# с сайта К. Полякова. Исправления и рекомендации приветствуются!

"""
-------------------------------------------------
Задача C4-70. 
Решение на языке Python 3.
-------------------------------------------------
70) (Д.Ф. Муфаззалов) На вход программы поступает 
последовательность из N натуральных чисел, каждое из 
которых не больше 1000. Требуется вывести цифры, 
встречающиеся в эти числах, в порядке неубывания 
частоты их появления. Если какие-то цифры встречаются 
одинаковое число раз, они выводятся в порядке убывания. 
Входные данные:
  На вход программе подаётся натуральное число N (N <= 1000), 
  а затем N натуральных чисел, каждое из которых не 
  превышает 10000. 
Пример входных данных: 
  3 
  456
  20
  3452
Пример выходных данных для приведённого примера входных данных:
  6 3 0 5 4 2
"""

# Будем хранить все цифры в списке, как на Pascal
numbers = [0] * 10
for i in range(int(input())):
    # Считываем построчно, разбиваем строку на символы
    # и записываем в список numbers
    n = list(map(int, list(input())))
    for letter in n:
        numbers[letter] += 1

# В этой задаче мы перевернём словарь (наш список), заменив
# ключи значениями, а значения - ключами
# Так мы избежим решения за O(N^2)
numbers_resorted = dict()
for i in range(len(numbers)):
    # Хак, который нужно запомнить
    # Он позволяет не ловить исключение, а дописываеть в элемент словаря
    numbers_resorted[numbers[i]] = numbers_resorted.get(numbers[i], []) + [i]

# Сортируем ключи нового словаря, как это требуется в условии
# Отрезаем нулевую встречаемость
for item in sorted(numbers_resorted.keys())[1:]:
    # Мы уже отсортировали наш список, но в обратном порядке
    for element in numbers_resorted[item][::-1]:
        print(element, end=' ')

# ------------------------------------------------------------------------------------------- end.

"""
-------------------------------------------------
Задача C4-71. 
Решение на языке Python 3.
-------------------------------------------------
71) (Д.Ф. Муфаззалов) На вход программы поступает 
последовательность из N натуральных целых чисел, каждое 
из которых не больше 1000. Требуется определить, можно 
ли записать все значащие цифры шестнадцатеричной записи 
этих чисел так, чтобы полученная строка было симметричной 
(читалась одинаково как слева направо, так и справа налево). 
Если требуемую строку составить невозможно, то программа 
должна вывести на экран число 0, а если возможно, то 
вывести число 1.
Входные данные:
  На вход программе подаётся натуральное число N (N <= 1000), 
  а затем N натуральных чисел, каждое из которых не 
  превышает 10000. 
Пример входных данных: 
  3 
  13
  22
  32
Пример выходных данных для приведённого примера входных данных:
  0
Из цифр D, 1, 6, 2, 0 нельзя составить симметричную строку.
Пример входных данных: 
  4
  186
  68
  171
  14
Пример выходных данных для приведённого примера входных данных:
  1
Из цифр A, B, 4, 4, A, B, D можно составить симметричную строку.
"""

# Будем хранить все шестнадцатеричные цифры в строке
string = str()
for i in range(int(input())):
    # Используем встроенную функцию hex (она возвращает строку!)
    string += hex(int(input()))[2:]

# Проверка на палиндромность
# Подсчет баланса на множестве
# Решение за O(N)

m = set()
for letter in string:
    if letter in m:
        m.remove(letter)
    else:
        m.add(letter)

# После того, как мы избавились от пар, проверим длину множества
if len(m) > 1:
    print(0)
else:
    print(1)

# ------------------------------------------------------------------------------------------- end.

"""
-------------------------------------------------
Задача C4-72. 
Решение на языке Python 3.
-------------------------------------------------
72) (Д.Ф. Муфаззалов) Имеется набор данных, состоящий 
из пар положительных целых чисел. Для каждой пары чисел 
находится значение А – наибольший общий делитель. Напишите 
эффективную по времени работы и по используемой памяти 
программу, которая будет определять, какое значение А 
встречалось чаще всего. Если несколько значений А встречалось 
одинаковое наибольшее количество раз, вывести их в порядке 
убывания.
Программа считается эффективной по времени, если время 
работы программы пропорционально количеству пар чисел N, 
т. е. при увеличении N в k раз время работы программы должно 
увеличиваться не более чем в k раз. Программа считается 
эффективной по памяти, если размер памяти, использованной 
в программе для хранения данных, не зависит от числа N и 
не превышает 100 килобайт.
Входные данные:
На вход программе в первой строке подаётся количество пар 
N (1 <= N <= 100000). Каждая из следующих N строк содержит 
два натуральных числа, не превышающих 1000. 
Пример входных данных: 
  6
  1 3 
  5 15  
  6 9  
  5 4  
  3 3  
  36 40  
Пример выходных данных для приведённого примера входных данных: 
  3 1
"""

def gcd(a, b):
    # Алгоритм нахождения НОД
    while b != 0:
        a, b = b, a % b
    return a


# В этой задаче нам не обойтись без словаря, так будем считать
# число повторений (можно импортировать Counter из модуля collections)
d = dict()
for i in range(int(input())):
    x, y = map(int, input().split())
    A = gcd(x, y)
    d[A] = d.get(A, 0) + 1

# Вывод результата
# Подумайте, как можно это сделать лучше (но все еще понятно)
result = list()
for item in d.keys():
    if d[item] == max(d.values()):
        result.append(item)

print(' '.join(map(str, sorted(result, reverse=True))))

# ------------------------------------------------------------------------------------------- end.

"""
-------------------------------------------------
Задача C4-76. 
Решение на языке Python 3.
-------------------------------------------------
76) Назовём длиной числа количество цифр в его десятичной 
записи. Например, длина числа 2017 равна 4, а длина числа 
7 равна 1. Дан набор из N целых положительных чисел, каждое 
из которых меньше 10**9. Необходимо определить, числа какой 
длины реже всего (но не менее одного раза) встречаются в 
данном наборе и сколько в нём чисел этой длины. Если числа 
разной длины встречаются одинаково часто (и реже, чем числа 
любой другой длины), нужно выбрать меньшую длину. Напишите 
эффективную по времени и по памяти программу для решения 
этой задачи.
Описание входных и выходных данных 
В первой строке входных данных задаётся количество чисел 
N (1 ≤ N ≤ 10000). В каждой из последующих N строк записано 
одно натуральное число, не превышающее 10**9.
Пример входных данных:
  5
  12
  417
  125
  327
  4801
Пример выходных данных для приведённого выше примера 
входных данных:
  2 1 
В данном наборе реже всего (по 1 разу) встречаются числа 
длины 2 и 4. 
"""

# Воспользуемся словарём для подсчета частоты встречаемости
d = dict()
for i in range(int(input())):
    x = len(input())
    d[x] = d.get(x, 0) + 1

# По условию, максимальное число = 10e9
ans = 10

# Возможно, можно решить изящнее
for item in d.keys():
    if d[item] == min(d.values()):
        # Получаем именно числа меньшей длины, запоминаем длину
        ans = min(ans, item)
print(ans, d[ans])

# Список будет дополняться...