Алгоритмы

Мама прислала Дяде Фёдору посылку с конфетами. Дядя Фёдор хочет разделить конфеты поровну между собой, Матроскиным и Шариком. Если конфеты не делятся на троих поровну, остаток достанется Галчонку.

Сколько конфет получит каждый из троих друзей, и сколько останется Галчонку?

Входные данные: Одно целое число N (1 ≤ N ≤ 10000) — количество конфет в посылке.

Выходные данные: Два числа через пробел: сколько конфет получит каждый из друзей и сколько достанется Галчонку.

Дана блок-схема алгоритма, реализованного в виде рекурсивно вызываемой функции:

Известно, что 𝐴, 𝐵 и 𝐶 - натуральные числа и что 𝐴 < 𝐵 < 𝐶.
Петя вызывает эту функцию, передавая ей в качестве входного параметра натуральное число. Известно, что для некоторого 𝑘 функция возвращает следующие значения:
𝐹(𝑘) = 50890368413;
𝐹(𝑘 + 1) = 93601980590;
𝐹(𝑘 + 2) = 172160883161.
Определите значения 𝐴, 𝐵 и 𝐶, при которых это возможно. Если таких вариантов несколько, выберите вариант с наименьшей суммой 𝐴, 𝐵 и 𝐶. В ответе введите в указанном порядке значения 𝐴, 𝐵 и 𝐶, разделённые пробелом.
 

У учительницы есть X конфет. Она раздаёт их ученикам по очереди, давая каждому по Z конфет. Последний ученик может получить неполную порцию, если конфет останется меньше Z. Учеников в школе достаточно много. Напишите программу, которая выведет, сколько конфет получил каждый ученик.

Входные данные:

• X — количество конфет - целое число не больше 100

• Z — конфет каждому - целое число не больше 10
  Каждое число в отдельной строке

Выходные данные: номер ученика и количество конфет через пробел (каждая пара на новой строке). 

На Discord-сервере игрок получает VIP-статус, если количество его сообщений кратно 25 и при этом не менее 300.​

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

Входные данные: количество сообщений (целое положительное число)

Выходные данные:

• VIP — если количество сообщений кратно 25 и не менее 300

• NO — в остальных случаях

В магазине Roblox действует специальная скидка: игрок получает её, если сумма его покупки кратна 50 и при этом не менее 200 робуксов.​

Напишите программу, которая запрашивает у пользователя сумму покупки и определяет, получит ли игрок скидку.

Входные данные: сумма покупки в робуксах (целое положительное число)

Выходные данные:

• YES — если сумма кратна 50 и не менее 200

• NO — в остальных случаях

Вы работаете с простым датасетом, где нужно предсказать класс (0 или 1) по одному признаку. Например, предсказываем, болен ли человек (1) или здоров (0) по температуре тела.

У вас есть:

• Массив признаков X (например, температуры)

• Массив правильных ответов y (0 или 1)

Вам нужно найти лучшие значения коэффициента w и свободного члена b методом полного перебора, чтобы минимизировать log-loss.

Алгоритм

1. Переберите все возможные значения w от -2 до 2 с шагом 0.1
2. Переберите все возможные значения b от -10 до 10 с шагом 0.5
3. Для каждой пары (w, b):
   • Посчитайте линейную комбинацию: z=w⋅X+b
   • Примените сигмоиду: p=σ(z)
   • Посчитайте log-loss
4. Выберите пару (w, b) с минимальным log-loss

Важные детали

• Используйте функцию сигмоиды
• Для расчёта log-loss используйте формулу:
  • \(\text{Log-Loss} = -\frac{1}{n}\sum_{i=1}^{n} \left(y_i \cdot \log(p_i) + (1 - y_i) \cdot \log(1 - p_i)\right)\)
• Чтобы избежать ошибок с логарифмом нуля, ограничьте вероятности: p = np.clip(p, 1e-15, 1 - 1e-15)
• Bспользуйте np.arrange() для работы с вещественным шагом, вместо range()

Формат входных данных

На вход подаётся:

• в первой строке признаки (например, температуры): вещественные числа, разделенные одним пробелом
• во второй строке правильные классы для каждого признака соответственно  (0 или 1).

 Формат выходных данных

