Подразделы

Другие разделы

Дата и время

02/04/2025 18:18:24

Авторизация

Областная олимпиада школьников по информатике (командные соревнования)

1. Подарки 2. Санта-Клаус 3. Удаление буквы 4. Удаление цифры 5. Винни-Пух 6. Олимпиада-2008 7. Робинзон 8. Робот 9. Черное пятно 10. Соревнования

7. Робинзон

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

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

В первой строке ввода содержатся два целых числа, разделенных пробелом – высота скалы

$H$ (

$0\ <\ H\ ≤\ 10^6$ ) и количество уступов

$N$ (

$0\ ≤\ N\ ≤\ 1000$ ). Далее следует

$N$ строк, в каждой строке содержатся три целых числа – координаты левого края уступа

$L_i$ (

$0\ ≤\ L_i\ <\ 1000$ ), координаты правого края уступа

$R_i$ (

$L_i\ <\ R_i\ ≤\ 1000$ ) и высота уступа

$h_i$ (

$0\ <\ h_i\ <\ H$ ).

Вывести в первой строке одно целое число – минимальное число дней для выращивания лиан.

Пример ввода

100 2
0 50 25
50 70 60

Вывод для примера