Всем привет! Меня зовут Аргентум, или же Бронислав. На момент написания этой статьи мне 15 лет. Недавно я победил в школьном туре олимпиады по информатике, а скоро иду на муниципальный этап.

По нынешней системе всероссийских олимпиад, программирование на олимпиаде по информатике начинается с 8 класса. У нас в школе олимпиада проводилась в формате онлайн, на платформе "Сириус". Для решения задач по программированию можно было использовать Python, C++, C#, Java, Pascal и некоторые другие. Интересно, что я потратил ~20 минут олимпиадного времени на подключение стабильного интернета.

Я бы не сказал, что я гений программирования, второй Торвальдс, Страуструп, Столлман, Гвидо Ван Россум, Билл Гейтс, Цукерберг вместе взятые. Но я старался решать. За это время, пока велись расчеты победителя школьного тура, я решил изучить олимпиадное программирование и решение задач по программированию. И эти задачи могут касаться также других предметов - химии, физики, математики и так далее, т.к. я решил, что решая такие задачи, я также закрепляю пройденный материал других.

Но почему я решил написать статью на тему олимпиадного программирования и решения проблем? Как по мне, любому человеку важно постоянно тренировать свои навыки, будь то спортсмен или программист. Решение задач закрепляет материал, заставляет человека думать и постоянно развиваться.

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

Перечень моих репозиториев исходного кода

1. Наука и инжинерные вычисления

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

2. Общие задачи (в разработке, пока пустой)

   В репозитории есть директория tasks, в ней несколько директорий - base, medium, pro и модуль тестирования задач. В них я складываю задачи по сложности - легкие в base, средние в medium, сложные в pro.

   Также в репозитории есть файл olimp.py, через которого вы можете запустить решение той или иной задачи.

Предметные задачи (Химия) - относительная молекулярная масса

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

Ниже я привел формулу для вычисления относительной молекулярной массы на примере NaCl (хлорид натрия, или же поваренная соль).

Для того, чтобы реализовать такой калькулятор, нам потребуется парсер химических функций и сам класс элемента. Герои не ищут простых путей, мы создадим все с нуля

import re                              # Импорт библиотеки для регулярных выражений
from collections import Counter        # Импорт Counter из коллекций

Сверху мы импортировали нужные нам модули. Они нужны для парсинга формулы.

class Element:
    """Класс химического элемента"""
    def __init__(self, short_name: str, electronic_conf_of_outer_layer: str,
                name: str, atomic_number: int, relative_atomic_mass: float,
                group: str, period: int, row: int, group_num: int,
                side_group: bool, is_metal: bool):
        self.short_name = short_name    # химический символ элемента
        self.electronic_conf_of_outer_layer = electronic_conf_of_outer_layer    # внешний электронный слой
        self.name = name    # название химического элемента
        self.atomic_number = atomic_number    # атомное число, заряд ядра
        self.relative_atomic_mass = relative_atomic_mass    # относитльная атомная масса
        self.group = group    # группа (A или B)
        self.side_group = side_group    # побочная ли группа (True, False), зависит от группы
        self.is_metal = is_metal    # металл ли элемент
        self.period = period    # период
        self.row = row     # ряд
        self.group_num = group_num    # номер группы (от 1 до 8)


# Словарь элементов с ключом в виде химического символа элемента
ELEMENTS = {
    # Символ ЭлКонф Название АтомноеЧисло ОтносАтомМасса группа период ряд
    # номерГруппы ЭтопобочнаяГруппа ЭтоМетал
    'H': Element('H', '1s^1', 'Водород', 1, 1.00794, 'A', 1, 1, 1, False, False),
    'He': Element('He', '1s^2', 'Гелий', 2, 4.002602, 'A', 8, 1, 1, False, False),
    'Li': Element('Li', '2s^1', 'Литий', 3, 6.941, 'A', 1, 2, 2, False, True),
    'Be': Element('Be', '2s^2', 'Бериллий', 4, 9.01218, 'A', 2, 2, 2, False, True),
    'B': Element('B', '2s^2 2p^1', 'Бор', 5, 10.811, 'A', 3, 2, 2, False, False),
    'C': Element('C', '2s^2 2p^2', 'Углерод', 6, 12.011, 'A', 4, 2, 2, False, False),
    'N': Element('N', '2s^2 2p^3', 'Азот', 7, 14.0067, 'A', 5, 2, 2, False, False),
    'O': Element('O', '2s^2 2p^4', 'Кислород', 8, 15.9994, 'A', 6, 2, 2, False, False),
    'F': Element('F', '2s^2 2p^5', 'Фтор', 9, 18.998403, 'A', 7, 2, 2, False, False),
    'Ne': Element('Ne', '2s^2 2p^6', 'Неон', 10, 20.179, 'A', 8, 2, 2, False, False),
    'Na': Element('Na', '3s^1', 'Натрий', 11, 22.98977, 'A', 1, 3, 3, False, True),
    # добавляйте другие элементы по надобности
}

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

def repl(m):
    return m[1] * int(m[2] if m[2] else 1)


