Страница: << 14 15 16 17 18 19 20 >> Отображать по:

#3692

Куб

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

Сегодня на уроке геометрии Маша и Паша изучали геометрические тела. Одним из самых простых геометрических тел является куб. Обозначим четыре вершины нижней грани куба в порядке обхода как $A$, $B$, $C$ и $D$, а четыре вершины верхней грани куба, находящиеся над ними, как $A_1$, $B_1$, $C_1$ и $D_1$, соответственно.

$\text{[math]}$

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

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

Входной файл содержит две строки. Первая строка содержит названия вершин, которые являются концами первого отрезка, а вторая — названия вершин, которые являются концами второго отрезка. Названия не разделены пробелом, вершины $A_1$, $B_1$, $C_1$ и $D_1$ задаются как «$A_1$», «$B_1$», «$C_1$» и «D1» соответственно.

Отрезки, заданные во входном файле не совпадают. Начало и конец у каждого отрезка не совпадают.

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

Выведите в выходной файл «Yes», если отрезки пересекаются, или «No», если нет.

Примеры

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

AA1
A1C

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

Yes

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

AD
A1C1

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

No

#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

Страница: << 14 15 16 17 18 19 20 >> Отображать по:

Выбрано

Отменить

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