#3081

Темы: [Цикл while]

Дана последовательность натуральных чисел \(x_1\), \(x_2\), ..., \(x_n\). Стандартным отклонением называется величина \[ \sigma = \sqrt{\frac{(x_1-s)^2+(x_2-s)^2+\ldots+(x_n-s)^2}{n-1}} \] где \(s=\frac{x_1+x_2+\ldots+x_n}{n}\) —среднее арифметическое последовательности.

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

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

Дана последовательность натуральных чисел, оканчивающаяся числом 0.

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

Выведите ответ на задачу.

Примеры

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

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

4.16333199893

#3086

Разложение в сумму кубов

Темы: [Динамическое программирование: один параметр]

Дано натуральное число N. Необходимо представить его в виде суммы точных кубов, содержащей наименьшее число слагаемых. Программа должна вывести это число слагаемых.

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

Программа получает на вход натуральное число N, не превосходящее 10⁶.

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

Программа должна вывести единственное натуральное число.

Примеры

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

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

#3087

Банкомат

Темы: [Динамическое программирование: один параметр]

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

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

Первая строка входных данных содержит натуральное число N не превосходящее 100 — количество номиналов банкнот в обращении. Вторая строка входных данных содержит N различных натуральных чисел x₁, x₂, ..., x_N, не превосходящих 10⁶ — номиналы банкнот. Третья строчка содержит натуральное число S, не превосходящее 10⁶ —сумму, которую необходимо выдать.

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

Программа должна найти представление числа S виде суммы слагаемых из множества x_i, содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести строку No solution.

Примеры

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

5
1 3 7 12 32
40

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

32 7 1

#3088

Золотые слитки

Темы: [Задача о рюкзаке]

Даны N золотых слитков известных масс. Определите, какую наибольшую массу золота можно унести, если вместимость рюкзака не превышает S.

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

Программа получает на вход целое число S — вместимость рюкзака, не превосходящее 10000 и количество слитков N, не превосходящее 300. Далее следует N целых неотрицательных чисел, не превосходящих 100000 — веса слитков.

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

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

Примеры

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

10 3
5 7 4

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

#3089

Рюкзак

Темы: [Задача о рюкзаке]

Дано N предметов массой m₁, …, m_N и стоимостью c₁, …, c_N соответственно.

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

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

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

В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.

Во второй строке вводятся N натуральных чисел m_i, не превышающих 100.

Во третьей строке вводятся N натуральных чисел с_i, не превышающих 100.

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

Выведите одно целое число: наибольшую возможную стоимость рюкзака.

Примеры

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

4 6
2 4 1 2
7 2 5 1

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