Задача №113768. Умный обогреватель
Квартира Максима еще не прошла реновацию, поэтому температура в ней сильно зависит от температуры на улице. Для поддержания комфортной температуры он купил обогреватель и установил систему «Умный дом». В соответствующую программу Максим заложил два целых числа t min ≤ t max и следующий алгоритм использования обогревателя:
- Если в течение последних пяти дней до текущего дня включительно обогреватель каждый день был выключен, и в каждый из этих дней температура на улице была строго меньше t min , то надо включить обогреватель в этот день и считать, что он был включен весь день. Обогреватель остается включенным и в последующие дни до тех пор, пока программа его не выключит.
- Если в течение последних пяти дней до текущего дня включительно обогреватель каждый день был включен, и в каждый из этих дней температура на улице была строго больше t max , то надо выключить обогреватель в этот день и считать, что он был выключен весь день. Обогреватель остается выключенным и в последующие дни до тех пор, пока программа его не включит.
Из-за кратковременного отключения электроэнергии программу необходимо настроить заново. Сами значения t min и t max Максим забыл, зато у него остались записи программы о температуре и состоянии обогревателя в каждые из n дней использования системы.
Максим помнит, что t min и t max были целыми числами, по модулю не превосходящими 10 9 и t min ≤ t max , также он помнит, что программа не учитывала дни до первого дня использования системы и не включала обогреватель в течение первых четырех дней. Наконец, Максим помнит, что он выбирал t min и t max как можно более близкими друг к другу.
Помогите найти два подходящих значения t min и t max , не превосходящих 10 9 по абсолютной величине, таких, что выполняются правила использования обогревателя в каждые из n дней, t min не превосходит t max и величина t max - t min минимальна.
Гарантируется, что записи программы правильные, и такие два числа существуют.
В первой строке задано целое число n ( 5 ≤ n ≤ 10 5 ) — количество дней, в течение которых работала система.
Во второй строке входных данных задаются n целых чисел t 1 , ..., t n ( - 10 9 ≤ t i ≤ 10 9 ) — температуры на улице в каждый из n дней.
В третьей строке входных данных задается строка из n символов, состоящая из 0 и 1 — если в i -й позиции данной строки записан 0 , то это значит, что в i -й день обогреватель был выключен, а если 1 , — то включен.
В единственной строке выведите два целых числа t min и t max ( t min ≤ t max ), по модулю не превосходящих 10 9 — значения температур, при вставке которых в программу обогреватель будет включен и выключен в те же дни, в которые он был включен и выключен при исходных значениях, а значение t max - t min минимально.
Если подходящих пар значений несколько, выведите любую из них.
В первом тестовом примере первые пять дней температура строго меньше 7 градусов, при этом до пятого дня обогреватель был в каждый из четырех дней выключен, следовательно в пятый день программа его включила. На данный тест корректен любой ответ удовлетворяющий условию 6 ≤ t min = t max ≤ 10 9 .
В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования
Решения, работающие при 5 ≤ n ≤ 10 , - 10 ≤ t i ≤ 10 , наберут не менее 20 баллов.
Решения, работающие при 5 ≤ n ≤ 100 , - 100 ≤ t i ≤ 100 , наберут не менее 40 баллов.
Решения, работающие при 5 ≤ n ≤ 100 , - 10 9 ≤ t i ≤ 10 9 , наберут не менее 60 баллов.
5 1 2 3 4 5 00001
7 7
11 2 1 -1 -1 1 1 6 7 8 8 6 00000111111
2 6