Информатика

Даны два массива arr1 и arr2. Элементы массива arr2 различны, и при этом все элементы arr2 содержатся в arr1.

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

• 1 <= n, m <= 106
• 0 <= arr1[i], arr2[i] <= 1000
• Все элементы массива arr2 различны.
• Каждый элемент массива arr2[i] содержится в массиве arr1.

Примеры

• items[i] = [valuei, weighti], где valuei обозначает значение, а weighti обозначает вес  iго элемента;
• значение каждого элемента уникально.

Верните двумерный массив ret, где ret[i] = [valuei, weighti], в котором weighti является суммой весов всех значений valuei.
Массив ret должен быть отсортирован по возрастанию по значению value.

• 1 <= n1, n2 <= 1000
• items1[i].len() == items2[i].len() == 2
• 1 <= valuei, weighti <= 1000
• Каждое значение valuei в items1 уникально.
• Каждое значение valuei в items2 уникально.

Примеры

3
1 1
4 5
3 8
2
3 1
1 5

[[1, 6], [3, 9], [4, 5]]

3
1 1
3 2
2 3
3
2 1
3 2
1 3

[[1, 4], [2, 4], [3, 4]]

Дано целое число  N<=10³ и N целых чисел. необходимо найти три числа, произведение которых максимально.

Если таких троек чисел несколько, выведите любую из них. 

Входные данные
В первой строке задано целое число 3 <= N <= 10³ - количество элементов в списке.
Во второй строке заданы N целых  элементов списка, не превосходящих по модулю 30000.

Выходные данные
Выведите ответ на задачу.
 

Примеры

Примеры

Примеры

Чебурашка обожает мандарины. Сейчас он оказался на новогодней ярмарке среди большого количества ящиков с мандаринами. В i-м ящике bi мандаринов. Ярмарка начинает свою работу через h часов.

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

Чебурашка любит есть медленно, но желает съесть все мандарины до открытия ярмарки.

Помогите найти Чебурашке минимальную скорость поедания мандаринов, но такую, чтобы он все-таки смог съесть все мандарины.
 

Примеры

В Сильвертауне расположены n розничных магазинов. В логистический центр города доставили m типов товаров с различным количеством, которые необходимо распределить по всем розничным магазинам. Логистическому центру необходимо распределить все товары по магазинам, следуя следующим правилам:

- Каждому магазину распределяется не более одного типа товара, но любое его количество.
- После распределения каждому магазину предоставляется некоторое количество товаров (возможно нулевое).

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

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

Примеры

На конвейерной ленте расположены посылки, которые необходимо доставить из одного порта в другой в течение d дней. Судно отправляется в другой порт один раз в сутки. i-я упаковка на конвейерной ленте имеет вес wi. Судно принимает на борт грузы в том порядке, в котором они располагаются на ленте. Причем, судно не сможет вместить больше посылок, чем его максимальная грузоподъемность.

Вам известно, в каком порядке расположены посылки на конвейерной ленте. Найдите минимальную грузоподъемность судна, на котором вы сможете доставить все ваши посылки в другой порт за d дней.

Примеры

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются целые числа, знаки арифметических операций, круглые скобки, вызовы функций ( sin , cos , abs , sqrt ) и имена переменных (только однобуквенные). Результат операции деления – вещественное число.

Первая строка содержит правильную запись арифметического выражения. В следующих нескольких строках записаны значения всех переменных, использованных в выражении. Каждая из этих строк имеет формат:

<имя переменной>=<значение>

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

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

Примеры

cos(z+abs(sqrt(r*sin(x+4))))
r=5
z=10
x=3

0.729

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются целые числа, знаки арифметических операций, круглые скобки и вызовы функций ( sin , cos , abs , sqrt ). Результат операции деления – вещественное число.

На вход программы поступает символьная строка, содержащая правильную запись арифметического выражения.

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

Примеры

12+cos(sqrt(12+sin(2)))

11.100

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются только целые числа, знаки арифметических операций (+-*/) и скобки произвольной вложенности. Результат операции деления – целое число.

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

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

Примеры

(5+20)*(98-34)/(5*8-23)

94

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются только целые числа и знаки арифметических операций (+-*/). Результат операции деления – целое число.

На вход программы поступает символьная строка, содержащая правильную запись арифметического выражения.

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

Примеры

125-6-73/5*8

7

Компания Giggle открывает свой новый офис в Судиславле, и вы приглашены на собеседование. Ваша задача — решить поставленную задачу.

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

• запрос: «? i j» — возвращает минимальный элемент между i-ым и j-м, включительно;
• изменение: «+ i x» — добавить элемент x после i-го элемента списка. Если i=0, то элемент добавляется в начало массива.

