Перебор

Дано число n. Вам необходимо сгенерировать все правильные скобочные последовательности, содержащие n пар скобок.

Входные данные
В первой строке дано натуральное число n (1 <= n <= 8).

Выходные данные
Выведите все правильные скобочные последовательности по возрастанию в лексикографическом порядке. Каждую в отдельной строке.

 

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

Входные данные
В первой строке вам дано положительное число n (1 <= n <= 8) - количество работ и рабочих.
В следующих n строках дано по n положительных чисел, разделенных пробелами - матрица А, где A_i,j показывает за сколько долларов рабочий под номером i выполнит работу под номером j. Для всех A_i,j выполнено 1 <= A_i,j <= 10⁵.

Выходные данные
Выведите одно число - минимальную стоимость, за которую вы можете нанять данных рабочих на все имющиеся дела.


Пояснение к примеру
Первый рабочий выполнит вторую работу, второй рабочий третью работу и третий рабочий первую работу. Итоговая стоимость 1 + 4 + 7 = 12.

Вам дано натуральное число n. Выведите все перестановки размера n в лексикографическом порядке.

Входные данные
В первой строке дано натуральное число n (1 <= n <= 7).

Выходные данные
Выведите все перестановки по возрастанию в лексикографическом порядке. Каждую в отдельной строке. Числа в перестановке должны быть отделены пробелами.

 

В тактике футбола одним из основных понятий является схема игры. Она определяет, сколько из десяти полевых игроков будут играть в защите, сколько — в полузащите и сколько — в нападении.

Например, схема игры 5-3-2 означает, что в команде пять защитников, три полузащитника и два нападающих. В соответствии с современными представлениями на схему игры накладываются следующие ограничения: должно быть не менее одного и не более пяти защитников, не менее одного и не более пяти полузащитников и не более трех нападающих. Отметим, что нападающих может в команде и не быть совсем. Будем рассматривать только такие схемы.

Будем считать, что футбольное поле имеет длину 120 метров и ширину 80 метров. Введем на нем прямоугольную декартову систему координат таким образом, как показано на рисунке. Ворота рассматриваемой нами команды находятся слева.

Будем также считать, что игрок в некоторый момент времени находится в линии полузащиты, если он находится на расстоянии не более 20 метров от центральной линии. Соответственно, игрок находится в линии защиты, если он находится не более чем в 40 метрах от «своей» лицевой линии, и в линии нападения, если находится не более чем в 40 метрах от «чужой» лицевой линии.


Например, в ситуации, изображенной на рисунке, в линии защиты находятся четыре игрока, в линии полузащиты — три, в линии нападения — также три.

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

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

Входные данные
Входной файл содержит десять строк, содержащих по два целых числа x_i и y_i каждая, — координаты каждого из игроков команды (0 ≤ x_i ≤ 120, x_i ≠ 40, x_i ≠ 80, 0 ≤ y_i ≤ 80).

Выходные данные
В первой строке выходного файла выведите k — число схем игры, по которым может играть команда. В последующих k строках в произвольном порядке выведите описание каждой из этих схем. Следуйте формату данных, приведенному в примере.

Примеры

№	Входные данные	Выходные данные
1	97 0 13 18 2 6 119 11 42 21 72 80 75 78 106 45 22 67 28 47	9 2-5-3 3-5-2 3-4-3 4-5-1 4-4-2 4-3-3 5-4-1 5-3-2 5-2-3

Примеры

№	Входные данные	Выходные данные
1	2	11 10 01 00

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

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

На обед пришло \(p\) человек, у каждого из которых тоже есть аллергия на некоторые виды специй. Попробуйте для каждого из участников обеда предположить, может ли у них возникнуть аллергия на главное блюдо?

В первой содержатся целые числа \(n\) и \(m\) (\(1 \le m \le n \le 100\)) — число специй на складе и количество специй в главном блюде соответственно.

Далее в отдельной строке идет число \(k\) (\(0 \le k \le n\)) — число специй, на которые аллергия у помощника повара.

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

