Страница: 1 Отображать по:
#20
Уроки физкультуры
  

Сегодня в 5-А классе праздник — урок физкультуры. Традиционно ребята в это время после небольшой разминки играют в футбол. Коля очень любит футбол, но сегодня, проходя мимо учительской, он случайно услышал, что несколько самых сильных школьников из 5-А во время урока физкультуры должны помочь разгружать новые парты. Что же делать? Ведь Коля предпочитает поиграть в футбол!

В голове Коли моментально созрел план. Коля знает, что в 5-А классе N школьников. Он хочет воспользоваться тем, что учитель физкультуры Иван Петрович на уроках вместо обычной расстановки школьников в шеренгу по росту практикует расстановку «по силе». Для этого Иван Петрович сначала расставляет N школьников по росту, а затем (N – 1) раз проходит вдоль шеренги слева направо, каждый раз начиная с самого левого (первого) школьника и заканчивая предпоследним школьником справа. Проходя мимо школьника, который стоит на i-м месте (1 ≤ i ≤ N – 1), Иван Петрович просит его помериться силой с соседом справа, который стоит на (i + 1)-м месте. Если школьник, стоящий левее, оказывается сильнее своего соседа справа, то они меняются местами. Если же силы школьников оказываются равны, либо слева стоит более слабый школьник, то школьники остаются на своих местах. После этого Иван Петрович просит помериться силой школьников, стоящих на местах (i + 1) и (i + 2), и т. д., заканчивая каждый проход школьниками, которые стоят на местах (N – 1) и N. При любом сравнении «по силе» все школьники, включая Колю, показывают свою реальную силу, так как не хотят прослыть слабаками.

Для увеличения шансов поиграть в футбол, Коля хотел бы оказаться как можно левее в получившейся шеренге. Силу каждого из своих одноклассников он знает. По предыдущим занятиям Коля заметил, что если присесть «завязывать шнурки» при каком-либо из проходов учителя, то Иван Петрович во время такого прохода не будет просить Колю мериться силой ни с соседом слева, ни с соседом справа, и, тем более, не будет просить мериться силой соседей Коли, так как они не стоят рядом. Однако, чтобы сохранить силы для игры в футбол, Коля не может присесть более k раз.

Требуется написать программу, которая определит, как нужно действовать Коле, чтобы после проведения расстановки «по силе» оказаться в шеренге как можно левее.

Входные данные

В первой строке входных данных задаются три целых числа: N — число школьников в классе, p — место Коли в шеренге по росту, и k — количество приседаний, которое Коля может сделать, не потеряв при этом способность играть в футбол (2 ≤ N ≤ 100 000, 1 ≤ p ≤ N, 1 ≤ k ≤ N – 1).

Во второй строке задаются целые числа a1, a2, ..., aN (1 ≤ ai ≤ 109). Число ai показывает силу школьника, который стоит на i-м месте по росту. Школьник, который стоит на i-м месте в расстановке по росту, сильнее школьника, который стоит j-м месте в расстановке по росту, если ai > aj.

Выходные данные

В первой строке выведите самую левую позицию в шеренге, в которой может оказаться Коля после построения школьников «по силе». Во второй строке выведите любую из возможных стратегий Коли, приводящую к этому результату. Стратегия выводится в виде строки из (N – 1) символов, j-й символ этой строки должен быть равен символу «+», если на j-м проходе Коле необходимо присесть, и символу «-» — в противном случае.

Примечание

Решения, корректно работающие при N ≤ 3000, будут оцениваться, исходя из 70 баллов.

Примеры
Входные данные
10 5 6
10 1 8 3 6 5 4 7 2 9
Выходные данные
5
---++++++
#22
Ударим мостом по бездорожью
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Профиль Уральских гор задается ломаной (x1, y1), (x2, y2), …, (xN, yN), для координат вершин которой верны неравенства x1 < x2 < … < xN. Начальные и конечные точки профиля расположены на уровне моря (y1 = yN = 0).

На горном профиле заданы две различные точки A и B, между которыми требуется проложить дорогу. Эта дорога будет проходить по склонам гор и проектируемому горизонтальному мосту, длина которого не должна превышать L. Оба конца моста находятся на горном профиле. Дорога заходит на мост с одного конца и выходит с другого. Мост не может содержать точек, расположенных строго под ломаной (строительство тоннелей не предполагается).

Возможные примеры расположения моста

1

Невозможное расположение моста

2

Достоверно известно, что строительство такого моста в данной местности возможно, причем позволит сократить длину дороги из точки A в точку B. Требуется написать программу, которая определит такое расположение горизонтального моста, что длина дороги от точки A до точки B будет наименьшей.

Входные данные

Первая строка входных данных содержит два целых числа N и L — количество вершин ломаной (2 ≤ N ≤ 100 000) и максимальную длину моста (1 ≤ L ≤ 106) соответственно. Вторая строка  содержит координаты точки A, третья строка — координаты точки B. Точки A и B различны.

Последующие N строк содержат координаты вершин ломаной (x1, y1), (x2, y2), …, (xN, yN). Координаты вершин ломаной, а также точек A и B, задаются парой целых чисел, не превосходящих по абсолютному значению 106. Гарантируется, что x1 < x2 < … < xN и y1 = yN = 0, а также, что точки A и B принадлежат ломаной.

Выходные данные

В первой и второй строках выходных данных выведите координаты концов моста с точностью не менее 5 знаков после десятичной точки. В случае, когда решений несколько, выведите любое из них.

В примере в первой строке указана длина дороги от точки A до точки B с учётом построенного моста. Её не нужно выводить.

Примечание

Решения, корректно работающие при N ≤ 2000, будут оцениваться, исходя из 80 баллов.

Примеры
Входные данные
5 3
1 1
3 1
-1 0
0 2
2 0
4 2
5 0
Выходные данные
2.000000000
1.00000 1.00000
3.00000 1.00000
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест