Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 266 267 268 269 270 271 272 >> Отображать по:
#2785
Химия!!!
  
Темы: [Потоки]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Вася и Сережа играют в следующую игру. В некоторых клетках клетчатого листка Сережа рисует один из символов 'H', 'O', 'N' или 'C', после чего Вася должен провести между некоторыми находящимися в соседних клетках символами линии так, чтобы получилось корректное изображение химической молекулы. К сожалению, Сережа любит рисовать много символов, и Вася не может сразу определить, возможно ли вообще нарисовать линии нужным способом. Помогите ему написать программу, которая даст ответ на этот вопрос.

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

  • каждая линия соединяет символы, нарисованные в соседних (по стороне) клетках,
  • между каждой парой символов проведено не более одной линии,
  • от каждого элемента отходит ровно столько линий, какова валентность этого элемента (1 для H, 2 для O, 3 для N, 4 для C),
  • пустые клетки ни с чем не соединены, и
  • хотя бы в одной клетке нарисован какой-то символ.
Входные данные

Первая строка входного файла содержит два натуральных числа \(n\) и \(m\) (\(1\leq n,m\leq 50\)) — размеры листочка, на котором рисует Сережа. Далее следуют \(n\) строк по \(m\) символов в каждой, задающих конфигурацию химических элементов, которую нарисовал Сережа; пустые клетки задаются символом '.'.

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

В выходной файл выведите одно слово «Valid», если линии провести требуемым образом можно, и «Invalid», если нельзя.

Примеры
Входные данные
3 4
HOH.
NCOH
OO..
Выходные данные
Valid
Входные данные
3 4
HOH.
NCOH
OONH
Выходные данные
Invalid
#2786
Разрезание графа
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дан неориентированный граф. Над ним в заданном порядке производят операции следующих двух типов:

  • cut — разрезать граф, то есть удалить из него ребро;
  • ask — проверить, лежат ли две вершины графа в одной компоненте связности.

Известно, что после выполнения всех операций типа cut рёбер в графе не осталось. Найдите результат выполнения каждой из операций типа ask.

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

Первая строка входного файла содержит три целых числа, разделённые пробелами — количество вершин графа \(n\), количество рёбер \(m\) и количество операций \(k\) (\(1 \le n \le 50\,000\), \(0 \le m \le 100\,000\), \(m \le k \le 150\,000\)).

Следующие \(m\) строк задают рёбра графа; \(i\)-ая из этих строк содержит два числа \(u_i\) и \(v_i\) (\(1 \le u_i, \, v_i \le n\)), разделённые пробелами — номера концов \(i\)-го ребра. Вершины нумеруются с единицы; граф не содержит петель и кратных рёбер.

Далее следуют \(k\) строк, описывающих операции. Операция типа cut задаётся строкой „cut \(u\) \(v\)“ (\(1 \le u, \, v \le n\)), которая означает, что из графа удаляют ребро между вершинами \(u\) и \(v\). Операция типа ask задаётся строкой „ask \(u\) \(v\)“ (\(1 \le u, \, v \le n\)), которая означает, что необходимо узнать, лежат ли в данный момент вершины \(u\) и \(v\) в одной компоненте связности. Гарантируется, что каждое ребро графа встретится в операциях типа cut ровно один раз.

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

Для каждой операции ask во входном файле выведите на отдельной строке слово „YES“, если две указанные вершины лежат в одной компоненте связности, и „NO“ в противном случае. Порядок ответов должен соответствовать порядку операций ask во входном файле.

Примеры
Входные данные
3 3 7
1 2
2 3
3 1
ask 3 3
cut 1 2
ask 1 2
cut 1 3
ask 2 1
cut 2 3
ask 3 1
Выходные данные
YES
YES
NO
NO
#2787
LCA-Offline
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Изначально имеется дерево состоящее только из корня (вершина с номером \(1\)). Требуется научиться отвечать на следующие запросы:

  • ADD \(a\) \(b\) — подвесить вершину \(b\) за вершину \(a\) (гарантируется, что вершина \(a\) уже существует, а вершина \(b\) еще не существует).
  • GET \(a\) \(b\) — вернуть LCA вершин \(a\) и \(b\).

Все номера вершин от \(1\) до \(N\).

В каждый момент времени у нас есть одно дерево.

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

В первой строке входного файла содержится число \(k\) — количество запросов. Следующие \(k\) строк содержат сами запросы. Гарантируется, что число запросов каждого из типов не превосходит \(500\,000\).

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

Для каждого запроса типа GET выведите в отдельную строку одно целое число — ответ на соответствующий запрос.

Примеры
Входные данные
9
ADD 1 2
ADD 1 3
ADD 2 4
GET 1 3
GET 2 3
GET 3 4
ADD 2 5
GET 4 5
GET 5 5
Выходные данные
1
1
1
2
5
#2789
Своппер
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes

Современные компьютеры зацикливаются в десятки раз эффективнее человека
Рекламный проспект OS Vista-N

Перед возвращением в штаб-квартиру корпорации Аазу и Скиву пришлось заполнить на местной таможне декларацию о доходах за время визита. Получилась довольно внушительная последовательность чисел. Обработка этой последовательности заняла весьма долгое время.

— Своппер кривой, — со знанием дела сказал таможенник.

— А что такое своппер? — спросил любопытный Скив.

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

  • Взять отрезок чётной длины от \(x\) до \(y\) и поменять местами число \(x\) с \(x+1\), \(x+2\) с \(x+3\), и т.д.
  • Посчитать сумму чисел на произвольном отрезке от \(a\) до \(b\).

Учитывая, что обсчёт может затянуться надолго, корпорация «МИФ» попросила Вас решить проблему со своппером и промоделировать ЭТО эффективно.

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

Во входном файле заданы один или несколько тестов. В первой строке каждого теста записаны число \(N\) — длина последовательности и число \(M\) — число операций (\(1 \le N, \, M \le 100\,000\)). Во второй строке теста содержится \(N\) целых чисел, не превосходящих \(10^6\) по модулю — сама последовательность. Далее следуют \(M\) строк — запросы в формате 1 \(x_i\) \(y_i\) — запрос первого типа, и 2 \(a_i\) \(b_i\) — запрос второго типа. Сумма всех \(N\) и \(M\) по всему файлу не превосходит \(200\,000\). Файл завершается строкой из двух нулей. Гарантируется, что \(x_i \le y_i\), а \(a_i \le b_i\).

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

Для каждого теста выведите ответы на запросы второго типа, как показано в примере. Разделяйте ответы на тесты пустой строкой.

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

Swapper 2:
10
9
2
#2790
Range Minimum Query
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
128 megabytes

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

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

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

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

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

Первая строка входного файла содержит единственное целое число \(n\) — число операций над массивом (\(1 \le n \le 200\,000\)). Следующие \(n\) строк описывают сами операции. Все операции добавления являются корректными. Все числа, хранящиеся в массиве, по модулю не превосходят \(10^9\).

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

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

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

Нижеследующая таблица показывает процесс изменения массива из примера.

ОперацияМассив после её выполнения
изначальнопуст
+ 0 55
+ 1 35, 3
+ 1 45, 4, 3
+ 0 22, 5, 4, 3
+ 4 12, 5, 4, 3, 1

Примеры
Входные данные
8
+ 0 5
+ 1 3
+ 1 4
? 1 2
+ 0 2
? 2 4
+ 4 1
? 3 5
Выходные данные
4
3
1
Страница: << 266 267 268 269 270 271 272 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест