Страница: << 78 79 80 81 82 83 84 >> Отображать по:

#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.

#3901

Золотые слитки

Источники: [ Командные олимпиады, Турнир Архимеда, 2011, Задача A ]

Дано N золотых слитков. Требуется распилить не более одного из них на две части (не обязательно равные, но с целой массой), после чего разделить слитки на две кучи равной массы.

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

В первой строке вводится одно натуральное число N, не превосходящее 100.

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

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

Выведите массы слитков, которые вошли в первую кучку (включая массу части распиленного слитка).

Если решений несколько, выведите любое из них.

Если решений нет, выведите фразу NO SOLUTION (заглавными буквами).

Выводить массы можно в произвольном порядке, но масса части распиленного слитка (если таковой имеется) должна быть последней.

Примеры

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

3
5 5 5

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

NO SOLUTION

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

4
1 2 3 8

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

1 2 3 1

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

4
1 2 3 8

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

1 2 3 1

#3902

Ежедневник

Темы: [Дата и время]

Источники: [ Командные олимпиады, Турнир Архимеда, 2011, Задача B ]

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

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

Вводится одно натуральное число i, не превышающее 2011.

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

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

Примеры

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

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

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

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

Страница: << 78 79 80 81 82 83 84 >> Отображать по:

Выбрано

Отменить

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