В следующей строке написано число \(p\) (\(1 \le p \le 100\)) — число людей на обеде. Далее идет \(p\) блоков, описывающих специи, опасные для \(i\)-го участника обеда. Каждый блок начинается строкой с числом \(n_i\) (\(0 \le n_i \le n\)) — количеством продуктов, на которые аллергия у \(i\)-го человека, вслед за которым идёт \(n_i\) строк с названиями аллергенных специй.

Все названия — слова из латинских букв длиной не более 30 символов.

Для каждого из \(p\) запросов выведите на отдельной строке одно слово:

• NO, если обед будет полностью безвреден для очередного гостя;

• YES, если в главном блюде есть специя аллергенная для гостя;

• MAYBE, если при таких исходных данных возможна и та, и другая ситуация.

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

Формат входных данных
Первая строка: числа через пробел (от 2 до 8 чисел)
Вторая строка: целевая сумма S

Формат выходных данных
Все подмножества с суммой S, каждое на отдельной строке. Числа в подмножестве выводить через пробел в порядке возрастания. Подмножества выводить в лексикографическом порядке. Если решений нет, вывести "NO"
 

Примечание

В тестовом примере возможны только две комбинации
2+3+5=10
3+7=10
Другие комбинации не дают сумму 10.

ПОДСКАЗКА:
Для каждого числа есть два варианта: взять его или не взять. Используй отсечение: если текущая сумма уже больше S, дальше искать не нужно.

Даны номиналы монет и сумма S. Найдите количество способов  разменять сумму S данными монетами. Каждую монету можно использовать неограниченное число раз.

Важно: наборы, отличающиеся только порядком монет, считаются  одинаковыми! Например, 1+2 и 2+1 — это один способ.

Формат входных данных
Первая строка: номиналы монет через пробел (от 1 до 5 монет)
Вторая строка: сумма S (1 ≤ S ≤ 20)

Формат выходных данных
Одно число — количество способов размена.
 

Примечание

В тестовом примере способы разменять 4: 

• 1+1+1+1
• 1+1+2
• 2+2

Всего 3 способа.

ПОДСКАЗКА:
Чтобы избежать повторений (1+2 и 2+1), перебирай монеты  в определённом порядке: каждая следующая монета должна быть не меньше предыдущей.

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

Формат входных данных
Одна строка: цифры через пробел (от 2 до 5 различных цифр)

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

ПОДСКАЗКА:
Нужно отслеживать, какие цифры уже использованы. Используй множество (set) или список для отметки использованных цифр. При откате не забудь снять отметку!

Даны цифры и длина числа N. Выведите все числа длины N,  составленные из данных цифр, в которых никакие две соседние  цифры не совпадают.

Формат входных данных
Первая строка: цифры через пробел (от 2 до 5 цифр)
Вторая строка: длина числа N (2 ≤ N ≤ 5)

Формат выходных данных
Все подходящие числа, каждое на отдельной строке. Числа выводить в лексикографическом порядке.

ОБЪЯСНЕНИЕ:
Числа 11, 22, 33 не подходят, так как соседние цифры одинаковые.

ПОДСКАЗКА:
Перед добавлением цифры проверяй, не равна ли она последней добавленной. Если равна — это отсечение, пропускаем эту ветку.

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

Формат входных данных
Первая строка: цифры через пробел (от 1 до 5 цифр, все цифры > 0)
Вторая строка: целевая сумма S (1 ≤ S ≤ 15)

Формат выходных данных
Все возможные числа с суммой цифр = S, каждое на отдельной строке. Числа выводить в лексикографическом порядке. Если решений нет, вывести "NO"


ПОДСКАЗКА:
Используй отсечение! Если текущая сумма уже больше S, дальше искать не нужно — это экономит время.

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

Формат входных данных
Первая строка: цифры через пробел (от 1 до 5 цифр)
Вторая строка: длина числа N (1 ≤ N ≤ 4)

Формат выходных данных
Все возможные числа, каждое на отдельной строке. Числа выводить в лексикографическом порядке (как в словаре).


ПОДСКАЗКА:
Это базовая задача на перебор. Откат здесь не нужен, достаточно рекурсивно перебрать все комбинации.
 

Шарик и Матроскин чистят дорогу от снега. Дорога разделена на N участков. Для каждого участка известно, сколько минут нужно на его расчистку. Друзья договорились: Шарик чистит первые несколько участков с начала, а Матроскин — оставшиеся с конца. Нужно разделить работу так, чтобы максимальное время работы (у того, кто работает дольше) было минимальным.

Входные данные: В первой строке число N (2 ≤ N ≤ 10). Во второй строке N положительных целых чисел, не превышающих 1000, — время расчистки каждого участка.

Выходные данные: Минимально возможное значение максимального времени работы.

Вы работаете с простым датасетом, где нужно предсказать класс (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 знака после запятой)

Будем называть пару различных целых чисел похожими, если у них \(k\) последних цифр совпадает.

Дано число \(n\), найдите количество пар различных похожих чисел, состоящих из \(n\) цифр. Ведущие нули запрещены. Пары \((a, b)\) и \((b, a)\) считаются одинаковыми.

Формат входных данных
На первой строке находится целое число \(n\) (\(1 \le n \le 10\)).

На второй строке находится целое число \(k\) (\(1 \le k \le n\)).

Формат выходных данных
Выведите одно число — количество пар похожих чисел, состоящих из \(n\) цифр.

Даны два целых числа n и k, выведите все возможные комбинации из k чисел, выбранных из диапазона [1, n]. Порядок элементов в одной комбинации не важен. То есть комбинация (1, 2, 3) и (3, 2, 1) считается одинаковой.
Выведите на экран все такие комбинации в лексикографическом порядке. 

Входные данные
В первой строке записано целое число n, во второй - целое число k.
 

Ограничения

• 1 <= n <= 20
• 1 <= k <= n

Выходные данные
Выведите в лексикографическом порядке все возможные комбинации из k чисел, выбранных из диапазона [1, n]. Каждая комбинация чисел должна выводиться в отдельной строке, числа в одной комбинации разделяются одним пробелом.
 

Громозека очень любит валерьянку. На его родной планете Чумароза можно купить за k чумриков (местная валюта) первую упаковку валерьянки, за 2·k чумриков - вторую и так далее (иными словами, за i-ю упаковку надо заплатить i·k чумриков). Громозека хочет купить w упаковок валерьянки.  У него есть n чумриков. Сколько чумриков ему придется взять в кредит в чумарозском банке, чтобы купить w упаковок валерьянки?

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

В первой строке записано три положительных целых числа k, n, w (1  <=  k, w  <=  1000, 0 <= n <= 10⁹), стоимость первой упаковки, изначальное количество чумарозиков у Громозеки и количество упаковок валерьянки, которые он хочет купить.

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

Выведите единственное целое число - количество чумарозиков, которое Громозеке необходимо взять в кредит в банке. Если брать кредит не надо, выведите 0.

 

Примеры

№	Входные данные	Выходные данные
1	3 17 4	13

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

Входные данные
Первая строка содержит две строчные латинские буквы - строка s, которую Бельвита хочет видеть в названии пекарни. Вторая строка содержит одно целое число n (1 <= n <= 100) - количество наборов табличек в чулане. Следующие n строк содержат по две строчные латинские буквы каждая, описывающие надписи на табличках в наборах.

Выходные данные
Выведите «YES», если Бельвита может выбрать несколько табличек так, чтобы в получившемся слове была подстрока s, и «NO» иначе.
 

Примеры

№	Входные данные	Выходные данные	Примечание
1	ya 4 ah oy to ha	YES	Можно использовать третий, второй и первый набор, составив слово "tooyah", в котором есть подстрока "ya".
2	hp 2 ht tp	NO	Получить слово с подстрокой "hp" никак нельзя.
3	ah 1 ha	YES	Можно использовать две из трех табличек первого набора, составив слово "haha", где есть подстрока "ah".

 

Дана функция \(z(x) = ax^3 + bx^2 + cx + d\). Для заданных чисел a, b, c и d, выведите все целые значения x из диапазона от 0 до 1000, при которых функция z(x) принимает нулевое значение.

Входные данные
Программа получает на вход 4 числа: a, b, c и d. Каждое число записано в отдельной строке.

Выходные данные
Выведите все значение x, которые удовлетворяют условию задачи в порядке возрастания. 
 

Примеры

№	Входные данные	Выходные данные
1	1 -5 6 0	0 2 3