На День учителя Вася решил купить букет цветов. В магазине продаются ромашки по A рублей за штуку и гладиолусы по B рублей за штуку (A < B). У Васи есть C рублей. Он хочет составить букет из максимально возможного количества цветов, и при этом потратить как можно больше денег. Другими словами, из всех букетов с максимально возможным количеством цветов он хочет выбрать самый дорогой, но не дороже C рублей. Помогите ему вычислить стоимость такого букета.
Вводятся три целых числа A, B, C (1 ≤ A < B ≤ 100, 0 ≤ C ≤ 1000).
Выведите одно число — стоимость самого дорогого букета из максимального количества цветов.
В первом тесте искомый букет состоит из четырёх ромашек и одного гладиолуса. Во втором — только из трёх ромашек.
2 3 11
11
3 5 10
9
Компания из M человек пришла в пиццерию. Посовещавшись, они решили заказать одну большую пиццу с K начинками. Пицца представляет собой круг, поделённый на K равных секторов, в каждом из которых находится своя начинка. Пиццу подают ещё не разрезанной.
Друзья попросили официанта разрезать пиццу на M равных секторов, по одному куску на человека, так, чтобы как можно большему количеству людей достался кусок по крайней мере с двумя начинками.
Помогите официанту определить, какому именно количеству людей достанется больше одной начинки, если резать пиццу наиболее оптимально.
Вводятся два целых числа K, M (1 ≤ K ≤ 100, 1 ≤ M ≤ 100) — количество начинок в пицце и количество человек в компании соответственно.
Выведите количество человек, которым достанется более одной начинки в наилучшем случае.
В первом тесте каждому достанется по две начинки, если резать как угодно, но не по границам секторов с начинками.
Во втором тесте не важно как резать: в любом случае обоим достанется по половине пиццы, в каждой из которых будет больше одной начинки.
3 3
3
3 2
2
В этой задаче Вася готовится к олимпиаде. Учитель дал ему N (1 ≤ N ≤ 100 000) задач для тренировки. Для каждой из этих задач известно, каким умением ai нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения i-й задачи Васино умение увеличивается на число bi.
Исходное умение Васи равно A. Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения?
Сначала вводятся два целых числа N, A (1 ≤ N ≤ 100 000, 0 ≤ A ≤ 109) — количество задач и исходное умение. Далее идут N пар целых чисел ai, bi (1 ≤ ai ≤ 109, 1 ≤ bi ≤ 109) — соответственно сколько умения нужно для решения i-й задачи и сколько умения прибавится после её решения.
Выведите одно число — максимальное количество задач, которое Вася сможет решить.
3 2 3 1 2 1 1 1
3
Глеб обожает шоппинг. Как-то раз он загорелся идеей подобрать себе кепку, майку, штаны и ботинки так, чтобы выглядеть в них максимально стильно. В понимании Глеба стильность одежды тем больше, чем меньше разница в цвете элементов его одежды.
В наличии имеется N1 кепок, N2 маек, N3 штанов и N4 пар ботинок (1 ≤ Ni ≤ 100 000). Про каждый элемент одежды известен его цвет (целое число от 1 до 100 000). Комплект одежды — это одна кепка, майка, штаны и одна пара ботинок. Каждый комплект характеризуется максимальной разницей между любыми двумя его элементами. Помогите Глебу выбрать максимально стильный комплект, то есть комплект с минимальной разницей цветов.
Для каждого типа одежды i (i = 1, 2, 3, 4) сначала вводится количество Ni элементов одежды этого типа, далее в следующей строке — последовательность из Ni целых чисел, описывающих цвета элементов. Все четыре типа подаются на вход последовательно, начиная с кепок и заканчивая ботинками. Все вводимые числа целые, положительные и не превосходят 100 000.
Выведите четыре целых числа — цвета соответственно для кепки, майки, штанов и ботинок, которые должен выбрать Глеб из имеющихся для того, чтобы выглядеть наиболее стильно. Если ответов несколько, выведите любой.
3 1 2 3 2 1 3 2 3 4 2 2 3
3 3 3 3
1 5 4 3 6 7 10 4 18 3 9 11 1 20
5 6 9 20
В городе Н. олимпиада по информатике состоит из двух туров, каждый из которых оценивается из 400 баллов. Для удобства все её участники занумерованы числами от 1 до N.
Сразу после проведения олимпиады курьер принёс жюри пренеприятнейшее известие: «сверху» пришло указание о том, что некто Вася, выступавший в олимпиаде под номером 1, должен по итогам олимпиады занять место A, то есть ровно A - 1 участников должны набрать по сумме двух туров больше баллов, чем Вася. При этом места, занятые школьниками в каждом из туров в отдельности, уже опубликованы, и их менять нельзя. Для каждого тура дан список номеров участников в порядке занятого места — перестановка чисел от 1 до N. Теперь задача жюри заключается в том, чтобы расставить целые баллы от 1 до 400 каждому участнику в первом и втором турах таким образом, чтобы в итоговой таблице Вася занял место A, а места участников в каждом из туров не изменились.
Никакие два участника не должны получить в одном туре одинаковые баллы. Одинаковые баллы в итоговой таблице возможны.
Ваша задача — проделать за жюри такую работу или определить, что это невозможно.
В первой строке вводятся два целых числа N, A (1 ≤ N ≤ 200, 1 ≤ A ≤ N) — соответственно количество участников олимпиады и требуемое Васино место. Во второй строке перечислены номера участников в порядке занятых мест в первом туре (от первого места до N-го). В третьей строке в таком же формате следует описание второго тура. Номера участников во второй и третьей строках разделены пробелами.
В случае, если невозможно расставить баллы требуемым образом, выведите единственное слово Impossible. Иначе в первой строке выведите Possible, во второй строке выведите N целых чисел от 1 до 400, соответствующих расстановке баллов участникам первого тура, где i-ое число — балл в первом туре участника, занявшего на нём i-е место, в третьей аналогично выведите N целых чисел, соответствующих расстановке баллов во втором туре. Числа в строках разделяйте пробелами.
Никакие два участника не должны получить одинаковые баллы в одном и том же туре. Если существует несколько способов расставить баллы требуемым образом, выведите любой.
3 1 2 1 3 3 1 2
Possible 3 2 1 3 2 1
3 1 2 3 1 3 1 2
Impossible
5 3 2 3 4 5 1 2 3 1 4 5
Possible 5 4 3 2 1 400 399 398 2 1