Темы --> Информатика --> Алгоритмы --> Алгоритмы поиска --> Бинарный поиск --> Бинарный поиск по ответу
---> 56 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
#2967
Когда корень не равен корню
  

Найдите наименьшее натуральное число x, такое что math.sqrt(x*x) != x.

(Предполагается, что вы используете python3!)

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

отсутствует

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

Одно натуральное число.

#2969
Дракон
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В королевстве Флатландия наступили тяжелые времена. В пещерах неподалеку от столицы поселился ужасный Черный Дракон. Каждую ночь он выползал на охоту. Много людей погубил он, много построек уничтожил.

Король Флатландии понял, что дальше так продолжаться не может, и нанял отважного Рыцаря, чтобы тот победил рептилию.

Рыцарь принял предложение Короля и начал готовиться к битве. Сам он участия в битве принимать не желал (не рыцарское это дело –– мечом махать), поэтому решил собрать войско из копейщиков. Но копейщикам надо платить, а у Рыцаря из-за кризиса осталось совсем немного сбережений. Помогите ему определить минимальное число копейщиков, необходимое для победы над Черным Драконом.

У копейщика и у дракона есть два параметра: количество очков здоровья и наносимый противнику урон.

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

Требуется написать программу, которая определяет минимальное количество копейщиков, которое необходимо нанять Рыцарю, чтобы победить Черного Дракона.

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

Вводятся четыре натуральных числа через пробел: Hd, Dd, hp, dp –– количество очков здоровья дракона, урон, наносимый драконом, количество очков здоровья одного копейщика и урон, наносимый одним копейщиком. Все числа положительные и не превосходят 109.

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

Выведите на экран одно целое число –– минимальное число копейщиков, необходимое для победы над драконом.

Примеры
Входные данные
500 50 10 10
Выходные данные
20
Входные данные
500 28 10 10
Выходные данные
15
#3334
Проходной балл
  

Одна Очень Престижная Олимпиада, как и все престижные олимпиады в последнее время, состоит из двух туров - регионального и заключительного. Правила отбора во второй тур (заключительный этап) просты:

  1. Призеры олимпиады прошлого года приглашаются на заключительный этап вне зависимости от набранных ими в первом туре баллов.
  2. Все участники, набравшие не меньше баллов, чем установленный жюри проходной балл, проходят во второй тур.
  3. Если в каком-либо из регионов ни один участник по первым двум правилам во второй тур не прошел, то на заключительный этап приглашается участник из этого региона, набравший в нем максимальное количество баллов (это не касается регионов, от которых участников не было).
  4. На второй тур можно пригласить не более \(M\) участников.

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

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

В первой строке входного файла содержатся три целых числа \(N\), \(M\) и \(R\) - число участников первого тура, максимально возможное число участников второго тура и число регионов, из которых могли быть участники (\(1 \le M < N\)). Далее в \(N\) строках содержатся результаты каждого из участников. Каждая строка состоит из четырех целых чисел. Сначала идет \(id\) - уникальный идентификатор участника (\(1 \le id \le N\)), далее номер региона \(region\), в котором данный участник учится (\(1 \le region \le R\)), затем \(score\) - число баллов, набранных участником, четвертое число равно 1, если участник является призером олимпиады прошлого года, и 0 - в противном случае.

Гарантируется, что все идентификаторы участников различны, никакие два участника не набрали одинаковое число баллов, и выполнить все правила отбора возможно.

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

Выведите одно число - минимальный проходной балл, который можно установить.

Примечания

Тесты состоят из четырёх групп. Во всех тестах \(0 \le score \le 10^9\).

  1. Тест 1 из условия, оценивается в 0 баллов.
  2. В тестах этой группы все числа на входе не превосходят 1000. Эта группа оценивается в 30 баллов, при этом баллы начисляются только при прохождении всех тестов группы.
  3. В тестах этой группы \(1 \le R \le M \le 10\,000\), \(M < N \le 100\,000\). Эта группа также оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. В тестах этой группы, \(1 \le R \le M < N \le 100\,000\). Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Каждый из тестов оценивается независимо от других.
Примеры
Входные данные
9 6 5
6 1 799 0
2 4 995 0
1 4 989 1
7 2 538 0
5 4 984 0
8 2 1000 0
3 2 998 0
4 2 823 1
9 1 543 0
Выходные данные
985
#3380
Лифт
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Высокое здание, состоящее из \(N\) этажей, оснащено только одним лифтом. Парковка находится ниже фундамента здания, что соответствует одному этажу ниже первого. Этажи пронумерованы от \(1\) до \(N\) снизу вверх. Про каждый этаж известно количество человек, желающих спуститься на лифте на парковку. Пусть для i-го этажа эта величина равна \(A_i\). Известно, что лифт не может перевозить более \(C\) человек единовременно, а также то, что на преодоление расстояния в один этаж (не важно вверх или вниз) ему требуется \(P\) секунд. Какое наибольшее количество человек лифт может перевезти на парковку за \(T\) секунд, если изначально он находится на уровне парковки?

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

В первой строке входного файла содержатся целые числа \(N\), \(C\), \(P\), \(T\) (\(1 \leq N \leq 100\), \(1 \leq C \leq 10^9\), \(1 \leq P \leq 10^9\), \(1 \leq T \leq 10^9\)). Вторая строка содержит последовательность \(N\)  целых чисел \(A_1\), \(A_2\), ..., \(A_N\) (\(0 \leq A_i \leq 10^9\)). Сумма всех значений последовательности не превосходит \(10^9\).

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

Выведите наибольшее количество человек, которое лифт успеет перевезти на парковку.

Примеры
Входные данные
4 5 2 15
0 1 2 3
Выходные данные
3
Входные данные
4 5 2 18
0 1 2 3
Выходные данные
5
Входные данные
3 2 1 9
1 1 1
Выходные данные
3
#3381
Коровники
  

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

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

В первой строке входного файла содержатся два числа \(n\) и \(k\) (\(2 \le n \le 50\;000\), \(1 \le k \le n\)) --- количество лужаек и планируемое число коровников, соответственно. Следующие \(n - 1\) строк содержат описания дорожек. Каждая дорожка задается парой целых положительных чисел (\(a, \, b\)), где \(a\) и \(b\) --- номера лужаек, которые соединяет данная дорожка. Лужайки нумеруются с единицы.

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

В первой строке входного файла выведите \(l\) --- максимальное количество дорожек, по которым придется пройти корове, чтобы попасть в коровник. Во второй строке выведите \(k\) различных целых чисел --- номера лужаек, на которых следует построить коровники. Если оптимальных решений несколько, разрешается вывести любое из них.

Примеры
Входные данные
7 2
5 4
4 3
1 3
2 3
4 6
6 7
Выходные данные
2
1 4
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест