Информатика

Примеры

1 1 10
2

9.0000

5 1 10
1 2 4 8 16

28.0000

Примеры

8 2 3
170
205
225
190
260
130
225
160

30

Дан массив из n чисел, отсортированный по невозрастанию, и k запросов. Для каждого запроса выведите минимальный номер элемента массива, меньший данного (нумерация элементов массива начинается с 1).

В первой строке входных данных содержатся числа n и k (0 < n, k <= 10⁵) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по невозрастанию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅10⁹ .

Для каждого из k запросов выведите минимальный номер элемента массива, меньше данного. Если таких нет, выведите 0.

Примеры

5 5
9 8 5 3 3
2 4 8 1 10

0
4
3
0
1

Дан массив из n чисел, отсортированный по невозрастанию, и k запросов. Для каждого запроса выведите максимальный номер элемента массива, не меньше данного (нумерация элементов массива начинается с 1).

В первой строке входных данных содержатся числа n и k (0 < n, k <= 10⁵) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по невозрастанию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅10⁹ .

Для каждого из k запросов выведите максимальный номер элемента массива, не меньше данного. Если таких нет, выведите 0.

Примеры

5 5
9 8 5 3 3
2 4 8 1 10

5
3
2
5
0

Дан массив из n чисел, отсортированный по невозрастанию, и k запросов. Для каждого запроса выведите максимальный номер элемента массива, большего данного (нумерация элементов массива начинается с 1).

В первой строке входных данных содержатся числа n и k (0 < n, k <= 10⁵) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по невозрастанию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅10⁹ .

Для каждого из k запросов выведите максимальный номер элемента массива, большего данного. Если таких нет, выведите 0.

Примеры

5 5
9 8 5 3 3
2 4 8 1 10

5
3
1
5
0

Дан массив из n чисел, отсортированный по неубыванию, и k запросов. Для каждого запроса выведите максимальный номер элемента массива, меньший данного (нумерация элементов массива начинается с 1).

В первой строке входных данных содержатся числа n и k (0 < n, k <= 10⁵) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по неубыванию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅10⁹ .

Для каждого из k запросов выведите максимальный номер элемента массива, меньший данного. Если таких нет, выведите 0.

Примеры

5 5
3 3 5 8 9
2 4 8 1 10

0
2
3
0
5

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

Вводится последовательность целых чисел, заканчивающаяся нулем. Сам ноль в последовательность не входит.

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

Примеры

7 3 2 1 9 5 4 6 8 0

1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1

Миша занимается параллельным программированием. Сегодня он пишет программу для исполнителя "Квадратик". Исполнитель "Квадратик" живет на клетчатом поле размера  N х M, размер одной клетки 1х1. Перемещаясь он закрашивает клетку, на которой побывал. Клетку, на которой он начал движение и на которой остановился он также закрашивает. 
Миша установил на поле K "Квадратиков". Каждый "Квадратик" будет двигаться в указанном Мишей направлении и останавливаться дойдя до конца поля. После окончании движения всех "Квадратиков", Миша хочет узнать сколько клеток поля получились закрашенными. Так как задача подсчета не относится к параллельному программированию, а размер поля может быть очень большим, Миша попросил вас написать программу для подсчета таких клеток.
 

Программа получает на вход несколько строк. Первая строка содержит целые числа M и N - размеры поля исполнителя "Квадратик" (1 <= M, N <= 10⁶). Во второй строке записано число K - количество "Квадратиков" на поле (0 <= K <= 10³). Далее идут K строк, каждая из которых описывает положение определенного "Квадратика" и направление, в котором он будет перемещаться. Формат каждой из таких строк: два целых числа, записанных через один пробел и один символ  {N, E, S, W} - начальные координаты и направление движения соответствующего "Квадратика". Символ отделен от чисел ровно одним пробелом. 
Символами обозначены следующие направления движения: N - вверх, S - вниз, W - влево, Е - вправо.

Выведите количество закрашенных клеток поля, после окончания движения всех "Квадратиков".


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

Примеры

8 5
4
4 4 S
6 2 W
6 3 N
6 4 S

13

