Страница: << 101 102 103 104 105 106 107 >> Отображать по:

#111981

Защищенное соединение

Источники: [ Командные олимпиады, ВКОШП, 2013, Задача H ]

В свете недавних новостей о прослушке каналов связи, два непримиримых интернет-гиганта Урагании «Laim.UR» и «Xenda» решили подписать соглашение об установлении защищенного канала связи между дата-центрами друг друга. В Урагании \(n\) городов, но, к сожалению, ни в одном городе нет дата-центров обоих гигантов. Поэтому для формирования защищенного канала придется прокладывать междугородние линии связи.

Специалисты компаний определили \(m\) пар городов, которые можно соединить, проложив сегмент канала связи, и оценили стоимость создания такого сегмента для каждой из этих пар.

Результирующий канал может состоять из нескольких сегментов. Он должен начинаться в одном из городов, где находится дата-центр первой компании, может проходить через промежуточные города и должен заканчиваться в городе, где находится дата-центр второй компании.

Теперь необходимо определить минимальную стоимость защищенного канала, соединяющего два дата-центра компаний.

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

В первой строке находятся целые числа \(n\) и \(m\) (\(2 \le n \le 5\,000\), \(1 \le m \le 10^5\)) - количество городов и количество пар городов, которые можно соединить сегментом канала связи.

Во второй строке находятся \(n\) целых чисел \(a_i\) (\(0 \le a_i \le 2\)). Если \(a_i = 0\), то в \(i\)-м городе нет дата-центра ни одного из гигантов. Если \(a_i = 1\), то в \(i\)-м городе есть дата-центр «Laim.UR», а если \(a_i = 2\), то в \(i\)-м городе находится дата-центр «Xenda». Гарантируется, что среди этих чисел есть как минимум одна единица и одна двойка.

В каждой из следующих \(m\) строк находится по три целых числа - \(s_i\), \(t_i\) и \(c_i\), которые означают, что города \(s_i\) и \(t_i\) (\(1 \le s_i, t_i \le n\), \(s_i \ne t_i\)) можно соединить сегментом канала связи стоимостью \(c_i\) (\(1 \le c_i \le 10^5\)). Каждую пару городов можно соединить не более чем одним сегментом канала.

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

Если соединить защищенным каналом связи два дата-центра разных интернет-гигантов возможно, то выведите в выходной файл три числа: \(x\), \(y\) и \(d\), означающие, что между городами \(x\) и \(y\) возможно провести канал связи суммарной стоимостью \(d\). В городе \(x\) должен находиться дата-центр «Laim.UR», в городе \(y\) - дата-центр «Xenda». Если существует несколько оптимальных ответов, выведите любой. Если провести искомый канал невозможно, выведите \(-1\).

Пояснение к примерам

В первом примере оптимально построить канал связи из двух сегментов: \(3-2\) и \(2-4\).

Примеры

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

6 7
1 0 1 2 2 0
1 3 3
1 2 4
2 3 3
2 4 2
1 6 5
3 5 6
5 6 1

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

3 4 5

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

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

-1

#111982

Перетягивание каната

Источники: [ Командные олимпиады, ВКОШП, 2013, Задача I ]

В 2086 году в программу зимней олимпиады решено было добавить соревнования по перетягиванию каната на льду. Для проведения финала соревнования организаторы нашли \(n\) кусков каната. Для повышения зрелищности соревнования решено было сделать связать некоторые из этих кусков в один как можно более длинный канат.

Когда начались работы по связыванию, выяснилось, что на узел, связывающий два куска каната между собой, уходит по \(d\) сантиметров каната с каждого из связываемых концов. Также, оказалось, что связывать так, что получающиеся узлы находятся близко друг к другу, невозможно: расстояние между соседними узлами должно быть хотя бы \(d\) сантиметров. Например, если \(d = 10\), то после связывания кусков каната длиной 25 и 50 сантиметров, получается канат длиной 55 сантиметров, в 15 сантиметрах от одного из краев которого находится узел.

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

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

В первой строке заданы числа \(n\) (\(1 \le n \le 100\,000\)) и \(d\) (\(1 \le d \le 1000\)) - количество кусков каната и длина каната, уходящая на завязывание узла.

Во второй строке заданы \(n\) чисел \(a_i\) (\(1 \le a_i \le 1000\)) - длины имеющихся кусков каната.

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

Выведите единственное число- максимальную длину каната, которую можно получить.

Примеры

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

2 10
25 50

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

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

5 2
4 5 6 7 8

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

#111983

Загранпаспорт

Источники: [ Командные олимпиады, ВКОШП, 2013, Задача J ]

Осень 2243-го года. Государства в прошлом, главным территориальным образованием является автономия. В результате терраформирования территория бывшей Евразии теперь представляет собой прямоугольник, он разбит на \(w \times h\) квадратных автономий, которые организованы в виде сетки из \(w\) автономий по ширине и \(h\) по высоте. Некоторые автономии входят в содружество Крипто, они представляют собой криптоанархистские технократические общества и не признают бюрократии. Остальные автономии входят в конфедерацию Бюрро, бюрократия в них доведена до высшего совершенства.

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

Опытный путешественник по имени Вениамин хочет получить загранпаспорт нового образца. Чтобы это сделать досрочно, ему нужно заполнить все страницы своего старого паспорта штампами пограничных служб. На данный момент у него осталось \(n\) пустых страниц, соответственно ему нужно ровно \(n\) раз въехать в автономию Бюрро. Он хочет сделать это как можно быстрее.

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

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