Конечно, эта структура должна быть достаточно хорошей.

Первая строка входного файла содержит единственное целое число n — число операций над массивом (1<=n<=200000). Следующие n строк описывают сами операции. Все операции добавления являются корректными. Все числа, хранящиеся в массиве, по модулю не превосходят 10⁹.

Для каждой операции в отдельной строке выведите её результат.

Комментарий к примеру тестов

Примеры

8
+ 0 5
+ 1 3
+ 1 4
? 1 2
+ 0 2
? 2 4
+ 4 1
? 3 5

4
3
1

Дан массив. Надо научиться обрабатывать два типа запросов.

* 1 L R - перевернуть отрезок [L,R]

* 2 L R - найти минимум на отрезке [L,R]

Первая строка файла содержит два числа n, m. (1<=n,m<=10⁵) Во второй строке находится n чисел ni (1<=a_i<=10⁹) - исходный массив. Остальные m строк содержат запросы, в формате описанном в условии. Для чисел L, R выполняется ограничение (1<=L<=R<=n).

На каждый запрос типа 2, во входной файл выведите ответ на него, в отдельной строке.

Примеры

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

3
2
2
2

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

ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».

DELETE n — если указанное число есть в дереве, удалять его и выводить слово «DONE», если нет — оставлять дерево как было и выводить слово «CANNOT». При удалении элемента, имеющего два сына, обязательно обменивать значение с максимальным элементом левого поддерева.

SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

В каждой строке входных данных записан один из запросов ADD n или DELETE n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

Для каждого запроса выводите ответ на него. Для запросов ADD, DELETE и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:

template void print_tree(Node *p, int level)

{

  if(p==NULL)

    return;

  print_tree(p->left, level+1);

  for(int i=0; i < level; i++)

    cout << ".";

  cout <<  p->data << endl;

  print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

Примеры

ADD 2
ADD 7
ADD 5
PRINTTREE
ADD 5
DELETE 3
ADD 0
PRINTTREE
DELETE 7
PRINTTREE

DONE
DONE
DONE
2
..5
.7
ALREADY
CANNOT
DONE
.0
2
..5
.7
DONE
.0
2
.5

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

ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».

SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

В каждой строке входных данных записан один из запросов ADD n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

Для каждого запроса выводите ответ на него. Для запросов ADD и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:
 

template void print_tree(Node *p, int level)

{

  if(p==NULL)

    return;

  print_tree(p->left, level+1);

  for(int i=0; i < level; i++)

    cout << ".";

  cout <<  p->data << endl;

  print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

Примеры

ADD 2
ADD 3
ADD 2
SEARCH 2
ADD 5
PRINTTREE
SEARCH 7

DONE
DONE
ALREADY
YES
DONE
2
.3
..5
NO

У вашего одноклассника, которого вы не очень любите за его занудство, но уважаете за его ум, были обнаружены две строки: строка t длины m и строка s длины n. Последовательность индексов p1, p2, ..., pm, где 1<=p1<p2<…<pm<=n, называется хорошей , если spi=ti для всех i от 1 до m. Шириной последовательности называется величина \(\max_{i = 1}^{m - 1} \left(p_{i + 1} - p_i\right)\), то есть максимальная разность между соседними элементами последовательности p.

Помогите однокласснику найти хорошую последовательность индексов с максимальной шириной. Одноклассник обещал вам, что строки s и t таковы, что хотя бы одна хорошая последовательность точно существует.

Первая строка входных данных содержит два числа n и m (2<=m<=n<=200000) - длины строк s и t соответственно.

Во второй строке входных данных задана строка s, состоящая из строчных букв английского алфавита, а в третьей строке задана строка t, состоящая из строчных букв английского алфавита.

Гарантируется, что существует хотя бы одна хорошая последовательность индексов.

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

В первом примере из условия существуют две хорошие последовательности с шириной 3: это {1,2,5} и {1,4,5}.

Во втором примере из условия хорошая последовательность максимальной ширины — это {1,5}.

В третьем примере из условия есть лишь одна хорошая последовательность — это {1,2,3,4,5}.

В четвёртом примере из условия есть лишь одна хорошая последовательность — это {1,2}.

Примеры

5 3
abbbc
abc

3

5 2
aaaaa
aa

4

5 5
abcdf
abcdf

1

2 2
ab
ab

1

Примеры

Примеры

3 2
2 6
3 4 5

1
1

3 2
1 6
4 3 5

0

3 5
1 7
5 3 4

3 
2
3
1

Примеры

4 1
4 2 1 5

3

7 10
1 3 20 2 7 45 5

15