Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 3 4 5 6 7 >> Отображать по:
#1
Коровы - в стойла
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке вводятся числа \(N\) \((2 \lt N \lt 10001)\) – количество стойл и \(K\) (\(1 \lt K \lt N )\) – количество коров. Во второй строке задаются \(N\) натуральных чисел в порядке возрастания – координаты стойл (координаты не превосходят \(10^9\))

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

Выведите одно число – наибольшее возможное допустимое расстояние.

Примеры
Входные данные
6 3
2 5 7 11 15 20
Выходные данные
9
#2
Приближенный двоичный поиск
  

Реализуйте алгоритм приближенного бинарного поиска.

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

В первой строке входных данных содержатся числа \(N\) и \(K\) (\(0 \lt N,\,K \lt 100\,001\)). Во второй строке задаются \(N\) чисел первого массива, отсортированного по неубыванию, а в третьей строке – \(K\) чисел второго массива. Каждое число в обоих массивах по модулю не превосходит \(2\cdot10^9\).

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

Для каждого из \(K\) чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.

Примеры
Входные данные
5 5
1 3 5 7 9 
2 4 8 1 6
Выходные данные
1
3
7
1
5
#3
Сложность двоичного поиска
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Вводится одно число N

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

Выведите наименьшее количество вопросов, которого гарантированно хватит Пете, чтобы угадать Васино число.

Примеры
Входные данные
5
Выходные данные
3
#4
Двоичный поиск
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

Реализуйте алгоритм бинарного поиска.

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

В первой строке входных данных содержатся натуральные числа \(N\) и \(K\) (\(0 \lt N, K \le 100\,000\)). Во второй строке задаются \(N\) элементов первого массива, отсортированного по возрастанию, а в третьей строке – \(K\) элементов второго массива. Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит 109

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

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

Примеры
Входные данные
10 5
1 2 3 4 5 6 7 8 9 10 
-2 0 4 9 12
Выходные данные
NO
NO
YES
YES
NO
#5
Дейкстра
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой.

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

В первой строке содержатся три числа: N, S и F (1≤ N≤ 100, 1≤ S, F≤ N), где N – количество вершин графа, S – начальная вершина, а F – конечная. В следующих N строках вводится по N чисел, не превосходящих 100, – матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы записаны нули.

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

Требуется вывести искомое расстояние или -1, если пути между указанными вершинами не существует.

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