В первой строке входного файла содержатся три целых числа: \(w\), \(h\) и \(n\) (\(1 \le w, h \le 500\), \(1 \le n \le 1\,000\)).

В каждой из следующих \(h\) строк содержится по \(w\) символов, они задают карту Евразии. Символ «Arlaquo обозначает автономию содружества Крипто, а «T» - автономию конфедерации Бюрро. Автономия, в которой Вениамин начинает свое путешествие, обозначена символом «V».

Карта дана с севера на юг по строкам и с запада на восток по столбцам, таким образом, первый символ второй строки входного файла описывает самую северо-западную автономию.

Гарантируется, что в Евразии есть хотя бы одна автономия Бюрро.

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

В выходной файл выведите одну строку из символов «N», «E», «S», «W» - план путешествия Вениамина. Эти символы означают, что Вениамину следует поехать на север, восток, юг или запад, соответственно. Число перемещений в плане необходимо минимизировать, в процессе путешествия Вениамин должен ровно \(n\) раз въехать в автономию Бюрро. Если возможных оптимальных планов путешествия несколько, можно вывести любой.

Примеры

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

5 3 6
AAATA
VAATA
AAAAT

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

EEENSNSN

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

3 1 2
TVT

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

WEW

#111984

Вирус

Источники: [ Командные олимпиады, ВКОШП, 2013, Задача K ]

В лаборатории биоинформатики ученые проводят эксперименты по распространению искусственно созданных вирусов. Для эксперимента используется специальная лабораторная установка, представляющая собой таблицу из \(n \times m\) ячеек. В каждую ячейку помещается живая клетка. Ученые заражают вирусом некоторые клетки, всего исходно заражается не более 8 клеток.

Каждую секунду среди незараженных клеток, имеющих зараженную клетку в соседней по стороне ячейке, ровно одна клетка заражается вирусом.

Ученые заинтересовались, какие конфигурации зараженных клеток могут получиться через \(t\) секунд. Для начала они хотят посчитать число таких конфигураций. Помогите им это сделать.

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

В первой строке входного файла находятся целые числа \(n\), \(m\) и \(t\) (\(1 \le n, m \le 100\), \(1 \le t \le 6\)) - размеры таблицы и количество секунд.

Каждая из следующих \(n\) строк содержит \(m\) символов. Символ <<.>> означает, что в изначальной конфигурации клетка не заражена, а символ <<*>> - что заражена. Количество <<*>> в таблице не превышает 8.

Гарантируется, что незараженных клеток в исходной конфигурации не меньше \(t\).

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

Выведите количество различных возможных конфигураций таблицы после \(t\) секунд.

Примеры

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

2 2 1
*.
..

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

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

2 2 2
*.
..

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

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

2 2 3
*.
..

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

#112685

Янтарный шарик

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2014, Лига А, Задача A ]

Янтарный шарик падает на землю, встречая на своём пути перегородки. Введём стандартную двумерную систему координат таким образом, что земля будет представлять собой ось \(O_x\), а сила тяжести действует в отрицательном направлении оси \(O_y\). Перегородки представляют собой отрезки, а шарик — точку. Попадая на перегородку (даже в её самой верхней точке), шарик скатывается по ней и продолжает падение вертикально вниз (иными словами, горизонтальная составляющая скорости шарика мгновенно исчезает по достижении конца перегородки). Среди перегородок нет ни вертикальных, ни горизонтальных, все они находятся строго над уровнем земли, и никакие две перегородки не имеют общих точек. Таким образом, рано или поздно шарик достигнет земли в некоторой точке.

Шарик несколько раз запускают с разных стартовых позиций. Для каждого запуска требуется найти x-координаты точки соприкосновения шарика с землёй.

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

В первой строке содержится число N (0 <= N <= 3 * \(10^5\)) — количество перегородок.

Каждая из последующих \(N\) строк содержит описание очередной перегородки — четыре числа \(x_1\), \(y_1\), \(x_2\), \(y_2\) (\(x_1\) < \(x_2\), \(y_1\) ̸= \(y_2\), \(y_1\); \(y_2\) > 0): (\(x_1\); \(y_1\)) — координаты левого конца перегородки, (\(x_2\); \(y_2\)) — координаты правого конца.

В следующей строке содержится число M (1 <= M <= 3 * \(10^5\)) — количество запусков шарика.

Далее следуют \(M\) строк, в каждой из которых записано одно целое число — \(x\)-координата позиции, с которой производится запуск. Гарантируется, что \(y\)-координата стартовой позиции превосходит \(y\)-координаты концов всех перегородок.

Все координаты во входном файле — целые числа, не превосходящие \(10^6\) по модулю. Гарантируется, что среди перегородок нет вертикальных и горизонтальных, перегородки не имеют общих точек, длина каждой перегородки строго больше нуля.

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

Для каждого запуска выведите на отдельной строке единственное число — x-координату точки соприкосновения шарика с землёй.

Note

Изображение в условии соответствует третьему примеру входных данных.

Примеры

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

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

2
3

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

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

-1
-4
-1

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

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

Страница: << 101 102 103 104 105 106 107 >> Отображать по:

Выбрано

Отменить

Добавить в контест