Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 17 18 19 20 21 22 23 >> Отображать по:
#2532
Ханты-Мансийск — Париж
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В 2050 году руководство Глобальной Телефонной Сети (ГТС) приняло решение о новой системе тарификации коротких текстовых сообщений. Теперь цена отправки одного сообщения зависит от количества совпадающих цифр в начале номеров телефонов отправителя и получателя. Если первые \(c\) цифр телефонов совпадают, а \((c+1)\)-я цифра различается, то стоимость сообщения составляет \((10-c)\) кредитов (\(0\le c\le9\)). Все номера телефонов — десятизначные. При этом ГТС разрешает каждому абоненту отправлять сообщение только в пределах часового пояса своего проживания или часовых поясов, отличающихся от него на 1 час.

Школьник Поликарп из Ханты-Мансийска (время +2 часа от московского) успешно решил все задания первого тура олимпиады школьников по информатике. Теперь он желает сообщить об этом в Париж (время −2 часа от московского) своему учителю — профессору де Коде́ру. Так как Ханты-Мансийск и Париж находятся не в соседних часовых поясах, Поликарп не может послать сообщение напрямую. Поэтому он пользуется тем, что у него есть друзья, которые проживают в Ханты-Мансийске, Париже, а также в промежуточных часовых поясах — в Дубае (время +1 час от московского), Москве и Калининграде (время −1 час от московского). Друзья Поликарпа по цепочке доставят профессору де Коде́ру столь важную информацию. Поликарп хочет организовать передачу информации таким образом, чтобы минимизировать суммарные расходы по отправке всех сообщений.

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

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

Первые две строки входного файла содержат телефонные номера Поликарпа и профессора де Коде́ра. Далее следуют 5 блоков данных, описывающих друзей Поликарпа, живущих в Ханты-Мансийске, Дубае, Москве, Калининграде и Париже, соответственно. Каждый блок начинается со строки, содержащей одно число \(n_i\) (\(1\le n_i\le100\,000\)) — количество друзей Поликарпа в соответствующем городе, после которой следуют \(n_i\) строк — номера телефонов друзей. Все номера телефонов состоят ровно из 10 цифр. Гарантируется, что сумма всех \(n_i\) не превосходит 100 000. Все номера телефонов во входных данных различны.

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

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

Система оценивания

  • Решения, корректно работающие при сумме \(n_i\), не превосходящей 500, будут оцениваться из 40 баллов.
  • Решения, корректно работающие при сумме \(n_i\), не превосходящей 5 000, будут оцениваться из 60 баллов.

    • Примеры
    Входные данные
    2099013166
7043239909
1
0258442145
1
0000000000
1
0000000001
1
0000000002
1
0147571204
    Выходные данные
    22 5
2099013166
0000000000
0000000001
0000000002
7043239909
    Входные данные
    4261802325
7967612531
1
8176476745
1
3084033164
1
1737248630
1
9447552231
1
2848478213
    Выходные данные
    40 5
4261802325
3084033164
1737248630
9447552231
7967612531
    #2534
    Земледелие 2.0
      
    ограничение по времени на тест
    2.0 second;
    ограничение по памяти на тест
    256 megabytes

    Фермер Архип решил заняться земледелием и выращивать брюссельскую редиску. Для этого он купил прямоугольное поле, состоящее из \(n\) рядов по \(m\) участков в каждом. Все участки являются одинаковыми и имеют квадратную форму. Оказалось, что на момент покупки некоторые из этих участков уже удобрены, а некоторые — нет. Редиска растет только на удобренных участках.

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

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

    Напишите программу, которая по заданному полю находит фрагмент поля для удобрения и фрагмент поля под посадку.

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

    В первой строке входного файла записаны натуральные числа \(n\) и \(m\) (\(2\le n\le2\,000\), \(2\le m\le2\,000\)), где \(n\) — количество рядов на поле, а \(m\) — количество участков в каждом ряду (количество столбцов). Далее в \(n\) строках содержится описание поля. Каждая из этих \(n\) строк содержит \(m\) символов. Символ «1» обозначает, что соответствующий участок поля удобрен, а «0» — не удобрен. Гарантируется, что поле содержит хотя бы один удобренный и хотя бы один неудобренный участок. Поле расположено таким образом, что первая строка его описания соответствует северной стороне, а первый столбец — западной стороне.

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

    Первая строка должна описывать фрагмент поля для удобрения. Фрагмент описывается четырьмя числами \(a\), \(b\), \(c\), \(d\), где \(a\) и \(b\) — номер ряда и столбца самого северо-западного его участка, а \(c\) и \(d\) — номер ряда и столбца самого юго-восточного. Ряды нумеруются с севера на юг от 1 до \(n\), а столбцы — с запада на восток от 1 до \(m\).

    Вторая строка должна описывать фрагмент под посадку в том же формате.

    Третья строка должна содержать площадь фрагмента (количество участков) под посадку.

    Если решений несколько, выведите любое.

    Система оценивания

    Решения, корректно работающие при \(n\le40\) и \(m\le40\), будут оцениваться из 30 баллов, а решения, корректно работающие при \(n\le300\) и \(m\le300\), будут оцениваться из 60 баллов.

    Примеры
    Входные данные
    4 4
