| Условие задачи | | Прогресс |
|
Темы:
0-1 BFS
Дек
В городе Н при невыясненных обстоятельствах территория одного из заводов превратилась в аномальную зону. Все подъезды к территории были перекрыты, а сама она получила название промзоны. В промзоне находятся N зданий, некоторые из них соединены дорогами. По любой дороге можно перемещаться в обоих направлениях.
Начинающий сталкер получил задание добраться до склада в промзоне. Он нашел в электронном архиве несколько карт территории промзоны. Так как карты составлялись разными людьми, то на каждой из них есть информация только о некоторых дорогах промзоны. Одна и та же дорога может присутствовать на нескольких картах.
В пути сталкер может загружать из архива на мобильный телефон по одной карте. При загрузке новой карты предыдущая в памяти телефона не сохраняется. Сталкер может перемещаться лишь по дорогам, отмеченным на карте, загруженной на данный момент. Каждая загрузка карты стоит 1 рубль. Для минимизации расходов сталкеру нужно выбрать такой маршрут, чтобы как можно меньшее число раз загружать карты. Сталкер может загружать одну и ту же карту несколько раз, при этом придется заплатить за каждую загрузку. Изначально в памяти мобильного телефона нет никакой карты.
Требуется написать программу, которая вычисляет минимальную сумму расходов, необходимую сталкеру, чтобы добраться от входа в промзону до склада.
Входные данные:
- в первой строке входных данных содержатся два натуральных числа N и K (\(2 <= N <= 2000\); \(1 <= K <= 2000\)) — количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад — в здании с номером N.
- в последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число ri — количество дорог, обозначенных на i-ой карте;
- затем идут ri строк, содержащие по два натуральных числа a и b (\(1 <= a\), \(b <= N\); \(a ? b\)), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (\(r_1 + r_2 + … + r_K <= 300 000\)).
Выходные данные: выведите одно число — минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число –1.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
12 4
4
1 6
2 4
7 9
10 12
3
1 4
7 11
3 6
3
2 5
4 11
8 9
5
3 10
10 7
7 2
12 3
5 12 |
3 |
| |
![]()
|
|
Темы:
Дек
Реализуйте структуру данных "дек". Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push_front
Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.
push_back
Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.
pop_front
Извлечь из дека первый элемент. Программа должна вывести его значение.
pop_back
Извлечь из дека последний элемент. Программа должна вывести его значение.
front
Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.
back
Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.
size
Вывести количество элементов в деке.
clear
Очистить дек (удалить из него все элементы) и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Все операции pop_front, pop_back, front, back всегда корректны.
Входные данные
Вводятся команды управления деком, по одной на строке.
Выходные данные
Требуется вывести протокол работы дека, по одному сообщению на строке.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
push_back 1
back
exit |
ok
1
bye |
| 2 |
size
push_back 1
size
push_back 2
size
push_front 3
size
exit |
0
ok
1
ok
2
ok
3
bye |
| |
![]()
|
|
Темы:
Дек
Реализуйте структуру данных "дек". Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push_front
Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.
push_back
Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.
pop_front
Извлечь из дека первый элемент. Программа должна вывести его значение.
pop_back
Извлечь из дека последний элемент. Программа должна вывести его значение.
front
Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.
back
Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.
size
Вывести количество элементов в деке.
clear
Очистить дек (удалить из него все элементы) и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Перед исполнением операций pop_front, pop_back, front, back программа должна проверять, содержится ли в деке хотя бы один элемент. Если во входных данных встречается операция pop_front, pop_back, front, back, и при этом дек пуст, то программа должна вместо числового значения вывести строку error.
Входные данные
Вводятся команды управления деком, по одной на строке.
Выходные данные
Требуется вывести протокол работы дека, по одному сообщению на строке
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
push_back 1
back
exit |
ok
1
bye |
| 2 |
size
push_back 1
size
push_back 2
size
push_front 3
size
exit |
0
ok
1
ok
2
ok
3
bye |
| |
![]()
|
|
Темы:
Дерево отрезков, RSQ, RMQ
Дек
Рассмотрим последовательность целых чисел длины N. По ней с шагом 1 двигается “окно” длины K, то есть сначала в “окне” видно первые K чисел, на следующем шаге в “окне” уже будут находиться K чисел, начиная со второго, и так далее до конца последовательности. Требуется для каждого положения “окна” определить минимум в нём.
Входные данные
В первой строке входных данных содержатся два числа N и K (1 ≤ N ≤ 150000, 1 ≤ K ≤ 10000, K ≤ N) – длины последовательности и “окна”, соответственно. На следующей строке находятся N чисел – сама последовательность.
Выходные данные
Выходые данные должны содержать N − K + 1 строк – минимумы для каждого положения “окна”.
| |
![]()
|