--->
13 задач
<---
Источники
В классе учатся N человек. Классный руководитель получил указание разбить их на R бригад по С человек в каждой и направить на субботник (N = R∙C).
Все бригады на субботнике будут заниматься переноской бревен. Каждое бревно одновременно несут все члены одной бригады. При этом бревно нести тем удобнее, чем менее различается рост членов этой бригады.
Числом неудобства бригады будем называть разность между ростом самого высокого и ростом самого низкого членов этой бригады (если в бригаде только один человек, то эта разница равна 0). Классный руководитель решил сформировать бригады так, чтобы максимальное из чисел неудобства сформированных бригад было минимально. Помогите ему в этом!
Рассмотрим следующий пример. Пусть в классе 8 человек, рост которых в сантиметрах равен 170, 205, 225, 190, 260, 130, 225, 160, и необходимо сформировать две бригады по четыре человека в каждой. Тогда одним из вариантов является такой:
1 бригада: люди с ростом 225, 205, 225, 260
2 бригада: люди с ростом 160, 190, 170, 130
При этом максимальное число неудобства будет во второй бригаде, оно будет равно 60, и это наилучший возможный результат.
Формат входных данных:
Сначала вводятся натуральные числа R и C количество бригад и количество человек в каждой бригаде (1 ≤ R∙C ≤ 1000). Далее вводятся N = R∙C целых чисел по одному в строке — рост каждого из N учеников. Рост ученика — натуральное число, не превышающее 1 000 000 000.
Формат выходных данных:
Выведите одно число — наименьше возможное значение максимального числа неудобства сформированных бригад.
Пример
| Входные данные | Выходные данные |
2 4 170 205 225 190 260 130 225 160 | 60 |
В одной далекой стране ученые обнаружили странное скопление камней. Изучив его, ученые пришли к выводу, что это части старой крепостной стены, имевшей форму окружности. К сожалению, время и вандалы разрушили некоторые части стены.
Чтобы защитить оставшиеся фрагменты стены и продолжить их изучение в спокойной обстановке, ученые хотят обнести фрагменты стены забором из колючей проволоки. Если сделать отдельный забор для каждого фрагмента, будет неудобно переходить от одного фрагмента к другому, поэтому ученые хотят сделать один общий забор, окружающий все фрагменты.
Помогите ученым посчитать минимальную возможную длину забора, чтобы они знали, сколько просить колючей проволоки.
Во входном файле задано два натуральных числа: число фрагментов \(n\) (1 ≤ \(n\) ≤ 180) и радиус крепости \(r\) (1 ≤ \(r\) ≤ 100). Далее следует n пар целых чисел, описывающих сохранившиеся фрагменты стены: \(a_i\), \(b_i\) – углы в градусах, соответствующие началу и концу фрагмента. Углы отмеряются от направления на север из центра крепости, против часовой стрелки (0 ≤ \(a_i\), \(b_i\)< 360, \(a_i\) ≠ \(b_i\)). Каждый фрагмент от начального угла к конечному также проходится против часовой стрелки. Фрагменты не имеют общих точек.
Выведите минимальную возможную длину забора. Ответ должен отличаться от правильного не более, чем на \(10^{-3}\).
1 100 0 90
298.5009889168
Мария Ивановна, учитель средней школы 5 села Уборкино, заполняет классный журнал. Но она неожиданно столкнулась с проблемой: список имен, который у неё есть, не отсортирован. Помогите ей! Список необходимо отсортировать в алфавитном порядке по фамилиям. Люди с одинаковой фамилией должны идти в том же порядке, в котором они идут в исходном списке.
Первая строка входного файла содержит натуральное число \(N\) (\(1\leq N\leq 20\,000\)) — количество человек в классе. Далее идут \(N\) строк, содержащих по два слова, записанных через пробел: фамилия и имя ученика. В записи фамилии и имени встречаются только буквы латинского алфавита, причём первая буква всегда большая, а остальные — маленькие. Длина фамилии не менее 1 и не более 20. Длина имени не менее 1 и не более 20.
Выходной файл должен полностью удовлетворять формату входного файла и должен содержать тот же список, но отсортированный согласно условию.
4 Pupkin Vasya Ivanov Petya Iskandeev Semil Ivanov Roma
4 Iskandeev Semil Ivanov Petya Ivanov Roma Pupkin Vasya
В обувном магазине продается обувь разного размера.Известно, что одну пару обуви можно надеть на другую,если она хотя бы на три размера больше. В магазин пришел покупатель.Требуется определить, какое наибольшее количество пар обуви сможет предложить ему продавец так, чтобы он смог надеть их все одновременно.
Сначала вводится размер ноги покупателя (обувь меньшего размера он надеть не сможет), в следующей строке — размеры каждой пары обуви в магазине через пробел. Размер — натуральное число, не превосходящее 100.
Выведите единственное число — максимальное количество пар обуви, которое сможет надеть покупатель.
60 60 63
2
26 30 35 40 41 42
3
В олимпиаде участвовало \(N\) человек. Каждый получил определенное количество баллов, при этом оказалось,что у всех участников — разное число баллов.
Упорядочите список участников олимпиады в порядке убывания набранных баллов.
Программа получает на вход число участников олимпиады \(N\). Далее идет \(N\) строк, в каждой строке записана фамилия участника, затем, через пробел, набранное им количество баллов.
Выведите список участников (только фамилии) в порядке убывания набранных баллов.
3 Ivanov 15 Petrov 10 Sidorov 20
Sidorov Ivanov Petrov