Задача A. Урок физкультуры ≡

Условие

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

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

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

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

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

Формат входного файла

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

Во второй строке задаются целые числа a₁, a₂, ..., a_N(1 ≤ ai ≤ 10⁹). Число a_i показывает силу школьника, который стоит на i-м месте по росту. Школьник, который стоит на i-м месте в расстановке по росту, сильнее школьника, который стоит j-м месте в расстановке по росту, если a_i > a_j.

Формат выходного файла

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

Примеры тестов

10 7 7
8 3 5 4 5 7 4 2 1 3

3
---++-+++

Задача B. Электрички на перегонах не меняют ≡

Условие

На пригородной железной дороге N станций и M соединяющих их перегонов. Любые две станции соединены не более чем одним перегоном. Сеть перегонов устроена так, что, отправившись от любой станции, можно вернуться на нее, только проехав хотя бы один перегон дважды. На железной дороге организовано движение электричек. Каждая электричка ходит в обоих направлениях по своему маршруту между двумя конечными станциями и останавливается на всех промежуточных станциях.

Для удобства пассажиров руководство железной дороги решило ввести новую систему оплаты проезда. По этой системе каждой станции присваивается некоторое целое число, называемое тарифным номером этой станции. Стоимость проезда между двумя станциями без пересадок определяется модулем разности тарифных номеров этих станций. Тарифные номера станций вдоль маршрута каждой электрички должны изменяться монотонно, то есть при движении в каком-либо направлении строго возрастать и, следовательно, строго убывать при движении в обратном направлении. Это обеспечивает рост стоимости проезда с увеличением количества пройденных перегонов.

Требуется написать программу, которая назначит каждой станции тарифный номер.

Формат входного файла

В первой строке входного файла содержатся два целых числа: N — количество станций (2 ≤ N ≤ 10⁵), и M — количество перегонов между ними (1 ≤ M ≤ N). В последующих M строках записаны пары целых чисел a, b (a ≠ b, 1 ≤ a ≤ N, 1 ≤ b ≤ N), означающие наличие перегона между станциями a и b. За ними в отдельной строке записано единственное целое положительное число K — количество маршрутов электричек. В последующих K строках идут описания маршрутов электричек, по одному на строке. Каждое описание представляет собой последовательность целых чисел — номеров всех станций маршрута в порядке одного из двух возможных направлений следования электрички. Описание маршрута заканчивается числом 0.

Все номера станций в описании маршрута различны. Количество станций в каждом маршруте не менее двух. Любые две последовательные станции в маршруте каждой электрички соединены перегоном. Суммарное количество станций в описаниях всех маршрутов не превосходит 2 × 10⁵. Могут быть станции и перегоны, через которые не проходит ни одна электричка.

Формат выходного файла

В первую строку выходного файла выведите NO, если искомого назначения тарифных номеров не существует. В противном случае в первую строку выведите YES, а в следующей строке — N целых положительных чисел, где i-е число — тарифный номер i-й станции. Тарифный номер каждой станции должен находиться в диапазоне от 1 до N.

Примеры тестов

4 3
1 4
2 4
3 4
3
1 4 2 0
2 4 3 0
3 4 1 0

NO

5 4
1 5
2 5
3 5
4 5
4
1 5 2 0
2 5 3 0
3 5 4 0
4 5 1 0

YES
1 4 1 5 3

Задача C. Ударим мостом по бездорожью ≡

Условие

Профиль Уральских гор задается ломаной (x₁, y₁), (x₂, y₂), …, (x_N, y_N), для координат вершин которой верны неравенства x₁ < x₂ < … < x_N. Начальные и конечные точки профиля расположены на уровне моря (y₁ = y_N = 0).

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

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

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

Формат входного файла

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

Последующие N строк содержат координаты вершин ломаной (x₁, y₁), (x₂, y₂), …, (x_N, y_N). Координаты вершин ломаной, а также точек A и B, задаются парой целых чисел, не превосходящих по абсолютному значению 10⁶. Гарантируется, что x₁ < x₂ < … < x_N и y₁ = y_N = 0, а также, что точки A и B принадлежат ломаной.

Формат выходного файла

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

Примеры тестов

4 6
13 0
2 1
1 0
5 4
11 -2
13 0

13.00000 0.00000
9.00000 0.00000

6 8
3 -6
11 -2
0 0
4 -8
6 -4
7 -4
9 -6
12 0

2.00000 -4.00000
10.00000 -4.00000

Задача D. Теория цифр ≡

Условие

Юный информатик стал исследовать, как изменяются суммы цифр натуральных чисел при умножении и делении на разные однозначные числа. Однажды он задался вопросом, можно ли восстановить число A, если нам известна сумма его цифр, а также сумма цифр числа DA, где D — заданное однозначное число. Довольно быстро он установил, что для восстановления числа А этой информации недостаточно. Так, например, у чисел 9 и 45 одинаковые суммы цифр. Если же их умножить на 5, то получим числа 45 и 225, которые тоже имеют одинаковые суммы цифр.

