Начало
СоревнованияПодразделы
Другие разделы
Дата и время
2548. Пещера
Пещера
Максимум (минимум) для последовательности вычисляемых значений
Олимпиадные задачи на русском языке
| 27/12/2020 | Очный тур личного первенства по спортивному программированию (K) |
| 03/07/2023 | Лето 2023-4 простые (C) |
| 13/11/2023 | Сканирующая прямая (проводит BOGAT) (C) |
| 01/07/2024 | Лето 2024-4 простые (C) |
| 06/11/2024 | ЦОП1 (дорешивание) Метод сканирующей прямой (проводит BOGAT) (B) |
Ограничения: время – 500ms/1000ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (1)
В пещере на Марсе необходимо проложить канал для связи между поселениями. За миллионы лет на потолке пещеры выросли сталактиты, а на полу - сталагмиты. Чтобы проложить канал связи, нужно пробить на некоторой высоте эти образования. Высота туннеля для канала равна 1.
Напишите программу, вычисляющую минимальное количество сталактитов и сталагмитов, которые нужно пробить при прокладке канала.
Первая строка ввода содержит два целых числа - высота пещеры H (2≤H≤500000) и количество сталактитов и сталагмитов N (1≤N≤500000). Вторая строка ввода содержит N целых чисел - длины сталактитов от 1 до H-1. Третья строка ввода содержит N целых чисел - длины сталагмитов от 1 до H-1.
Вывести два целых числа - минимальное количество пробиваемых при прокладке канала сталактитов и сталагмитов и количество уровней (целых значений высот), на которых данный минимум достигается.
Пример ввода
5 7 3 2 4 4 3 2 3 1 4 2 3 3 3 3
Пример вывода
7 2
Пояснение к примеру:
Расположение сталактитов и сталагмитов показано на рисунке. Если пробивать туннель для канала на уровне 4, то потребуется пробить 8 образований, минимальное количество достигается на уровнях 1 и 5.
Рис. 1
