Сначала хотел написать полный разбор, но как разбирать задачи A и B я не представляю :о) Разве что можно сказать, что на C++ чтобы читать до конца надо использовать while( gets( s ) ), а если вы не любите перенаправлять файлы и вводите тест прямо в консоль, то чтобы обозначить конец файла надо нажать Ctrl+Z.
Задача С
Давайте введем понятие баланса некоторого префикса подстроки - на сколько открывающихся скобок больше в этом префиксе, чем закрывающихся. Понятно, что некоторая строка является правильной скобочной подпоследовательностью, если для всей строки баланс равен нулю, а для любого ее префикса не отрицателен. Посчитаем баланс для каждого префикса данной нам в задаче строки и сложим их в массив prefs. Теперь рассмотрим любую подстроку это строки - пусть она идет от символа с позицией l включительно до символа в позиции r исключительно. Эта подстрока - правильная скобочная последовательность, если prefs[l] == prefs[r] и prefs[i] >= prefs[l] для любого i в интервале [l, r). Как нам теперь, зная это, найти максимальную подстроку правильную и их количество? Будем делать примерно так: поддерживать стек пар (баланс-позиция) - на какой позиции в строке впервые был замечен такой баланс, после которой еще не встречался меньший баланс. На самом деле можно даже хранить только позиции, потому что баланс всегда очевиден - в последнем элементе в стеке всегда будет текущий баланс, в предпоследнем на единицу меньше итд. Рассмотрим теперь скажем последовательность ((()())))(()). Балансы: 1,2,3,2,3,2,1,0,-1,0,1,0,-1
Будем идти слева на право и поддерживать наш стек следующим образом: добавляя открывающуюся скобку добавлять в стек позицию этой скобки, а добавляя закрывающуюся удалять последний элемент из стека, улучшая ответ. Пример с нашей последовательносью:
1. Помним, что на позиции 0 (то есть до добавления любой скобки) баланс был 0. То есть сейчас стек: 0
2. Добавляем первую скобку. Занесем ее позицию в стек. Стек: 0,1
3. Добавим вторую скобку. Занесем ее позицию в стек. Стек: 0,1,2
4. Аналогично для третьей скобки. Стек 0,1,2,3
5. Четвертая скобка - закрывающаяся. Соответственно удалим последний элемент из стека, Текущий стек: 0,1,2. Запоминаем, что мы нашли последоательность длины 2 (позиция-последний элемент в стеке после удаления, 4-2=2).
6. Пятая скобка - открывающаяся, добавим ее в стек: 0,1,2,5
7. Шестая скобка - закрывающаяся, удалим из стека последний элемент, запомним, что мы нашли последовательность длины 4. Стек: 0,1,2
8. Седьма скобка - закрывающаяся, удалим из стека последний элемент, запомнив, что мы нашли последовательность длины (7-1)=6. Стек: 0,1.
9. Восьмая скобка - закрывающаяся, удалим из стека последний элемент, запомнив, что мы нашли последовательность длины (8-0)=8. Стек: 0
10. Девятая скобка - закрывающаяся, удалим из стека последний элемент. Стек: пустой.
11. 10-ая скобка закрывающаяся, но стек и так пустой - ничего не меняем.
12. Скобка открывающаяся, стек: 11
13. Скобка открывающаяся, стек: 11,12
14. Далее две закрывающихся скобки очистят стек и еще одна ничего не изменит, ответа больше 8 найдено не будет, таким образом мы нашли ответ 8.
Задача D
Это задача хитрая на рассмотрение граничных случаев.
Сначала случаи до столба:
1. Самый простой - мы разгоняемся до макисимальной скорости, едем на ней участок и тормозим до скорости w. Достаточно просто - считаем время t1 и расстояние s1, проехав которое мы наберем макс. скорость, время t2 и расстояние s2, проехав которой мы с макс. скорости затормозим до w, проверяем, что сумма этих расстояний меньше d, прибавляем время t3=(d-s1-s2)/v, которое мы будем ехать с макс. скоростью. На второй участок мы попадем со скоростью w.
2. Вариант второй - мы не успеваем разогнаться до максимальной скорости и затормозить до скорости w к столбу, то есть s1+s2 > d. Тогда все очевидно - ищем, до какой скорости мы можем разогнаться (я делал это бинарным поиском, но не сомневаюсь что это не обязательно :о)), и считаем сколько времени уйдет чтобы разогнаться до нее и затормозить с нее до w. На второй участок выходим со скоросью w.
3. Третий случай - мы вообще за интервал d не успеваем даже разогнаться до w. Тогда проезжаем весь интервал d на разгоне, на второй участок выходим со скоростью, которую успели набрать.
Тут есть корнер кейс, который зачем-то поместили в первый семпл - если w > v, и третий случай рассматривается до первого, и за интервал d нельзя достичь скорости w, но можно успеть достичь скорости v. Тогда можно ошибочно на первом интервале разгоняться до скорости большей v. Но наличие первого семпла спасало от такой ошибки (и меня от лишнего штрафа :о))
На второй интервал мы выходим либо со скоростью w, если мы попали в первые два случая, либо со скоростью меньшей, если в третий. Теперь тут два достаточно простых случая - мы либо разгоняемся до максимальной и проезжаем часть дороги на максимальной скорости, либо, если мы не успеваем за оставшийся фрагмент дороги достичь максимальной скорости, просто проезжаем весь участок с ускорением a.
Задача E.
Задача подозрительно похожа на задачу С :о)
Найдем максимальный элемент в последовательности и сдвинем все так, чтобы он оказался первым (или любой из них, если их несколько). Теперь, если не учиытвать максимальные холмы, мы можем полагать, что холмы расположены на не окружности, а в ряд, что упрощает задачу. Дальше отдельно решим для пар холмов, оба из которых не максимальной длины, для пар холмов, один из которых не максимальной длины, и для пар холмов, оба из которых максимальной длины.
1. Как посчитать количество пар, где оба холма ниже максимального? Будем идти слева на право, поддерживая стек высот холмов, которые теоретически еще могут быть видны, и их количеств. Разумеется, этот стек всегда будет содержать высоты, идущие по убыванию. Добавляя очередной холм:
1.а) если он максимальной длины, просто очистим стек (ничто не может быть видно, он все загородил), и НЕ улучшаем ответ, и НЕ добавляем его в стек, так как сейчас считаем ответ только для пар, в которых оба холма ниже максимального.
1.б) иначе, пока последний элемент в стеке содержит высоту ниже текущего холма, удаляем этот элемент, прибавляя количество таких холмов к ответу (каждый из этих холмов виден с нашего более высокого).
1.в.i) если после этого высота последнего элемента в стеке равна нашей, прибавим его количество и еще единицу, если в стеке хотя бы два элемента (потому что мы видим все холмы нашей высоты и еще ровно один выше, если он существует)
1.в.ii) если же после этого высота последнего элемента в стеке выше нашей, то просто прибавляем к ответу единицу (мы видим только этот самый правый холм).
1.в.iii) если же стек после 1.б. остался пустой, не меняем ответ.
1.г) если последний элемент в стеке равен нашему, увеличим его количество. Иначе добавим в конец стека текущий элемент с количеством=1.
1.д) пройдя так по всему массиву мы посчитаем количество пар, где оба холма ниже макисимального
2. Как посчитать количество пар, где один из холмов максимальный, а второй нет? Очень легко, начиная от каждого максимального холма идем влево и вправо пока не встретим другой максимальный холм, и считаем сколько холмов мы видим. Это будет линейное время, потому что каждый элемент будет пройден ровно дважды: от холма максимальной высоты слева от него и от холма максимальной высоты справа от него.
3. Как посчитать количество пар, где оба холма максимальны? n*(n-1)/2 где n - количество холмов максимальной высоты.
Затем суммируем ответы из 1, 2 и 3.
Задача С
Давайте введем понятие баланса некоторого префикса подстроки - на сколько открывающихся скобок больше в этом префиксе, чем закрывающихся. Понятно, что некоторая строка является правильной скобочной подпоследовательностью, если для всей строки баланс равен нулю, а для любого ее префикса не отрицателен. Посчитаем баланс для каждого префикса данной нам в задаче строки и сложим их в массив prefs. Теперь рассмотрим любую подстроку это строки - пусть она идет от символа с позицией l включительно до символа в позиции r исключительно. Эта подстрока - правильная скобочная последовательность, если prefs[l] == prefs[r] и prefs[i] >= prefs[l] для любого i в интервале [l, r). Как нам теперь, зная это, найти максимальную подстроку правильную и их количество? Будем делать примерно так: поддерживать стек пар (баланс-позиция) - на какой позиции в строке впервые был замечен такой баланс, после которой еще не встречался меньший баланс. На самом деле можно даже хранить только позиции, потому что баланс всегда очевиден - в последнем элементе в стеке всегда будет текущий баланс, в предпоследнем на единицу меньше итд. Рассмотрим теперь скажем последовательность ((()())))(()). Балансы: 1,2,3,2,3,2,1,0,-1,0,1,0,-1
Будем идти слева на право и поддерживать наш стек следующим образом: добавляя открывающуюся скобку добавлять в стек позицию этой скобки, а добавляя закрывающуюся удалять последний элемент из стека, улучшая ответ. Пример с нашей последовательносью:
1. Помним, что на позиции 0 (то есть до добавления любой скобки) баланс был 0. То есть сейчас стек: 0
2. Добавляем первую скобку. Занесем ее позицию в стек. Стек: 0,1
3. Добавим вторую скобку. Занесем ее позицию в стек. Стек: 0,1,2
4. Аналогично для третьей скобки. Стек 0,1,2,3
5. Четвертая скобка - закрывающаяся. Соответственно удалим последний элемент из стека, Текущий стек: 0,1,2. Запоминаем, что мы нашли последоательность длины 2 (позиция-последний элемент в стеке после удаления, 4-2=2).
6. Пятая скобка - открывающаяся, добавим ее в стек: 0,1,2,5
7. Шестая скобка - закрывающаяся, удалим из стека последний элемент, запомним, что мы нашли последовательность длины 4. Стек: 0,1,2
8. Седьма скобка - закрывающаяся, удалим из стека последний элемент, запомнив, что мы нашли последовательность длины (7-1)=6. Стек: 0,1.
9. Восьмая скобка - закрывающаяся, удалим из стека последний элемент, запомнив, что мы нашли последовательность длины (8-0)=8. Стек: 0
10. Девятая скобка - закрывающаяся, удалим из стека последний элемент. Стек: пустой.
11. 10-ая скобка закрывающаяся, но стек и так пустой - ничего не меняем.
12. Скобка открывающаяся, стек: 11
13. Скобка открывающаяся, стек: 11,12
14. Далее две закрывающихся скобки очистят стек и еще одна ничего не изменит, ответа больше 8 найдено не будет, таким образом мы нашли ответ 8.
Задача D
Это задача хитрая на рассмотрение граничных случаев.
Сначала случаи до столба:
1. Самый простой - мы разгоняемся до макисимальной скорости, едем на ней участок и тормозим до скорости w. Достаточно просто - считаем время t1 и расстояние s1, проехав которое мы наберем макс. скорость, время t2 и расстояние s2, проехав которой мы с макс. скорости затормозим до w, проверяем, что сумма этих расстояний меньше d, прибавляем время t3=(d-s1-s2)/v, которое мы будем ехать с макс. скоростью. На второй участок мы попадем со скоростью w.
2. Вариант второй - мы не успеваем разогнаться до максимальной скорости и затормозить до скорости w к столбу, то есть s1+s2 > d. Тогда все очевидно - ищем, до какой скорости мы можем разогнаться (я делал это бинарным поиском, но не сомневаюсь что это не обязательно :о)), и считаем сколько времени уйдет чтобы разогнаться до нее и затормозить с нее до w. На второй участок выходим со скоросью w.
3. Третий случай - мы вообще за интервал d не успеваем даже разогнаться до w. Тогда проезжаем весь интервал d на разгоне, на второй участок выходим со скоростью, которую успели набрать.
Тут есть корнер кейс, который зачем-то поместили в первый семпл - если w > v, и третий случай рассматривается до первого, и за интервал d нельзя достичь скорости w, но можно успеть достичь скорости v. Тогда можно ошибочно на первом интервале разгоняться до скорости большей v. Но наличие первого семпла спасало от такой ошибки (и меня от лишнего штрафа :о))
На второй интервал мы выходим либо со скоростью w, если мы попали в первые два случая, либо со скоростью меньшей, если в третий. Теперь тут два достаточно простых случая - мы либо разгоняемся до максимальной и проезжаем часть дороги на максимальной скорости, либо, если мы не успеваем за оставшийся фрагмент дороги достичь максимальной скорости, просто проезжаем весь участок с ускорением a.
Задача E.
Задача подозрительно похожа на задачу С :о)
Найдем максимальный элемент в последовательности и сдвинем все так, чтобы он оказался первым (или любой из них, если их несколько). Теперь, если не учиытвать максимальные холмы, мы можем полагать, что холмы расположены на не окружности, а в ряд, что упрощает задачу. Дальше отдельно решим для пар холмов, оба из которых не максимальной длины, для пар холмов, один из которых не максимальной длины, и для пар холмов, оба из которых максимальной длины.
1. Как посчитать количество пар, где оба холма ниже максимального? Будем идти слева на право, поддерживая стек высот холмов, которые теоретически еще могут быть видны, и их количеств. Разумеется, этот стек всегда будет содержать высоты, идущие по убыванию. Добавляя очередной холм:
1.а) если он максимальной длины, просто очистим стек (ничто не может быть видно, он все загородил), и НЕ улучшаем ответ, и НЕ добавляем его в стек, так как сейчас считаем ответ только для пар, в которых оба холма ниже максимального.
1.б) иначе, пока последний элемент в стеке содержит высоту ниже текущего холма, удаляем этот элемент, прибавляя количество таких холмов к ответу (каждый из этих холмов виден с нашего более высокого).
1.в.i) если после этого высота последнего элемента в стеке равна нашей, прибавим его количество и еще единицу, если в стеке хотя бы два элемента (потому что мы видим все холмы нашей высоты и еще ровно один выше, если он существует)
1.в.ii) если же после этого высота последнего элемента в стеке выше нашей, то просто прибавляем к ответу единицу (мы видим только этот самый правый холм).
1.в.iii) если же стек после 1.б. остался пустой, не меняем ответ.
1.г) если последний элемент в стеке равен нашему, увеличим его количество. Иначе добавим в конец стека текущий элемент с количеством=1.
1.д) пройдя так по всему массиву мы посчитаем количество пар, где оба холма ниже макисимального
2. Как посчитать количество пар, где один из холмов максимальный, а второй нет? Очень легко, начиная от каждого максимального холма идем влево и вправо пока не встретим другой максимальный холм, и считаем сколько холмов мы видим. Это будет линейное время, потому что каждый элемент будет пройден ровно дважды: от холма максимальной высоты слева от него и от холма максимальной высоты справа от него.
3. Как посчитать количество пар, где оба холма максимальны? n*(n-1)/2 где n - количество холмов максимальной высоты.
Затем суммируем ответы из 1, 2 и 3.
Comments (0)