Сегодня Максиму не повезло в игре в "Морской бой". Играя с соседом по парте, он ни разу не попал ни в один корабль противника. Игра продолжалась до тех пор, пока Марь Иванна не увидела, что ребята заняты на уроке не тем, чем надо.  Игру пришлось закончить досрочно победой соседа. Прийдя домой, Максим решил определить, какой максимальной длины корабль мог быть у противника. 
Но теперь его отвлекла мама и позвала ужинать. Он ушел ужинать и попросил вас помочь ему найти ответ. 

Морской бой представляет из себя игру на клетчатом поле размером 10 x 10 клеток. Максим успел прислать вам поле прошедшей игры. На поле отмечены клетки, в которые Максим уже стрелял. На поле можно размещать корабли любого размера, но обязательное условие, чтобы корабль был прямоугольным с шириной, равной 1. Располагать корабль разрешается либо горизонтально либо вертикально.

На вход программа получает 10 строк по 10 чисел в каждой, числа разделены пробелами. Число 1 означает, что в соответствующую клетку стреляли, число 0 – что в клетку не стреляли.
(Гарантируется, что на поле есть хотя бы одна небитая клетка.)

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

Примеры

0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 0 0 1 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 1 0 0 1 0 0 0
0 0 1 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0

10

Громила Ральф вот уже 30 лет живёт в игровом автомате, и вы его можете увидеть на экране того самого автомата. 
Сегодня Ральф гуляет по экрану, на котором отображается прямоугольное изображение, разбитое на N x N клеток. В каждой клетке находится тарелка с его любимыми блинчиками (на всех тарелках разное количество блинчиков). Ральф начинает перемещаться с левой нижней клетки прямоугольника. Съев все блинчики в текущей клетке, он перемещается на одну клетку вправо или на одну клетку вверх, всегда выбирая ту из клеток, где больше блинчиков в тарелке (за пределами прямоугольника тарелок с блинчиками нет). В конце концов Ральф приходит в правую верхнюю клетку. Вам же предстоит определить, сколко всего блинчиков съел Ральф пока путешествовал по экрану. Блинчики в начальной и конечной клетках Ральф тоже съел с большим удовольствием.

Программа получает на вход в первой строке целое число N – размер изображения (2 <= N <= 10). В следующих N строках задаются через пробел числа, обозначающие количество блинчиков на тарелках, начиная с верхнего ряда и заканчивая нижним. Все числа – различные, натуральные, не превосходящие 100.

Выведите одно число - количество блинчиков, которое съест Ральф, добравшись до правой верхней клетки.

 

Примеры

2
37 82
23 52

157

Учащиеся театрального кружка школы любят посещать театр. В очередной раз они пошли в театр, в котором n рядов по m мест в каждом. Руководитель кружка пришла за билетами и хочет купить билеты всем учащимся в одном ряду на соседние места. 
По имеющейся информации о проданных билетах на спектакль определите, сможет ли руководитель купить билеты всем учащимся и себе в одном ряду. 
Информация о проданных билетах записана в двумерный массив (единицы означают, что на данное место билет продан, ноль - что место свободно). Руководителю кружка вместе с детьми необходимо k билетов.

В первой строке входных данных находятся числа n, m, k <= 100. В следующих n строках входных данных расположены по m чисел (0 и 1), разделенных пробелами.

Выведите YES или NO в зависимости от ответа на вопрос задачи.

Примеры

3 4 2
0 1 0 1
1 0 0 1
1 1 1 1

YES

Дан массив a из n целых чисел a1, a2,..., an. Научитесь быстро отвечать на запросы «Сколько чисел имеют значения от l до r»?

В первой строке находится целое число n (1<=n<=10⁵) — длина массива. Во второй строке находятся n целых чисел a1, a2,..., an (−10⁹<=ai<=10⁹). В третьей строке находится целое число k (1<=k<=10⁵) — число запросов. В следующих k строках находятся пары чисел l r (−10⁹<=l<=r<=10⁹).

Выведите k чисел (каждое в отдельной строке) - ответы на запросы.

Примеры

5
10 1 10 3 4
4
1 10
2 9
3 4
2 2

5
2
2
0 

Дан массив из n чисел, отсортированный по неубыванию, и k запросов. Для каждого запроса выведите максимальный номер элемента массива, не большего данного (нумерация элементов массива начинается с 1).

В первой строке входных данных содержатся числа n и k (0 < n, k <= 10⁵) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по неубыванию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅10⁹ .

Для каждого из k запросов выведите максимальный номер элемента массива, не большего данного. Если таких нет, выведите 0.

