Сначала хотел написать полный разбор, но как разбирать задачи 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.
Насчет задачи C
Мне кажется ошибка в шаге 7. Когда мы прошли 6-ю скобку, то мы нашли последовательность длины не 2, а 4. Т.к. получается последовательность ()().
Надо дополнительно посмотреть на баланс строки с индексом [5-1]. Если баланс [6] равен балансу [5-1], то длины их последовательностей суммируем, т.е. получится длина равна 4.
Тогда надо еще дополнительно ввести массив длин, где мы будем запоминать длины правильных последовательностей.
Это так, тонкости реализации, на которых я и погорел во время контеста. :(
Ошибка в разборе была в том, что я сравнивал с значением в стеке до удаления. Вроде бы исправил..
Чтобы не использовать бинарник, предлагаю использовать такие рассуждения:
Известна формула:
((Vк)*(Vк)-(Vн)*(Vн)=2*a*s
Где Vк- конечная скорость, Vн - начальная, s - расстояние, a - проекция ускорения на Ох(может быть отрицательной)
Пускай скорость, которую нам надо найти равна U.Тогда очевидно уравнение:
(U*U)/(2*a)+(U*U-w*w)/(2*a)=d;
2*U*U=2*a*d+w*w;
U*U=a*d+w*w/2
Следовательно, U равно квадратному корню из левой части нашего уравнения. В преобразованиях имелось в виду, что ускорение всегда положительно. Чесно говоря, еще не сдал задачу, так что поправьте пожалуйста, если что не так.
Другой разбор задачи D. Без двоичного поиска.
Для решения этой задачи рассмотрим 2 случая
Рассмотрим сначала более простую задачу: сколько минимум времени необходимо для проезда D километров с ускорением a и максимальной скоростью v. Нетрудно видеть в данной ситуации либо мы все время движемся с ускорением a, либо достигаем скорости v, а затем движемся со скоростью v.Пример реализации:
double solve(double D) { // время необходимое для равноускоренного движения double t1 = sqrt(2.0 * D / a); // если максимальная скорость не больше v, то мы двигаемся время t if (a * t1 <= v) return t1; // время необходимое для разгона до сорости v double t2 = v / a; // расстояние, которое осталось проехать double s = D - (a * t2 * t2 / 2.0); return t2 + (s / v); }Теперь рассмотрим наши случаи
1) В данном случае ответ на задачу просто solve(l); 2) Опять таки рассмотрим 2 случая: a) Мы двигаемся до точки d равноускоренно с ускорением a; б) Сначала мы движемся равноускоренно, а затем замедляемся и имеем в точке d скорость в точности w;Рассмотрим a). В этом случае ответ на задачу просто solve(l)Теперь рассмотрим б). Сначала мы набираем скорость w. Предположим мы проехали участок длиной s. Тогда до знака осталось d-s. Понятно, что оптимальным маршрутом будет движение с ускорением a на расстояние (d-s)/2, а затем с ускорением -a опять таки на расстояние (d-s)/2. А после этого необходимо пройти расстояние (l-d) уже с максимальным ускорением.
Это можно реализовать так:
double calc(double a, double v, double l, double d, double w) { if (v <= w) return solve(l); else { // время которое необходимо для движения с ускорением a до точки d double t = sqrt(2.0 * d / a); // если скорость меньше w - то это случай a, иначе - это случай b if (a * t <= w) return solve(l); else { // время для достижения скорости w double t1 = w / a; // расстояние, которое мы преодолели double s = a * t1 * t1 / 2.0; // время на прохождение расстояния, когда скорость увеличивается double t2 = solve((s + d) / 2.0); // время на оставшуюся часть double t3 = solve(l - (d - s)); return (t3 - t1) + t1 + 2.0 * (t2 - t1); } } }Объясним откуда получается ответ (t3 - t1) + t1 + 2.0 * (t2 - t1).
(t3 - t1) - время на оставшуюся часть. Предполагается что сначала мы достигли скорости w, а затем как будто бы пропустили кусок [s, d] и продолжили равноускоренное движение. Тогда t3 - общее время, а t1 - время на развитие скорости w => время на остаток дороги (t3 - t1), ведь от точки d мы начинали со скоростью w.
t1 - время необходимое для достижения скорости w.
2.0 * (t2 - t1) - время на прохождение участка [s, d]. Предполагается что от [0, (s + d) / 2] мы двигались с ускорением a, тогда мы потратим на это время t2, но на достижение точки s мы потратим время t1 => на отрезок [s, (s + d) / 2] уйдет (t2 - t1) времени, после этого мы сбавляем скорость с ускорением -a на отрезке [(s + d) / 2, d] - понятно, на это уйдет также (t2 - t1) времени => итоговое время на этот участок 2 * (t2 - t1). В итоге имеем минимальное время - это время time[0, s] + time[s, d] + time[d, l] = (t1) + 2 * (t2 - t1) + (t3 - t1) = t3 + 2 * t2 - 2 * t1.
В задаче С удобно хранить структуру deque < pair<char, int> > q. Каждая открывающаяся или непарная закрывающаяся скобка кладется вместе с 0. Если закрывающаяся парная, удаляем соответствующую открывающуюся и последней оставшейся в деке скобке прибавляем значение удаленной. O(N), понятно. http://www.codeforces.ru/contest/5/submission/3268096