Выведите три числа, каждое в отдельной строке:

1. best_w — лучшее значение коэффициента (float, с точностью до сотых)

2. best_b — лучшее значение свободного члена (float, с точностью до сотых)

3. min_loss — минимальное значение log-loss (float, с точностью 4 знака после запятой)

В строке содержатся теги в угловых скобках. Найдите все отдельные теги.

Формат входных данных
На вход подается одна строка. Строка содержит печатаемые ASCII-символы. В строке обязательно есть хотя бы одна подпоследовательность начинающаяся с < и заканчивающаяся >. 

Формат выходных данных
Выведите ответ на задачу. Введите все теги в одной строке, разделяя их одним пробелом.

Пример
Входные данные
<br><hr><img/>

Выходные данные
<br> <hr> <img/>

Валидация email адреса важная и не простая задача в реальной практике. Попробуйте написать одну из частей  проверки email адреса. 

---

В заданном тексте, состоящем не более чем из 100 строк, найдите все email адреса. Выведите эти адреса в столбик в порядке их встречаемости в тексте. 

Формат email адреса (немного упростим, для облегчения реализации):

• Локальная часть (до @): буквы (английские большие и маленькие), цифры, точки, дефисы, подчеркивания

• Доменная часть (после @): буквы, цифры, точки, дефисы. Доменная часть должна содержать как минимум одну точку. Недопускается две и более точек подряд. Существование доменной части не проверяется.

• Обязательно содержит символ @

• Обычно заканчивается доменом верхнего уровня (например, .com, .ru, .org и др), состоящим от 2-х до 4-х символов (существование домена верхнего уровня не проверяется). 

Примечание:

• Регистр не имеет значения

• Адреса могут быть в любом месте текста

• Нужно найти все вхождения, даже повторяющиеся

• Валидность адреса проверяется только по формату (может не существовать реально).

Формат входных данных
В первой строке записано натуральное число N - количество строке текста. Далее, идут сами строки текста.

Формат выходных данных
Выведите все искомые email адреса, каждый адрес в отдельной строке.

Словом называется последовательность символов ограниченная слева и справа пробелом или началом(концом) строки. Найдите все слова, начинающиеся на английскую букву p (без учета регистра).

Формат входных данных
Строка, состоящая из букв английского алфавита. Длина строки не более 1000 символов.

Формат выходных данных
Выведите все найденные слова в одной строке, разделяя их одним пробелом. Порядо слов должен быть таким же как в исходной строке.

Необходимо найти все строки, в которых содержится три буквы z подряд. 

Формат входных данных
Программа получает в первой строке натуральное число N - количество строк (N <= 100). Далее идет N алфавитно-цифровых строк (длина каждой строки не более 100 символов). 

Формат выходных данных
Выведите на экран все искомые строки. Строки необходимо вывести в том порядке, в котором они встречаются во входных данных.

 Найти все целые числа в строке. Число - это последовательность из одной или более цифр, которая:

• Ограничена слева либо началом строки, либо нецифровым символом

• Ограничена справа либо концом строки, либо нецифровым символом

• Может начинаться с нуля (например, "012" считается числом)

• Цифры могут повторяться

Формат входных данных
Строка, содержащая алфавитно-цифровые символы и знаки препинания. 

Формат выходных данных
Вывести все числа, находящиеся в данной строке. Все найденные числа вывести в одной строке через один пробел. Если чисел в строке нет, вывести None.

Формат входных данных
В первой строке записано натуральное число N - количество строк. Далее, записаны N строк в каждой из которых находится последовательность строчных английских букв. 

Формат выходных данных
Выведите N строк. В каждой строке необхоидимо вывести главсные буквы (aeiou), которые встречаются в соответствующей строке входных данных. Буквы должны быть выведены через пробел в том же порядке, что в исходной строке. Если в строке таких букв нет, то для такой строки необходимо вывести слово None.

 

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

Студент Павел недавно приобрёл себе подержанный автомобиль и теперь ездит на нём в университет. На его пути в вуз имеется один загруженный перекрёсток, проезд через который регулируется светофором. Сделав ряд поездок, Павел обнаружил интересную закономерность: пока на светофоре горит зелёный свет, через перекрёсток успевает проехать не менее a, но не более b машин. Сверху над перекрёстком установлена уличная видеокамера. Павел может подключиться к ней со своего смартфона и сосчитать количество машин n, которые стоят перед светофором впереди него (свою машину он тоже считает). Назовём тактом светофора включение на нём зелёного сигнала. Напишите программу, определяющую минимальный и максимальный номер такта, на котором Павел проедет перекрёсток.
Формат входных данных
Впервых двух строках входных данных записаны целые числа a и b (1 ≤a ≤ b ≤ 10⁹). В третьей строке записано целое число n (1≤ n ≤ 10⁹).
Формат выходных данных
Выведите два целых числа минимальный и максимальный номер такта светофора, на котором Павел проедет перекрёсток.

Замечание
В примере из условия перед светофором стоят 10 машин. Если через перекрёсток будут проезжать по 5 машин на зелёный свет, то Павел проедет на втором такте. Если же будут проезжать по 3 машины, то он проедет лишь на четвёртом такте.

Забор состоит из N одинаковых вертикальных досок. Некоторые из досок сгнили и нуждаются в замене, для каждой доски известно, нужно ли её заменить. Для ремонта забора можно использовать продающиеся в магазине щиты, которые бывают L разных видов: шириной в 1 доску, в 2 доски, ..., в L досок. Щит нельзя разрезать на части, то есть одним щитом можно заменить не более любых L подряд идущих досок. При этом можно менять не только сгнившие доски, но и хорошие.

Оказалось, что все щиты стоят одинаково, независимо от размера щита. Определите, какое наименьшее число щитов необходимо приобрести, чтобы починить весь забор.

Входные данные

Первая строка входных данных содержит целое число L (L > 0) – максимальный размер щита. Во второй строке входных данных записано целое число N (N > 0) – количество досок в заборе. Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующая доска в заборе нуждается в замене, число 0 – что доска может быть сохранена.

Выходные данные

Программа должна вывести одно целое число – минимальное число щитов, которое необходимо приобрести для ремонта всего забора.

re.fullmatch(pattern, string) - проверяет совпадение ВСЕЙ строки с шаблоном.

Возвращает: объект Match или None

Использование: match = re.fullmatch(r'\d+', text)
 

---

 Проверить, что строка является корректным ID товара:

• Формат: [Категория][Номер][Версия]
• Категория: 1 буква (A-Z)
• Номер: 1-3 цифры
• Версия: необязательная, начинается с '-v' и 1-2 цифры

Программа на вход получает строку и должна вывести True, если ID товара корректен и False в противном случае.

re.match(pattern, string) - проверяет совпадение ТОЛЬКО в начале строки.

• Возвращает: объект Match или None
• Использование: match = re.match(r'\d+', text)

---

 

Задача: Проверить, что строка начинается с корректного формата лог-записи:

• Дата: ГГГГ-ММ-ДД
• Время: ЧЧ:ММ:СС
• Уровень логирования: INFO, WARN, ERROR, DEBUG

В этой задаче на вход подается одна строка. Вам нужно вывести True если начало строки совпадает с шаблоном и False в противном случае.
 

re.search(pattern, string) - находит ПЕРВОЕ совпадение с шаблоном в строке.

• Возвращает: объект Match или None
• Использование: match = re.search(r'\d+', text)

---

Найти первый товар из категории Electronics и вывести его название и цену в одной строке через пробел. 

Например (только для понимания формата вывода), 
DVD 34.5$

Найти все цены выше 100$. Выведите список (аналогично первому заданию). Цены должны выводиться со знаком $.

re.findall(pattern, string) - находит ВСЕ совпадения с шаблоном в строке.

• Возвращает: список строк (если нет групп) или список кортежей (если есть группы)

• Использование: results = re.findall(r'\d+', text)

Для извлечения (сохранения) конкретной части совпадения используйте группы. 

Пример

import re

text = "Цена: 100 руб."

# Без группы
print(re.findall(r"\d+ руб", text))  # ['100 руб']

# С группой  
print(re.findall(r"(\d+) руб", text))  # ['100']

 

---

Задание
Найти все ID товаров (формат: английская буква + цифра) и вывести список (в формате ['A1', 'B2'....], ID товаров в алфавитном порядке).

Файл ко всем заданиям модуля