Страница: << 1 2 Отображать по:

#3693

Домашнее задание

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2009, Задача F ]

Сережа очень не любит делать домашние задания, но на последнем уроке информатики учитель задал классу n разных домашних заданий. Причем некоторые домашние задания можно делать только после того, как сделаны некоторые другие.

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

Помогите Сереже выбрать задание, которое можно не делать, чтобы закончить все остальные задания как можно быстрее.

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

Первая строка входного файла содержит целые числа n и m — количество заданий и количество зависимостей между заданиями (1 ≤ $n$ ≤ 100, 0 ≤ $m$ ≤ 1000). Вторая строка содержит n целых чисел: $t_1$, $t_2$, ... , $t_n$. Число $t_i$ означает количество минут, необходимое Сереже для выполнения $i$-го задания (1 ≤ $t_i$ ≤ 1000).

Затем следует m строк, каждая строка содержит два целых числа. Числа $a$ и $b$ означают, что задание $a$ должно быть выполнено до задания $b$. Гарантируется, что все задания можно выполнить.

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

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

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

В приведенном примере Сережа может не выполнять четвертое задание. Остальные задания суммарно требуют 11 минут.

Примеры

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

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

#3694

Москва 2042

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2009, Задача G ]

К 2042 году правительство Москвы завершило очередной масштабный проект, доведя количество кольцевых автодорог до $n$. Теперь у автомобилиста еще больше способов постоять в пробке в попытке добраться от одной точки города до другой

Компания «Giggle» планирует в своем новом продукте «Giggle Maps» реализовать возможность проложить оптимальный маршрут от одного перекрестка до другого. Карта Москвы во внутреннем формате программы представляет собой набор из $m$ радиальных и $n$ кольцевых магистралей, при этом некоторые из кольцевых магистралей являются односторонними.

В математической модели «Giggle» все кольцевые магистрали представляют собой концентрические окружности с центром на Красной площади и радиусами $r_1$, $r_2$, ..., $r_n$. Радиальные магистрали представляют собой отрезки, один из концов каждого отрезка лежит на Красной площади, а другой — на кольцевой магистрали с максимальным радиусом. Если встать на Красной площади и смотреть на восток, то, чтобы посмотреть в направлении j-ой радиальной магистрали, нужно повернуться против часовой стрелки на $a_j$ градусов. По каждой из радиальных магистралей можно ехать в любом направлении. Кольцевые магистрали, в свою очередь, бывают как двусторонними, так и односторонними.

Помогите компании «Giggle» найти кратчайший путь от перекрестка где пересекаются $i_s$-я кольцевая и $j_s$-я радиальная магистраль до перекрестка, где пересекаются $i_t$-я кольцевая и $j_t$-я радиальная магистраль. При этом проезжать через Красную площадь не разрешается

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

Первая строка входного файла содержит целые числа $n$ и $m$ (1 ≤ $n$, $m$ ≤ 100 000).

Следующие n строк описывают кольцевые магистрали. Каждая магистраль описывается целым числом $r_i$ (1 ≤ $r_i$ ≤ $10^6$) и числом 0, если магистраль является двусторонней, 1, если по ней разрешено движение только против часовой стрелки (в сторону увеличения углов радиальных магистралей) или −1, если по ней разрешено движение только по часовой стрелке.

Следующие m строк описывают радиальные магистрали. Каждая магистраль описывается одним целым числом $A_j$ , причем $a_j$ = $A_j$/$10^6$ (0 ≤ $A_j$ < 360 · $10^6$).

Затем следует две строки: первая из них содержит числа $i_s$ и $j_s$, а вторая — числа $i_t$ и $j_t$

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

Выведите в выходной файл одно вещественное число: минимальное расстояние, которое придется проехать, чтобы попасть с перекрестка где пересекаются $i_s$-я кольцевая и $j_s$-я радиальная магистраль на перекресток, где пересекаются $i_t$-я кольцевая и $j_t$-я радиальная магистраль. Ваш ответ должен отличаться от правильного не больше чем на 10⁻⁴.

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

$\text{[math]}$

Примеры

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

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

12.99557428756427600000

#3695

Морской бой

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2009, Задача H ]

Недавно Вова купил настольную игру «Морской бой». Это пошаговая игра для двух игроков, действие которой разворачивается на просторах бесконечного клетчатого поля. У каждого из игроков есть свой флот, который состоит из нескольких кораблей. Каждый корабль занимает ровно одну клетку поля. Флот каждого из игроков движется по полю с постоянной скоростью — все корабли i-ого игрока каждые ti шагов перемещается на вектор (∆$x_i$, ∆$y_i$). Таким образом, корабли i-ого игрока перемещаются по полю на шагах с номерами 1, $t_i$ + 1, 2 · $t_i$ + 1 и.т.д.

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

$\text{[math]}$

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

Входной файл содержит описания флотов двух игроков. Описание флота состоит из нескольких строк. Первая строка описания содержит четыре целых числа: $m_i$ (1 ≤ $m_i$ ≤ 10000) — число кораблей во флоте $i$-ого игрока, а так же $t_i$ (1 ≤ $t_i$ ≤ 10), ∆$x_i$, ∆$y_i$ (|∆$x_i$|, |∆$y_i$| ≤ 10).

