Алгоритмы

У Васи есть набор чисел. Для каждого запроса нужно найти минимальное число из набора, которое больше или равно заданному X. Если такого числа нет, вывести -1.

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

В первой строке — число N (1 ≤ N ≤ 100000) — размер набора.

Во второй строке — N целых чисел (1 ≤ число ≤ 1000000).

В третьей строке — число Q (1 ≤ Q ≤ 100000) — количество запросов.

В следующих Q строках — по одному числу X (1 ≤ X ≤ 1000001).

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

Для каждого запроса выведите ответ на отдельной строке.

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

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

ВАЖНО: Пиццы в списке должны быть отсортированы в лексикографическом порядке. Топпинги внутри каждой пиццы должны быть в порядке возрастания номеров.

ВХОДНЫЕ ДАННЫЕ:
Одно число N (1 ≤ N ≤ 10) - количество топпингов в меню.

ВЫХОДНЫЕ ДАННЫЕ:
Выведите 2^N строк - все возможные пиццы.
Пустая пицца (без топпингов) обозначается как "-".
Для непустых пицц выведите номера топпингов через пробел.
 

Кролик Роджер находится в начале числовой прямой (позиция 0) и хочет добраться  до позиции N, где лежит гигантская морковка.

Кролик умеет делать только два вида прыжков:
- Короткий прыжок: +1 позиция (тратит 1 единицу энергии)
- Длинный прыжок: +2 позиции (тратит 1 единицу энергии)

Сколько РАЗЛИЧНЫХ способов есть у Роджера добраться до морковки?

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

ВХОДНЫЕ ДАННЫЕ:
Одно число N (0 ≤ N ≤ 45) - позиция морковки.

ВЫХОДНЫЕ ДАННЫЕ:
Одно число - количество различных способов добраться до морковки.

Выведите все пути от корня до каждого листа дерева.

Формат входных данных
JSON с деревом решений.

Формат выходных данных
Каждый путь на отдельной строке: id узлов через пробел от корня до листа. Пути отсортированы по id конечного листа (по возрастанию).

 

Дано дерево решений и id целевого узла. Найдите путь от корня (id=0) до этого узла.

Формат входных данных
Первая строка: JSON с деревом. Вторая строка: целевой id узла.

Формат выходных данных
ID узлов от корня до целевого, через пробел.

Найдите максимальную глубину дерева решений. Глубина корня равна 0.

Формат входных данных
JSON с деревом решений.
 

Формат выходных данных
Одно целое число — глубина дерева.

В Простоквашино построили ледяную горку. Она состоит из N ступенек. На каждой ступеньке написано число — сколько секунд нужно отдохнуть, если встать на неё. Дядя Фёдор стартует перед первой ступенькой и может прыгать на 1 или 2 ступеньки вперёд. Ему нужно добраться до вершины (встать на последнюю ступеньку), потратив минимум времени на отдых.

Входные данные: В первой строке число N (1 ≤ N ≤ 10). Во второй строке N целых чисел от 0 до 100 — время отдыха на каждой ступеньке.

Выходные данные: Минимальное суммарное время отдыха.

Под ёлкой лежит N подарков в ряд. Известна радость, которую принесёт каждый подарок. По традиции Простоквашино, нельзя брать два соседних подарка — это невежливо. Дядя Фёдор хочет выбрать подарки так, чтобы суммарная радость была максимальной.

Входные данные: В первой строке число N (1 ≤ N ≤ 10). Во второй строке N целых чисел от 1 до 1000 — радость от каждого подарка.

Выходные данные: Максимальная суммарная радость.

Дети Простоквашино выстроили N санок в ряд. Каждые санки имеют определённый вес. Дядя Фёдор хочет выбрать несколько санок подряд (непрерывный отрезок), чтобы их суммарный вес был как можно ближе к числу S (грузоподъёмность трактора), но не превышал его.

Найдите максимальный суммарный вес санок, который можно погрузить на трактор.

Входные данные: В первой строке два числа N и S (1 ≤ N ≤ 10, 1 ≤ S ≤ 10^6). Во второй строке N целых чисел от 1 до 10 — веса санок.

Выходные данные: Максимальный суммарный вес санок, не превышающий S. Если ни одни санки не помещаются, выведите 0.

Шарик украшает ёлку гирляндой из N лампочек. Лампочки мигают по очереди: первая загорается в момент времени 0, вторая — в момент 1, третья — в момент 2, и так далее. Когда загорается последняя лампочка, следующей снова загорается первая, потом вторая и т.д.

Шарик хочет узнать, какая по счёту лампочка будет гореть в момент времени T.

Входные данные: Два целых числа N и T (1 ≤ N ≤ 1000, 0 ≤ T ≤ 10⁹) — количество лампочек и момент времени.

Выходные данные: Номер лампочки, которая горит в момент T.

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

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

Входные данные: Одно целое число 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 символов). 

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