Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 32967. Лучшее место
Темы: Бинарный поиск    Сканирующая прямая   

В зале ожидания на вокзале стоят N рядов из M кресел. Чтобы ожидающие не скучали, вместо некоторых кресел установлено K мощных Wi-Fi роутеров. Ожидающие стараются занять места ближе к роутерам, так как тогда они смогут смотреть ролики с Youtube или VK с более высоким разрешением, без задержек. Если пассажир сидит на месте с номером c в ряде r, а i-й роутер расположен на месте Ci в ряде Ri, то расстояние до i-го роутера вычисляется как max(|r−Ri|,|c−Ci|), где |x| – абсолютное значение x. Креслам в зале ожидания был присвоен приоритет от 1 до N⋅M−K, меньшие номера получили кресла с меньшим расстоянием до ближайшего роутера, среди кресел с одинаковым расстоянием до роутеров более удобными считаются кресла, стоящие в ряду с меньшим номером, а среди них — с меньшим номером места в ряду. На рисунке показан приоритет кресел в зале ожидания с 4 рядами из 7 кресел, в котором установлены 2 роутера (их позиции помечены черным цветом). Темно-серым цветом выделены кресла, стоящие на расстоянии 1 от роутеров, светло-серым — на расстоянии 2, белым — 3.
 

Напишите программу, которая вычисляет расстояние до ближайшего роутера от кресла с некоторым заданным приоритетом.

Первая строка ввода содержит четыре целых чисел — количество рядов N (2 ≤ N ≤ 109) и мест в ряду M (2 ≤ M ≤ 109), количество роутеров K (1 ≤ K ≤ 100, K < N⋅M), количество запросов Q (1 ≤ Q ≤ 100). Далее следует K строк, содержащих два целых числа — местонахождение роутеров: номер ряда Ri (1 ≤ Ri ≤ N) и номер места в ряду Ci (1 ≤ Сi ≤ M). Среди них нет совпадающих. Далее следует строка, содержащая Q целых чисел в диапазоне от 1 до N⋅M−K – приоритеты кресел.

Вывести для каждого запроса на отдельной строке одно целое число — расстояние до ближайшего роутера от кресла с заданным приоритетом.
 
Ввод Вывод
4 7 2 4
2 5
4 4
1 6 16 26
1
1
2
3

ID 33009. Сложность двоичного поиска
Темы: Бинарный поиск   

Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число?
 
Входные данные
Вводится одно число N
 
Выходные данные
Выведите наименьшее количество вопросов, которого гарантированно хватит Пете, чтобы угадать Васино число.
 
Ввод Вывод
5 3

ID 34879. K-квест
Темы: Бинарный поиск    Быстрая сортировка   

В одной из компьютерных игр-квестов есть следующее задание. На карте игрового мира размещены N персонажей, с каждым из которых может встретиться игрок. От общения с i-м персонажем карма игрока меняется на величину ai, которая может быть как положительной, так отрицательной или даже нулем.

Изначально карма игрока равна нулю. Для того чтобы пройти на следующий уровень, нужно чтобы карма была в точности равна значению K, при этом карма также может принимать как положительные, так и отрицательные значения.

Комнаты, в которых находятся персонажи, соединены односторонними магическими порталами, поэтому игроку придется встречать персонажей в определенной последовательности: после персонажа номер i он попадает к персонажу номер i + 1, затем к персонажу номер i + 2, и т.д. В комнате последнего персонажа с номером N портала к другому персонажу нет.

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

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

Входные данные
В первой строке входных данных записаны два числа: количество персонажей N и необходимый уровень кармы K (|K| ≤ 109, K ≠ 0). Во второй строке через пробел записаны N целых чисел a1, a2, ..., aN — величины, на которые меняется карма героя после общения с персонажами с номерами 1, 2, ..., N соответственно.

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

Ввод Вывод
5 3
-2 2 -1 2 4
2 4
7 1
1 -1 1 -1 1 -1 2
5 5
4 3
2 2 2 2
-1

 

ID 28311. Ближайшее число
Темы: Бинарный поиск   

Напишите программу, которая находит в массиве элемент, самый близкий по величине к данному числу.
 
