Дано натуральное n. Подсчитать количество решений неравенства x2 + y2 < n в натуральных числах, не используя действий с вещественными числами.
Дано одно число n (1 ≤ n ≤ 1012).
Выведите одно число — количество решений неравенства.
6
3
Вывести в порядке возрастания все обыкновенные несократимые дроби, заключенные между 0 и 1, знаменатели которых не превышают n. Массив при этом заводить не следует.
Дано одно натуральное число n (2 ≤ n ≤ 1000)
Выведите дроби по одной в каждой строке. Числитель от знаменателя стоит отделять знаком « / » (как в примере)
5
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
Помимо известной операции сложения двух строк, введем операцию умножения целого неотрицательного числа a на строку s, означающую повторение строки s a раз (при a = 0 мы получаем пустую строку).
Даны строки x и z длиной не более 250 символов. Требуется найти такую минимально возможную по длине строку y, что для некоторого натурального i и целого неотрицательного a, будет выполняться следующее: подстрока(ax + y, i, k) = z, здесь i означает, с какого символа берется подстрока, k — длина подстроки строки ax + y. Нумерация символов в строке начинается с 1.
В первой строке вводится строка x, во второй строке вводится строка z. Каждая строка состоит только из маленьких латинских букв и имеет длину не более 250 символов.
Выведите минимальную по длине искомую строку y.
В первом тесте ответ — пустая строка, a = 2, i = 2.
Во втором тесте a = 1, i = 2.
В третьем тесте a = 0, i = 1.
mama amamam
mam amamam
amam
ura mura
mura
Одной из классических NP-полных задач является так называемая «Задача о рюкзаке». Формулируется она следующим образом. Дано n предметов, каждый из которых характеризуется весом wi и полезностью pi. Необходимо выбрать некоторый набор этих предметов так, чтобы суммарный вес этого набора не превышал W, а суммарная полезность была максимальна. Ваша задача состоит в том, чтобы написать программу, решающую задачу о рюкзаке.
Первая строка входного файла содержит натуральные числа n(1 ≤ n ≤ 20) и W(1 ≤ W ≤ 109). Каждая из последующих n строк содержит описание одного предмета. Каждое описание состоит из двух чисел: wi — веса предмета и pi — его полезности (1 ≤ wi, pi ≤ 109).
В первой строке выходного файла выведите количество выбранных предметов и их суммарную полезность. Во второй строке выведите через пробел их номера в возрастающем порядке (предметы нумеруются с единицы в порядке, в котором они перечислены во входном файле). Если искомых наборов несколько, выберите тот, в котором наименьшее число предметов. Если же после этого ответ по-прежнему неоднозначен, выберите тот набор, в котором первый предмет имеет наименьший возможный номер, из всех таких выберите тот, в котором второй предмет имеет наименьший возможный номер, и т. д.
2 10 10 100 9 80
1 100 1
5 100 80 1000 50 550 50 550 50 550 50 550
2 1100 2 3
6 100 80 1000 50 550 50 550 50 550 50 550 100 1100
1 1100 6
Ваш младший брат Петя недавно получил домашнее задание и ему нужна ваша помощь. Учитель дал ему последовательность чисел, которую требуется отсортировать в возрастающем порядке. Во время сортировки можно менять местами два любых числа. Каждый обмен имеет стоимость, равную сумме чисел, которые в него входят.
Напишите программу, которая найдет минимальную стоимость такой сортировки заданной последовательности.
Входной файл содержит две строки. Первая строка содержит положительное целое число n (1000 > n > 1) — количество чисел, которые требуется отсортировать. Вторая строка содержит n различных чисел (каждое положительное и не больше 1000), которые надо отсортировать.
Выведите одну строку, содержащую минимальную стоимость сортировки чисел как показано в примере.
3 3 2 1
4
4 8 1 2 4
17
5 1 8 9 7 6
41
6 8 4 5 3 2 7
34