Затем следуют $m_i$ строк, каждая из которых содержит по два целых числа — $x_j$ и $y_j$ (|$x_j$|, |$y_j$ | ≤ $10^9$) — координаты кораблей во флоте до первого шага игры.

Никакие два корабля, описанные во входном файле, не находятся в начальный момент времени в одной и той же клетке.

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

В выходной файл необходимо вывести номер шага, на котором произойдет первый бой. Если бой никогда не состоится, выведите в выходной файл -1

Примеры

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

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

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

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

-1

#3696

Станция «Сортировочная»

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2009, Задача I ]

На железнодорожной станции «Сортировочная» на пути находятся $n$ товарных вагонов, из которых необходимо сформировать состав. Все вагоны имеют одинаковую длину, однако в них размещены различные грузы, поэтому вагоны могут иметь разную массу. Работники железнодорожной станции «Сортировочная» должны выстроить вагоны в порядке возрастания масс — тогда составу будет разрешено отправиться в путь.

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

Это устройство на воздушной подушке перемещается над вагонами, его длина немного превышает длину двух вагонов. Оно может зависнуть над двумя соседними вагонами, поднять их оба в воздух и поменять местами. Однако, грузоподъемность устройства ограничена — указанную операцию оно может выполнить только, если суммарная масса двух вагонов не превышает $M$

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

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

Первая строка входного файла содержит два числа: число вагонов $n$ (2 ≤ $n$ ≤ 100 000) и грузоподъемность экспериментального устройства $M$ (1 ≤ $M$ ≤ $10^9$). Вторая строка входного файла содержит массы вагонов $m_1$, ..., $m_n$ (для этих масс выполняются неравенства 1 ≤ $m_i$ ≤ $10^9$, кроме этого массы вагонов попарно различны). Массы вагонов перечислены во входном файле в том порядке, в котором вагоны исходно стоят на пути.

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

В выходной файл выведите слово «Yes», если с помощью экспериментального устройства для сортировки вагонов можно расставить вагоны в необходимом порядке, и слово «No» — иначе.

Примеры

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

4 10
5 6 3 4

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

Yes

#3697

Википедия

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2009, Задача J ]

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

Для начала он взял несколько текстов из «Encyclopedia Britannica» и набрал их. Теперь он хочет расставить внутри статей ссылки на другие статьи. Однако статей очень много, поэтому он решил автоматизировать процесс.

Ссылка на статью на вики-странице устроена следующим образом:

«[[Название статьи|текст ссылки]]».

Например, во фразе «In the wild cats are often enemies of [[Dog|dogs]].» слово «dogs» будет ссылкой на статью «Dog». Если название статьи совпадает с текстом ссылки, можно ссылку можно оформить просто как

«[[Название статьи]]»

Например, во фразе «Growing together a [[dog]] and a cat can often be friends.» слово «dog» будет ссылкой на статью «dog». При этом в названиях статей регистр первой буквы игнорируется, а регистр остальных букв важен. Например, слово «dog» может быть ссылкой на статью «Dog», а слово «DOG» — нет

Помогите Пете расставить ссылки на его сайте. Сайт представляет собой множество статей. Каждая статья имеет название — одно слово, и текст. Для слова названия известны все его словоформы и синонимы.

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

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

Первая строка входного файла содержит число $n$ — количество статей в Петиной википедии (2 ≤ n ≤ 50). Далее следуют описания статей

Описание каждой статьи начинается со строки, которая содержит название этой статьи. Далее следует строка, содержащая одно число $k$ — количество словоформ и синонимов к названию статьи, это число не превышает 10. Следующие k строк содержат по одному слову на строке — словоформы и синонимы к названию текущей статьи. Далее следует строка, содержащая число l — количество строк в тексте статьи, это число не превышает 10. Затем следует текст статьи — l строк, каждая из которых имеет длину не более 80 символов.

Все названия статей различны. Все словоформы и синонимы всех названий различны и отличаются от названий статей.

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

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

Выведите в выходной файл версии статей с расставленными ссылками. Выводите статьи следующим образом. Сначала выведите название статьи. Затем выведите текст статьи, разбитый на строки также как и во входном файле. Все слова в тексте, которые совпадают с названием статьи, или со словоформой или синонимом названия статьи, отличной от той, в которой они встречаются, следует превратить в ссылки. При сравнении слов следует игнорировать регистр первой буквы, но соблюдать регистр остальных. Слова, совпадающие с названием, следует превратить в краткую версию ссылки, а не совпадающие — в полную.

Примеры

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

2
Cat
2
Kitten
Cats
3
Cat is one of the most common pets, together with dogs.
In the wild cats are often enemies of dogs.
Growing together a dog and a cat can often be friends.
Dog
1
Dogs
2
Dog is one of the most common pets, together with cats.
DOG can also be an abbreviation.

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

Cat
Cat is one of the most common pets, together with [[Dog|dogs]].
In the wild cats are often enemies of [[Dog|dogs]].
Growing together a [[dog]] and a cat can often be friends.
Dog
Dog is one of the most common pets, together with [[Cat|cats]].
DOG can also be an abbreviation.

Страница: << 1 2 Отображать по:

Выбрано

Отменить

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