Тогда юный информатик стал искать ответ на поставленный вопрос при условии, что нам известно K — количество десятичных знаков в числе A. К сожалению, и тут его ждало разочарование. У некоторых чисел, имеющих одинаковое количество цифр и одинаковые суммы цифр, после умножения на один и тот же множитель эти суммы опять оказываются одинаковыми. Такими числами, например, являются 42 и 51 при D = 3.

И тогда юный информатик поставил перед собой такую задачу: найти наименьшее K-значное натуральное число A в десятичной системе счисления, которое имеет сумму цифр, равную S, а число DA имеет сумму цифр, равную P.

Требуется написать программу, решающую поставленную задачу.

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

Формат входного файла

Во входном файле заданы четыре натуральных числа K, S, P, D(1 ≤ K ≤ 100, 1 ≤ S ≤ 9 K, 1 ≤ P ≤ 9(K+1), 1 ≤ D ≤ 9).

Формат выходного файла

Выведите в выходной файл число A, если оно существует, или −1, в противном случае. Число A не может начинаться с нуля.

Примеры тестов

2 9 9 5

18

2 8 10 3

-1

Задача E. Интернет на черный день ≡

Условие

В городе Шахматовске два интернет-провайдера выполняют план по всеобщей интернетизации страны. Город расположен на бесконечной целочисленной решетке, по всем линиям которой проходят прямые улицы, а единичные квадраты сетки определяют кварталы. Координатами квартала считаются координаты вершины левого нижнего угла соответствующего единичного квадрата. Кварталы города окрашены в черный и белый цвета в шахматном порядке, при этом квартал с координатами (0, 0) окрашен в черный цвет.

Интернет-провайдер "Черный интернет" занимается подключением кварталов черного цвета. Недавно стало известно, что жителям квартала, подключенного K-м, будет предоставлена скидка в 10%.

В соответствии с планом компании "Черный интернет" интернетизация будет проводиться в течение N дней. В i-й день бригада сотрудников компании движется по какой-то из улиц города, начиная из точки (x_i, y_i). Бригада проходит l_i кварталов в заданном направлении. При этом она подключает ранее не подключенные кварталы черного цвета, граничащие по стороне с путем движения бригады (см. рис.).

Требуется написать программу, которая определит координаты квартала, подключенного во время реализации плана K-м по очереди. Гарантируется, что в процессе реализации плана будет подключено не менее K кварталов.

Формат входного файла

В первой строке входного файла заданы два целых числа N и K (1 ≤ N ≤ 2000, 1 ≤ K ≤ 10¹⁸).

Далее следуют N строк с описанием плана развития компании. В i-й строке описания плана записан путь бригады в i-й день: x_i и y_i (−10¹⁵?y_i, x_i?10¹⁵) — координаты начальной точки пути, символ c_i — направление движения, и l_i (1 ≤ l_i ≤ 10¹⁵) — расстояние, которое пройдет бригада. Направление движения задается одним из следующих символов: "N" — север (по увеличению y-координаты), "E" — восток (по увеличению x-координаты), "S" — юг (по уменьшению y-координаты), "W" — запад (по уменьшению x-координаты).

Формат выходного файла

Выведите в выходной файл координаты x и y квартала, подключенного K-м.

Примеры тестов

4 10
2 0 N 5
2 3 E 3
4 3 S 2
0 1 E 5

4 0

4 7
-1 0 E 4
-1 1 E 4
-1 0 E 4
-1 -1 E 4

0 -2

Задача F. То березка, то рябина... ≡

Условие

В целях улучшения ландшафтной архитектуры и экологической обстановки управление городского хозяйства разработало проект программы озеленения центрального проспекта. Согласно проекту с одной стороны проспекта планируется высадить в ряд деревья K различных видов, для чего были закуплены саженцы деревьев, причем i-го вида было закуплено a_i саженцев.

Для достижения эстетического совершенства высаживаемого ряда деревьев требуется, чтобы среди любых P подряд идущих деревьев все деревья были разных видов. Если количество деревьев в ряду меньше P, то все они должны быть различны.

Требуется написать программу, которая находит максимальное количество деревьев в эстетически совершенном ряду, посаженном из закупленных саженцев.

Формат входного файла

Первая строка входного файла содержит два целых числа: K — количество различных видов деревьев (1 ≤ K ≤ 10⁵), и P — требуемое количество подряд идущих деревьев разных видов (2 ≤ P ≤ K). Последующие K строк входного файла содержат целые числа a_i — количество закупленных саженцев деревьев i-го вида ($1 \le a_i \le 10^9), по одному числу в каждой строке.

Формат выходного файла

Выходной файл должен содержать единственное число — максимальное количество деревьев, посадка которых в ряд в некотором порядке достигает эстетического совершенства.

В приведенном примере деревья можно высадить, например, в следующем порядке: 2, 4, 3, 1, 2, 3, 1, 2.

Примеры тестов

4 3
2
5
2
1

8