Входные данные:
- в первой строке задается одно натуральное число N, не превосходящее 1000 – размер массива;
- во второй строке содержатся N чисел – элементы массива (целые числа, не превосходящие по модулю 1000);
- в третьей строке вводится одно целое число x, не превосходящее по модулю 1000.
 
Выходные данные: вывести значение элемента массива, ближайшее к x. Если таких чисел несколько, выведите любое из них.
 
Примеры
Входные данные Выходные данные
1
5
1 2 3 4 5
6
5
2
5
5 4 3 2 1
3
3

ID 27279. Приближенный двоичный поиск
Темы: Бинарный поиск   

Реализуйте алгоритм приближенного бинарного поиска.
 
Входные данные:
- в первой строке входных данных содержатся числа N и K (\(0< N,\ K <100001\));
- во второй строке задаются N чисел первого массива, отсортированного по неубыванию; 
- в третьей строке вводится K чисел второго массива.
Каждое число в обоих массивах по модулю не превосходит \(2 \cdot 10^9\).
 
Выходные данные: для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.
 
Примеры
Входные данные Выходные данные
1
5 5
1 3 5 7 9 
2 4 8 1 6 
1
3
7
1
5

ID 38466. Agar.io
Темы: Бинарный поиск   

В многопользовательской игре Agar.io игроки управляют бактериями. У каждой бактерии есть размер — целое положительное число. Если встречаются две бактерии разного размера, то бактерия большего размера поглощает меньшую бактерию. При этом меньшая бактерия исчезает, а размер большей бактерии увеличивается на размер меньшей бактерии. Если встречаются две бактерии равного размера, то ничего не происходит. Побеждает игрок, чья бактерия останется на игровом
поле одна.
В игре участвуют n игроков, вам даны размеры их бактерий. Определите, какие из игроков имеют возможность выиграть в этой игре.

Формат входных данных
Программа получает на вход целое число n, 1 ≤ n ≤ 105 — количество игроков. Следующие n строк содержат по одному числу ai — размеры бактерий, 1 ≤ ai ≤ 109. Числа ai заданы в порядке неубывания.
Формат выходных данных
Программа должна вывести n чисел равных «0» или «1», по одному числу в строке. Если i-е число равно 0, то это означает, что i-й игрок (размер бактерии которого первоначально был равен
ai) ни при каких обстоятельствах не может выиграть в этой игре. Если i-е число равно 1, то это означает, что i-й игрок имеет возможность выиграть в этой игре.

Примеры
Входные данные Выходные данные Пояснение
1 4
1
1
3
4
0
0
1
1
В примере из условия 4 бактерии размерами 1, 1, 3, 4. Бактерии размером 1 никого не могут
съесть, поэтому не могут выиграть. Бактерия размером 4 может съесть всех. Бактерия размером 3
может съесть по очереди две бактерии размером 1. Тогда её размер станет 5, после этого она сможет
съесть бактерию размером 4 и выиграть. Ответ: 0, 0, 1, 1.

ID 39381. Гармоничная последовательность
Темы: Бинарный поиск    Префиксные суммы(минимумы, ...)   

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел \(a_1, a_2, ..., a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Например, последовательность [1,2,1,–1]  является гармоничной, поскольку 2=1+1, и 1=2+(–1) .

Рассмотрим последовательности равной длины: \(A=[a_1,a_2, ... a_n]\)   и \(B=[b_1,b_2, ... b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\) . Например, \(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2|++|1–0|+|–1–0|=0+0+1+1=2 \)

В конце лекции профессор написал на доске последовательность из n целых чисел \(B=[b_1,b_2, ... b_n]\)и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A=[a_1,a_2, ... a_n]\), такую, что \(d(A, B)\) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A,B)\) .

Требуется написать программу, которая по заданной последовательности B определяет, на каком минимальном расстоянии от последовательности B найдется гармоничная последовательность A.

Входные данные
Первая строка входного файла содержит целое число n – количество элементов в последовательности ( \(3 \le n \le 300 000\)).

Вторая строка содержит n целых чисел \(b_1, b_2, …, b_n (–10^9 \le b_i \le 10^9 )\) .

Выходные данные
Выходной файл должна содержать одно целое число: минимальное возможное расстояние от последовательности во входном файле до гармоничной последовательности.

Примеры
Входные данные Выходные данные
1 4
1 2 0 0
2

