| Автор: | Антон Карабанов | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход |
После замены батарейки в электронных часах, Зинаиде требуется установить на индикаторе верное время. Для этого ей следует воспользоваться тремя кнопками, каждая из которых должна увеличивать число часов, минут и секунд на 1 соответственно. Однако, в последнее время эти кнопки барахлят — соответствующее число действительно увеличиваются на 1, зато два других на 1 уменьшаются! Например, если сейчас на индикаторе 12:34:56, то при нажатии на вторую кнопку время изменится на 11:35:55. Определите, какое минимальное количество нажатий на кнопки придётся сделать, чтобы установить нужное время.
Две строки входного файла содержат текущее и требуемое состояние индикатора в формате hh:mm:ss с ведущими нулями. Гарантируется, что эти два момента времени различны.
Выведите одно натуральное число — ответ на вопрос задачи. Гарантируется, что требуемая последовательность нажатий на кнопки существует.
00 ≤ hh ≤ 23
00 ≤ mm, ss ≤ 59
Сейчас на индикаторе 00:00:00. Зинаида дважды нажмёт на вторую кнопку (время изменится сперва на 23:01:59, затем на 22:02:58) и один раз на третью.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
Поиск в ширину.
Заведём массив из 24 * 60 * 60 элементов (время в секундах в сутках) и сформулируем правила перехода от одного элемента к другому в соответствии с нажатиями на кнопки (в результате от каждого момента времени мы можем перейти ровно к трём другим моментам времени).
Получили граф, применив BFS к которому, определим наименьшее количество операций, позволяющих достичь требуемого времени от стартового.