def parse_molecule(formula: str) -> dict:
    while '(' in formula:
        formula = re.sub(r'\((\w*)\)(\d*)', repl, formula)
    while '[' in formula:
        formula = re.sub(r'\[(\w*)\](\d*)', repl, formula)
    formula = re.sub(r'([A-Z][a-z]?)(\d*)', repl, formula)
    formula_dict = Counter(re.findall('[A-Z][a-z]*', formula))

    return formula_dict


def get_element_mass(element):
    return ELEMENTS[element].relative_atomic_mass


def calculate_relative_molecular_mass(formula):
    result = parse_molecule(formula)
    mass = 0

    for i in result.items():
        print(f'{i[1]} {ELEMENTS[i[0]].name} = {ELEMENTS[i[0]].relative_atomic_mass * i[1]}')
        mass += get_element_mass(i[0]) * i[1]

    return mass


def main():
    formula = input('Введите формулу: ')
    mass = calculate_relative_molecular_mass(formula)
    if mass is not None:
        print(f'Относительная молекулярная масса формулы {formula} = ~{mass}')
    else:
        print(f'Ошибка парсинга формулы {formula}')


if __name__ == "__main__":
    main()

Сверху конец кода, там мы вычисляем молекулярную массу формулы.

При запуске мы вводим свою формулу... И вуаля, все работает как часы. Весь код вы можете просмотреть в моем репозитории.

Предметные задачи (Химия) - массовая доля элемента в веществе

Пошли серьезные расчеты. Ниже вы видите, как рассчитать массовую долю водорода в формуле H2O (вода).

Мы делим атомную массу элемента на молекулярную массу формулы и умножаем на 100%, и получаем проценты. В итоге - массовая доля водорода равна 11.1%

Сама формула проста - делим атомную массу элемента и умножаем ее на количество элементов на относительную молекулярную массу всей формулы, после умножаем на 100% и получаем сколько процентов занимает элемент в формуле.

Реализуем это на Python, в добавок к предыдущему коду

def calculate_mass_fraction_of_element(formula, element):
    formula = parse_molecule(formula) # парсим формулу
    mass_fraction = 0 # массовая доля
    mass = 0 # молекулярная масса

    for i in formula.items(): # высчитываем молекулярную массу
        mass += get_element_mass(i[0]) * i[1]

    for i in formula.items(): # высчитываем массовую долю элемента
        if ELEMENTS[i[0]].short_name == element:
            mass_fraction = (get_element_mass(i[0]) * i[1] / mass) * 100
            break

    return mass_fraction

Вот и все. При запуске этой функции мы получим массовую долю в процентах

Решение простых задач

1. Из массива [2, 4, 19, 20, 40, 23, 45, 1000, 34, 23, 1, -3] найдите те, которые делятся на 2 без остатка и больше 5.

   На выходе должно получиться [20, 40, 1000, 34]

print([i for i in [2, 4, 19, 20, 40, 23, 45, 1000, 34, 23, 1, -3] if i % 2 == 0 and i > 5])

2. Найдите три ключа с самыми высокими значениями в словаре my_dict = {'a':500, 'b':5874, 'c': 560,'d':400, 'e':5874, 'f': 20}.

   На выходе должно получиться ['b', 'e', 'c']

mydict = {'a':500, 'b':5874, 'c': 560,'d':400, 'e':5874, 'f': 20}
print(sorted(mydict, key=mydict.get, reverse=True)[:3])

3. Постройте числовой треугольник из 12 рядов, по типу:

1
22
333
4444
55555

rows = 12
for i in range(rows):
    for i in range(i):
        print(i, end="")
    print("")

Олимпиадное программирование

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

Любой спортивный программист выбрал бы нечитабельное решение за 1 строчку кода, чем такое же, но за две.

Принцип олимпиадного программирования - это участие в соревнованиях по решению нетривиальных алгоритмических задач. Программисту важно быстро решить задачу, не сделав ошибок (но их нет только в том коде, которого не существует). Жюри готовит описание задачи, формат входных и выходных данных, сколько максимум ресурсов может использовать программа.

Для того чтобы стать профессионалом в олимпиадном программировании, вам надо решать не только задачи на программирование, но и простые, логические задачи.

Также вам нужно будет изучить динамическое программирование - способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, которые выглядят как набор подзадач, сложность которых меньше исходной. В этом случае время вычислений по сравнению с «наивными» методами можно значительно сократить. Чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы.

Заключение

Олимпиадное программирование, решение задач - штука сложная, но полезная. Они заставляют думать и отметать неэффективные решения.

Можно начинать с Python, но постепенно переходить на C++, если хотите участвовать в более сложных олимпиадах.

Минимум для изучения в программировании - переменные, функции, операторы и логика, массивы, циклы, процедуры, классы, стандартные библиотеки.

Сайты для решения задач по программированию:

• CodeWars (решение задач)

• Kaggle (исследовательские задачи, связанные с Data Science и МО)

• LeetCode (решение задач)

• Codeforces (решение задач)

• Exercism (решение задач)

• All Cups (решение задач)

Задавайте вопросы и комментируйте, я рад услышать любое мнение. И конечно, ставьте плюсы!