Задачи олимпиады "2й тур школьной олимпиады по Красноярскому краю"

Задача A. Кольцо

Заданы площадь кольца и радиус внешней окружности. Требуется определить радиус внутренней окружности.

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

Входной файл INPUT.TXT содержит два положительных вещественных числа: S и R₁ – площадь кольца и радиус внешней окружности соответственно. Радиус внешней окружности не превышает 100.

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

В выходной файл OUTPUT.TXT выведите радиус внутренней окружности R₂ с точностью не худшей, чем 10^-3.

Пример

Задача B. Числа без одинаковых цифр

Антон записал ряд натуральных чисел в порядке возрастания: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23 и т.д. Затем вычеркнул из него все числа, в которых имеется хотя бы две одинаковых цифры, и получил последовательность: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23 и т.д.

Вам необходимо по заданному N найти N-ое по счету число в получившейся последовательности.

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

В единственной строке входного файла INPUT.TXT записано натуральное число N (1 ≤ N ≤ 10000).

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

В единственную строку выходного файла OUTPUT.TXT нужно вывести N-ое по счету число без одинаковых цифр.

Пример

Задача C. Котлеты

На сковородке одновременно можно положить k котлет. Каждую котлету нужно с каждой стороны обжаривать m минут непрерывно. За какое наименьшее время удастся поджарить с обеих сторон n котлет?

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

В единственной строке входного файла INPUT.TXT записано три натуральных числа: k, m, n, не превышающих 30000.

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

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

Примеры

Задача D. Губернатор

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

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

Пронумеруем здания, требующие постройки числами от 1 до N, где N – их количество. Каждое здание i характеризуется двумя числами. Во-первых, это число a_i – его эффективность. Она является вещественным числом и обозначает то, во сколько раз возрастет текущая прибыль при постройке этого здания. Второй параметр b_i – это количество золотых монет, которые каждый месяц уходят на содержание этого здания. В итоге, если к моменту постройки i-го здания месячный доход составлял X монет, то после постройки этого здания его величина станет равна a_i•X – b_i. Отметим, что итоговый доход не обязательно будет целым числом.

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

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

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

В первой строке входного файла INPUT.TXT записаны через пробел два целых числа N и K (1 ≤ N ≤ 10 000, 1 ≤ K ≤ 10⁶). Далее, в каждой из N последующих строк описано по зданию. Каждое описание имеет вид a_i b_i, где число a_i – вещественное (0 ≤ a_i ≤ 10), а b_i – целое (0 ≤ b_i ≤ 100). i-ая из строк файла соответствует (i−1)-му зданию в нумерации, используемой комиссией.

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

В выходной файл OUTPUT.TXT выведите перестановку из N чисел от 1 до N, по одному числу на строку – номера зданий в порядке их постройки. Если существует несколько перестановок, максимизирующих прибыль, разрешается вывести любую.

Примеры