ID 39795. Поиск вершины по центру описанной окружности (O)
Темы: Бинарный поиск    Элементарная геометрия    Вычислительная геометрия   

Точка O – центр описанной окружности треугольника АВС.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D, E
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10-5.
Пример:

Входные данные Выходные данные
1 1 6 3 7 1 0 6  3.784
1 2 5 1 6 -1 1 5 3.207692

ID 39818. Поиск вершины по центру вписанной окружности (I, инцентр)
Темы: Бинарный поиск    Элементарная геометрия    Вычислительная геометрия   

Точка I – центр вписанной окружности треугольника АВС (инцентр).
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D, E
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10-5.
Пример:

Входные данные Выходные данные
1 1 7 3 8 1 1 7 4.348182
-1 3 9 1 8 -1 -1 1  6.500895

ID 39774. Поиск вершины по ортоцентру (H)
Темы: Бинарный поиск    Элементарная геометрия    Вычислительная геометрия   

Точка H – центр пересечения высот треугольника (ортоцентр) АВС.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D, E
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10-5.
Пример:

Входные данные Выходные данные
1 1 6 3 9 1 1 5 2.454545
1 2 5 1 6 -1 1 5 3.196078

ID 39757. Треугольник. Поиск вершины по положению центроида
Темы: Бинарный поиск    Элементарная геометрия    Вычислительная геометрия   

Точка G – центр пересечения медиан треугольника (центроид) АВС.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;

- координата точки D, лежащей на прямой ВС;
- точка G лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D

Все значения целые числа в интервале [-1000;1000].

Выходные данные: ответ на задание с точностью не менее 10-5.
Пример:

Входные данные Выходные данные
2 2 7 1 6 3 3 4 3.6
0 0 5 1 3 4 0 0 1.0

ID 40065. Описанный четырехугольник
Темы: Бинарный поиск    Вычислительная геометрия   

Известно, что вокруг выпуклого четырехугольника ABCD можно описать окружность.
Найдите площадь четырехугольника ABCD, если известно:
- координаты точек A, B, C;
- точка D принадлежит отрезку EF
Входные данные:
-в 1-й строке вводятся значения Ax, Ay, Bx, By Cx,Cy – координаты точек A, B, C
-в 2-й строке вводятся значения Ex, Ey, Fx, Fy – координаты вершин отрезка  EF
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10-5.
Пример:

Входные данные Выходные данные
1 2 8 1 10 5
5 8  14 11
36.0
3 2 4 6 9 1
5 1 0 0
15.797687719

ID 40066. Количество чисел на диапазоне
Темы: Префиксные суммы(минимумы, ...)    Бинарный поиск   

Вам даны N целых чисел A1, ..., AN.
На каждый из Q запросов, заданных в формате L R X, выведите количество элементов среди AL, ..., AR, значения которых равны X.

Входные данные
В первой строке задано целое число N (1 <= N <= 2·105). 
Вторая строка содержит целых чисел Ai (1 <= Ai <= N, 1 <= i <= N). 
В третьей строке задано одно целое число (1 <= Q <= 2·105).
Каждая из следующих строк содержит три целых числа L, R, (1 <= L <= R <= N, 1 <= X <= N).

Выходные данные
Выведите на экран строк, i-я строка содержит ответ на i-й запрос.
 

Примеры
Входные данные Выходные данные
1
5
3 1 4 1 5
4
1 5 1
2 4 3
1 5 2
1 3 3
2
0
0
1

ID 40069. Кардиоида
Темы: Бинарный поиск    Вычислительная геометрия   

Кардиоида-- плоская алгебраическая кривая 4-го порядка, которая описывается фиксированной точкой окружности радиуса , катящейся по неподвижной окружности с таким же радиусом

В прямоугольной декартовой системе координат уравнение кривой имеет вид:

Найдите координаты точки пересечения кардиоиды и отрезка EF, если известно:
- коэффициент кардиоиды a;
- координаты вершин отрезка EF;
гарантируеся, что одна из вершин отрезка лежит внутри кардиоиды, а другая снаружи.
Рассмотрим функцию F(x,y,a)= (x2+y2+2ax)2-4a2(x2+y2). Если для точки M с координатами (x,y) F(x,y,a)<0, то точка M лежит внутри кардиоды с параметром a. Если значение функции будет положительным, то точка M лежит снаружи.

