Темы
Информатика(2656 задач)
--->
228 задач
<---
В этой задаче Вася готовится к олимпиаде. Учитель дал ему 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
Вася заасфальтировал один прямоугольный треугольник, а Петя забетонировал другой прямоугольный треугольник. Катеты каждого из треугольников параллельны осям координат. Необходимо определить, забетонировал ли Петя хотя бы одну заасфальтированную точку.
Вам даны 8 целых чисел: x1, y1, a1, b1, x2, y2, a2, b2, где (x1, y1) - координаты прямого угла первого треугольника, а остальные две вершины имеют координаты (x1 + a1, y1) и (x1, y1 + b1). Аналогично, (x2, y2) - координаты прямого угла второго треугольника, а остальные две вершины имеют координаты (x2 + a2, y2) и (x2, y2 + b2). Каждое число по модулю не превосходит 109 и может быть равно нулю.
Выведите YES, если Петя забетонировал хотя бы одну заасфальтированную точку, и NO в противном случае.
3 3 1 1 3 3 -2 -2
YES
3 4 7 -4 6 6 -20 1
NO
Однажды, разбирая старые книги на чердаке, школьник Вася нашёл англо-латинский словарь. Английский он к тому времени знал в совершенстве, и его мечтой было изучить латынь. Поэтому попавшийся словарь был как раз кстати.
К сожалению, для полноценного изучения языка недостаточно только одного словаря: кроме англо-латинского необходим латинско-английский. За неимением лучшего он решил сделать второй словарь из первого.
Как известно, словарь состоит из переводимых слов, к каждому из которых приводится несколько слов-переводов. Для каждого латинского слова, встречающегося где-либо в словаре, Вася предлагает найти все его переводы (то есть все английские слова, для которых наше латинское встречалось в его списке переводов), и считать их и только их переводами этого латинского слова.
Помогите Васе выполнить работу по созданию латинско-английского словаря из англо-латинского.
В первой строке содержится единственное целое число N — количество английских слов в словаре. Далее следует N описаний. Каждое описание содержится в отдельной строке, в которой записано сначала английское слово, затем отделённый пробелами дефис (символ номер 45), затем разделённые запятыми с пробелами переводы этого английского слова на латинский. Переводы отсортированы в лексикографическом порядке. Порядок следования английских слов в словаре также лексикографический.
Все слова состоят только из маленьких латинских букв, длина каждого слова не превосходит 15 символов. Общее количество слов на входе не превышает 100 000.
Выведите соответствующий данному латинско-английский словарь, в точности соблюдая формат входных данных. В частности, первым должен идти перевод лексикографически минимального латинского слова, далее — второго в этом порядке и т.д. Внутри перевода английские слова должны быть также отсортированы лексикографически.
«Лексикографический порядок» означает, что слова идут по алфавиту. Иначе говоря, если у двух слов A и B несколько первых символов совпадают, то раньше идет то, у которого первая буква после общей части идет в алфавите раньше (например, слова solution и solve идут именно в таком порядке, так как первые 3 буквы в этих словах совпадают, а 4-я буква u в слове solution идет по алфавиту раньше буквы v слова solve). Если слово A является началом слова B, то раньше идет слово A (например, сначала идет слово school, а затем слово schoolboy).
3 apple - malum, pomum, popula fruit - baca, bacca, popum punishment - malum, multa
7 baca - fruit bacca - fruit malum - apple, punishment multa - punishment pomum - apple popula - apple popum - fruit