1110
1010
1110
0000
    Выходные данные
    2 2 2 2
1 1 3 3
9
    #2772
    Сумма в прямоугольнике
      
    ограничение по времени на тест
    6.0 second;
    ограничение по памяти на тест
    512 megabytes

    У Олега есть матрица целых чисел \(N \times M\). Его очень часто просят узнать сумму всех элементов матрицы в прямоугольнике с левым верхним углом (\(x_1\), \(y_1\)) и правым нижним  (\(x_2\), \(y_2\)). Помогите ему в этом.

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

    В первой строке находится числа \(N, M\) размеры матрицы (\(1 \leq N, M \leq 1000\)) и K - количество запросов (\(1 \leq K \leq 100000\)). Каждая из следующих \(N\) строк содержит по \(M\) чисел --- элементы соответствующей строки матрицы (по модулю не превосходят 1000). Последующие K строк содержат по \(4\) целых числа, разделенных пробелом - \(x_1\) \(y_1\) \(x_2\) \(y_2\) --- запрос на сумму элементов матрице в прямоугольнике (\(1 \leq x_1 \leq x_2 \leq N, 1 \leq y_1 \leq y_2 \leq M\))

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

    Для каждого запроса на отдельной строке выведите его результат - сумму всех чисел в элементов матрице в прямоугольнике \((x_1,y_1)\), \((x_2,y_2)\)

    Примеры
    Входные данные
    3 3 2
1 2 3
4 5 6
7 8 9
2 2 3 3
1 1 2 3
    Выходные данные
    28
21
    #2781
    Декартово дерево
      
    ограничение по времени на тест
    2.0 second;
    ограничение по памяти на тест
    64 megabytes

    Вам даны пары чисел \((a_i, b_i)\), Вам необходимо построить декартово дерево, такое что \(i\)-ая вершина имеет ключи \((a_i, b_i)\), вершины с ключом \(a_i\) образуют бинарное дерево поиска, а вершины с ключом \(b_i\) образуют кучу на минимум.

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

    В первой строке записано число \(N\) — количество пар. Далее следует \(N\) (\(1 \le N \le 50\,000\)) пар \((a_i, b_i)\). Для всех пар \(\lvert a_i\rvert, \lvert b_i \rvert \le 30\,000\). \(a_i \ne a_j\) и \(b_i \neq b_j\) для всех \(i \ne j\).

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

    Если декартово дерево с таким набором ключей построить возможно, выведите в первой строке YES, в противном случае выведите NO. В случае ответа YES, выведите \(N\) строк, каждая из которых должна описывать вершину. Описание вершины состоит из трёх чисел: номер предка, номер левого сына и номер правого сына. Если у вершины отсутствует предок или какой-либо из сыновей, то выводите на его месте число 0.

    Если подходящих деревьев несколько, выведите любое.

    Примеры
    Входные данные
    7
5 4
2 2
3 9
0 5
1 3
6 6
4 11
    Выходные данные
    YES
2 3 6
0 5 1
1 0 7
5 0 0
2 4 0
1 0 0
3 0 0
    #2782
    Следующий
      
    ограничение по времени на тест
    3.0 second;
    ограничение по памяти на тест
    64 megabytes

    Реализуйте структуру данных, которая поддерживает множество \(S\) целых чисел, с котором разрешается производить следующие операции:

    • \(add(i)\) — добавить в множество \(S\) число \(i\) (если он там уже есть, то множество не меняется);
    • \(next(i)\) — вывести минимальный элемент множества, не меньший \(i\). Если искомый элемент в структуре отсутствует, необходимо вывести -1.
    Входные данные

    Исходно множество \(S\) пусто. Первая строка входного файла содержит \(n\) — количество операций (\(1 \le n \le 300\,000\)). Следующие \(n\) строк содержат операции. Каждая операция имеет вид либо «+ \(i\)», либо «? \(i\)». Операция «? \(i\)» задает запрос \(next(i)\).

    Если операция «+ \(i\)» идет во входном файле в начале или после другой операции «+», то она задает операцию \(add(i)\). Если же она идет после запроса «?», и результат этого запроса был \(y\), то выполняется операция \(add((i + y) \bmod 10^9)\).

    Во всех запросах и операциях добавления параметры лежат в интервале от \(0\) до \(10^9\).

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

    Для каждого запроса выведите одно число — ответ на запрос.

    Примеры
    Входные данные
    6
+ 1
+ 3
+ 3
? 2
+ 1
? 4
    Выходные данные
    3
4
    Страница: << 17 18 19 20 21 22 23 >> Отображать по:
    Выбрано
    :
    Отменить
    |
    Добавить в контест