Входные данные:
-в 1-й строке вводится вещественное число - значениe коэффициента кардиоды (по модулю не более 10)
-в 2-й строке вводятся целые значения Ex, Ey, Fx, Fy – координаты вершин отрезка  EF (числа в интервале [-1000;1000]).
Выходные данные:
1 строка  - абцисса точки пересечения (координата x), с точностью не менее 10-5 
2 строка  - ордината точки пересечения (координата y), с точностью не менее 10-5 

Пример:
Входные данные Выходные данные
1.0
-1 1 1 3
0
2
-2.5
10 4 1 1
8.91545419
3.63848473

ID 40068. Сфера и отрезок
Темы: Вычислительная геометрия    Бинарный поиск   

Найдите точку пересечения отрезка AB и сферы радиуса R, с центром в точке O . Все точки заданы декартовыми координатами в пространстве. Гарантируеся, что только одна из вершин отрезка расположена внутри сферы.
Входные данные
В 1-й строке вводятся числа чисел, разделённых пробелами. Вначале вводится радиус сферы R, затем  координаты центра сферы
 O (Ox,Oy,Oz).
В 2-й строке вводятся шесть чисел, разделённых пробелами. Вначале вводятся координаты точки A (Ax,Ay,Az),  затем координаты точки
B (Bx,By,Bz).
Выходные данные
Выводится три числа - координаты точки пересечения. Каждая координата в отдельной строке и с точностью не менее 10-6.
Пример 1:

Входные данные Выходные данные
10 0 0 0
7 6 5 2 4 6
6.37704215657
5.75081686263
5.12459156869
Пример 2:
Входные данные Выходные данные
8 1 -1 2
5 6 -5 2 -4 6
4.45729353069
4.19097843564
-3.0100762792

ID 40067. Эллипс и отрезок
Темы: Информатика    Бинарный поиск    Вычислительная геометрия   

Найдите координаты точки пересечения эллипса и отрезка, если известно:
- координаты точек фокусов эллипса A, B;
- R - сумма расстояний от точки эллипса до фокусов;
- координаты вершин отрезка EF;
гарантируеся, что одна из вершин отрезка лежит внутри эллипса, а другая снаружи
Входные данные:
-в 1-й строке вводятся значения Ax, Ay, Bx, By, R – координаты точек A, B и сумма расстояний R
-в 2-й строке вводятся значения Ex, Ey, Fx, Fy – координаты вершин отрезка  EF
Все значения целые числа в интервале [-1000;1000].
Выходные данные:
1 строка  - абцисса точки пересечения (координата x), с точностью не менее 10-5 
2 строка  - ордината точки пересечения (координата y), с точностью не менее 10-5 

Пример:

Входные данные Выходные данные
-10 3 -2 7 12
-14 -9 -8 6
-10
1
3 3 6 7 7
3 4 -1 7
1.7670862633
4.9246853025

ID 39863. Расстояние между отрезками - 3
Темы: Бинарный поиск    Бинарный поиск    Вычислительная геометрия   

Найдите расстояние между отрезками AB и CD. Отрезки заданы декартовыми координатами границ в пространстве.
Расстояние между отрезками - минимальное расстояние между точками X,Y, где \(X \in [A,B], \ Y\in[C,D]\).
Входные данные
В 1-й строке вводятся шесть чисел, разделённых пробелами. Вначале вводятся координаты точки A (Ax,Ay,Az),  затем координаты точки B (Bx,By,Bz).
В 2-й строке вводятся шесть чисел, разделённых пробелами. Вначале вводятся координаты точки C (Cx,Cy,Cz),  затем координаты точки D (Dx,Dy,Dz).
Выходные данные
Выводится одно число - расстояние между отрезками AB, CD.
Расстояние необходимо найти с точностью не менее 10-6.

Пример 1:

Входные данные Выходные данные
-7 8 6 -6 -5 8
-7 8 6 0 -8 9
0.0
Отрезки имеют общую точку, поэтому расстояние равно 0.0
Пример 2:
Входные данные Выходные данные
-10 -10 -8 10 7 9
-7 4 0 2 -8 -2
0.14477985167371404