Примеры

5 5
3 3 5 8 9
2 4 8 1 10

0
2
4
0
5

Дан массив из n чисел, отсортированный по неубыванию, и k запросов. Для каждого запроса выведите минимальный номер элемента массива, не меньшего данного (нумерация элементов массива начинается с 1).

В первой строке входных данных содержатся числа n и k (0 < n,k <= 10⁵) - длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по неубыванию. В третьей строке содержатся k запросов. Все элементы массива и запросы - целые числа, каждое из которых по модулю не превосходит 2·10⁹ .

Для каждого из k запросов выведите минимальный номер элемента массива, не меньшего данного. Если таких нет, выведите n+1.

Примеры

5 5
3 3 5 8 9
2 4 8 1 10

1
3
4
1
6

Громозека и Алиса придумали правила игры в бесконечную Дженгу.
В бесконченой Дженге каждый ход заключается в одном из двух действий на выбор игрока:

• если в башне есть хотя бы один брусок, то можно вытащить и убрать из башни ровно один брусок (количество брусков в башне уменьшается на 1);
• поставить на башню количество брусков на 1 больше, чем ставили в последний раз перед этим.

Например, можно выполнить такую последовательность действий при игре:

После 9 ходов, количество брусокв в башне в итоге будет равно 11, а по ходу игры из башни извлекли 4 бруска.

Известно, что Алиса и Громозека сделали n ходов в придуманной игре, при этом после всех выполненных ходов, количество брусков в башне равнялось k. Найдите суммарное количество убранных Алисой и Громозекой с башни брусков за все n ходов. Гарантируется, что для заданных n и k ответ существует.

В первой строке входных данных заданы два целых числа n и k (1<=n<=10⁹; 0<=k<=10⁹) - суммарное количество ходов и количество брусков в башне после n ходов. Гарантируется, что для заданных n и k ответ существует.

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

Примеры

1 1

0

9 11

4

5 0

3

3 2

1

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

В первой строке вводится одно натуральное число N, не превосходящее 10⁵: количество чисел в массиве.

Во второй строке вводятся N натуральных чисел, не превосходящих 10⁹, каждое следующее не меньше прелылущего.

В третьей строке вводится количество искомых чисел M - натуральное число, не превосходящее 10⁶.

В четвертой строке вводится M натуральных чисел, не превосходящих 10⁹.

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

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

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

Примеры

4
1 2 2 3
4
4 3 2 1

0 0
4 4
2 3
1 1

Яркости пикселей рисунка закодированы числами от 0 до 255 в виде матрицы. Преобразовать рисунок в черно-белый по следующему алгоритму:

1. вычислить среднюю яркость пикселей по всему рисунку
2. все пиксели, яркость которых меньше средней, сделать черными (записать код 0), а остальные -– белыми (код 255)

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

В первой строке записаны через пробел размеры матрицы: количество строк N и количество столбцов M ( 1 <= N , M <= 100 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел в диапазоне от 0 до 255, разделённых пробелами.
 

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

Примеры

4 4
12 14 67 45
32 87 45 63
69 45 14 11
40 12 35 15

37.8750
0 0 255 255
0 255 255 255
255 255 0 0
255 0 0 0

Седловая точка – это элемент матрицы, который одновременно является наибольшим в своем столбце и наименьшим в своей строке. Напишите программу, которая находит индексы всех седловых точек матрицы. Нумерация строк и столбцов матрицы начинается с единицы.

В первой строке записаны через пробел размеры прямоугольной матрицы N и N (количество строк и количество столбцов, 1  <= N, M <=  100). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами.
 

Программа должна вывести индексы всех седловых точек матрицы в порядке обхода по строкам (сверху вниз, слева направо). Номер строки и номер столбца каждой седловой точки разделяются пробелами. Нумерация начинается с единицы. Если в матрице нет ни одной седловой точки, нужно вывести число 0.

Примеры

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
9 17 18 19 20

3 1

Создайте двумерный массив размером n×m и заполните его натуральными числами от 1 до nxm по вертикали (см. пример).

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

Даны два натуральных числа: n и m, не превышающие 10¹⁰.

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

Выведите заполненный двумерный массив

 

Примеры

3 4

1 4 7 10 
2 5 8 11 
3 6 9 12