Турнир Архимеда(52 задач)
Кировские командные турниры(8 задач)
Барнаульские командные турниры(10 задач)
Московская командная олимпиада(246 задач)
Командные чемпионаты школьников Санкт-Петербурга по программированию(167 задач)
ВКОШП(180 задач)
В этой задаче Вася готовится к олимпиаде. Учитель дал ему N (1 ≤ N ≤ 100) задач для тренировки. Для каждой из этих задач известно, каким умением ai нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения i-й задачи Васино умение увеличивается на число bi.
Исходное умение Васи равно A. Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения?
Сначала вводятся два целых числа N, A (1 ≤ N ≤ 100, 0 ≤ A ≤ 100) — количество задач и исходное умение. Далее идут N пар целых чисел ai, bi (1 ≤ ai ≤ 100, 1 ≤ bi ≤ 100) — соответственно сколько умения нужно для решения i-й задачи и сколько умения прибавится после её решения.
Выведите одно число — максимальное количество задач, которое Вася может решить.
В первом тесте Вася сможет решить все задачи, выбрав, например, порядок 2, 1, 3. Во втором тесте ему необходимо сначала разобраться с 1 и 3 задачами, после чего он осилит 2.
3 2 3 1 2 1 1 1
3
4 1 1 10 21 5 1 10 100 100
3
Директор школы «Лицей Программистов» города Линейска сумел привить ученикам этой школы хорошую дисциплину, но, несмотря на это, многие ученики продолжают опаздывать на уроки.
В Линейске есть всего одна главная улица, на которой расположен и сам лицей, и живут все его ученики. Дисциплинированные школьники выходят из своих домов в одно и то же время. Но, к сожалению, все они живут на разном расстоянии от школы и добираются с разной, но постоянной скоростью (среди учеников есть как весьма неторопливые, так и будущая чемпионка мира по бегу на 100 метров Маша Гайка).
Для улучшения ситуации с опозданиями школа купила один веломобиль, который взялся водить сторож школы. Веломобиль способен помимо водителя перевозить одного школьника. Веломобиль перемещается с постоянной скоростью \(v\).
Ночь веломобиль проводит в школьном гараже, а утром, ровно в тот момент, когда все ученики выходят из своих домов, отправляется им навстречу, чтобы подвезти какого-нибудь школьника. Конечно же, ему приходится подвозить школьника прямо до ворот школы, потому как никто не хочет быть высаженным посреди пути. После того, как веломобиль помог одному ученику быстрее добраться в учебное заведение, он снова может ехать навстречу следующему опаздывающему человеку.
Директор хочет начинать занятия как можно раньше, но для этого нужно, чтобы все ученики добрались до лицея. Он поручил вам помочь составить план, по которому должен действовать водитель веломобиля, чтобы время прибытия последнего школьника в школу было минимальным.
Первая строка входного файла содержит два целых числа \(n, v\) (\(1 \le n \le 10^5\), \(1 \le v \le 1000\)) — соответственно количество людей и скорость веломобиля. Следующие \(n\) строк содержат по два целых числа \(x_i, v_i\) (\(1 \le x_i, v_i \le 1000\)) — расстояния от школы до дома \(i\)-ого ученика и его скорость.
В первую строку выходного файла выведите вещественное число \(t\) — минимальное время, за которое все школьники доберутся до лицея. Во второй строке выходного файла выведите единственное число \(k\) — количество учеников, которых нужно подвезти. В следующих \(k\) строках выведите по два числа — номер школьника, которого нужно подвезти, и расстояние от школы, на котором этот школьник должен сесть в веломобиль.
Школьников нужно выводить в том же порядке, в котором они будут ехать на веломобиле.
Выводите все вещественные числа как можно точнее. При проверке вашего решения при сравнении вещественных чисел будет допускаться абсолютная или относительная погрешность \(10^{-6}\).
Пример5 4 1 1 4 2 3 1 7 5 5 1 | 2.400000000 2 5 4.000000000 3 0.800000000 |
Напомним, что числами Фибоначчи называется последовательность чисел, получаемая по следующему правилу: f0 = f1 = 1, fk = fk - 1 + fk - 2, где k > 1.
Фибоначчиева система счисления (ФСС) — это позиционная система счисления с алфавитом, состоящим из двух цифр: 0 и 1, а ее базисом является последовательность чисел Фибоначчи 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … (f0 = 1 в базис не включается). В фибоначчиевой системе, как и во всех позиционных системах счисления, «вес» каждого разряда определяется соответствующим элементом базиса этой системы. Так, 10011fib = 1 × 8 + 0 × 5 + 0 × 3 + 1 × 2 + 1 × 1 = 11. Если не наложить дополнительных ограничений, то представление чисел в такой системе счисления оказывается неоднозначным.
Например, 1110 = 1111fib = 10011fib = 10100fib
Однако, нетрудно доказать, что существует единственное представление данного числа в фибоначчиевой системе счисления, которое не содержит двух единиц подряд. Такое представление называется каноническим. Требуется написать программу, которая для натурального числа N будет выводить его каноническое представление в ФСС.
Во входном файле записано единственное число N (1 ≤ N ≤ 2· 109).
Единственная строка выходного файла должна содержать искомое представление.
5
1000
11
10100
Вася очень любит различные игры: шашки, шахматы, домино, крестики-нолики и т. д. Поскольку он играет в них уже достаточно давно, он успел изучить эти игры достаточно хорошо, и они стали скучными. Поэтому он теперь изобретает новые игры на основе тех, в которые уже наигрался. Недавно он изобрел игру «Доминошахматы».
Она состоит в следующем: Вася берет у дедушки большой кусок фанеры и раскрашивает его так, что у него получается шахматная доска размера N × M клеточек. Потом он берет кости домино и пытается покрыть ими полученную доску так, чтобы все клеточки были закрыты, не было наложений и никакие доминошки не торчали за края доски (каждая доминошка покрывает две соседние клетки).
Поскольку Вася не спрашивает разрешения у дедушки прежде, чем взять доску, он иногда берет ненужные доски, а иногда и те, которые дедушка хотел использовать в строительстве новой дачи. Как раз сегодня Вася взял «нужную» доску, поэтому дедушка был вынужден вырезать из Васиной доски два квадрата по одной клеточке.
Вася сначала огорчился, что не сможет поиграть в свою игру. А потом решил попробовать замостить доску с уже вырезанными клетками, причем так, чтобы вырезанные клетки не были накрыты доминошками.
Помогите Васе понять, можно ли это сделать.
В первой строке входных данных записаны числа N и M — размеры доски (1 ≤ N ≤ 200, 1 ≤ M ≤ 200, N·M > 2).
Во второй строке вводятся через пробел два целых числа — координаты x1 и y1 первой вырезанной клетки (1 ≤ x1 ≤ N, 1 ≤ y1 ≤ M).
В третьей строке вводятся через пробел два целых числа — координаты x2 и y2 второй вырезанной клетки (1 ≤ x2 ≤ N, 1 ≤ y2 ≤ M).
Первая и вторая клетки не совпадают.
Выведите «YES», если доску с вырезанными клеточками можно покрыть доминошками, и «NO» в противном случае. (Запас доминошек у Васи бесконечный.)
2 2 1 1 2 2
NO
2 2 1 1 1 2
YES