Задача A. Навигационные спутники Васи ≡

Условие

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

Для ведения своих расчётов Вася использует сферическую систему координат (r,φ, ψ), где r >  = 0 – расстояние от точки до начала координат, φ ∈ [ − 90^∘,90^∘] - зенитный угол, ψ ∈ [0^∘,360^∘] - азимутальный угол. Направления изменения углов показаны на рис. 1 и рис. 2.

В качестве модели Земли Вася взял идеальную сферу с уравнением r = 100 в сферических координатах. Поскольку первая координата зафиксирована, то каждая точка на поверхности будет описываться парой (φ,ψ).

Спутники Васи располагаются на k орбитах. Каждая i − ая орбита представляет из себя пространственную окружность радиуса R_i с центром в начале координат, лежащую в плоскости, заданной нормальным вектором n⃗ = (r_n,φ_n,ψ_n). На каждой орбите находится m_i точечных спутников, равноудалённых друг от друга. В начальный момент времени t₀ = 0 первый спутник расположен в координатах (R_i,φ_i1,ψ_i1); все спутники вращаются против часовой стрелки, если посмотреть на плоскость орбиты со стороны нормали n⃗, и пронумерованы последовательно от первого спутника, начиная с 1. Каждый спутник на орбите совершает полный оборот за время t_i.

Вася хочет написать программу, которая смогла бы оценить удачность выбранной системы спутников и расположения орбит. Для этого он выбирает целевую точку на поверхности сферы с координатами (φ_p,ψ_p) на сфере и пытается выяснить, сколько спутников в момент времени t будут находится на связи с целевой точкой. Будем говорить, что некоторый спутник находится на связи с целевой точкой, если отрезок, соединяющий спутник и целевую точку не пересекает сферу.

Помогите Васе написать такую программу.

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

В первой строке находится 2 числа φ_p и ψ_p – координаты целевой точки на поверхности сферы
Во второй строке находится число t – время для изучения положения спутников.
В третьей строке находится число k – количество орбит. Орбиты пронумерованы, начиная с 1, в порядке их появления.
Для каждой i − ой орбиты даны следующие данные:

• Число m_i – количество спутников на i − ой орбите;
• Числа r_n, φ_n, ψ_n - координаты вектора нормали плоскости вращения орбиты;
• Числа R_i, φ_i1, ψ_i1 – координаты первого спутника на орбите;
• Число t_i – время полного оборота каждого спутника орбиты.

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

Выходной файл содержит число k_v – число спутников, находящихся на связи с целевой точкой в момент времени t.
Далее следуют k_v строк, содержащих 2 числа – номера орбит и порядковых номеров спутников на этих орбитах, находящихся на связи с целевой точкой в порядке возрастания обоих значений.
Если на связи нет ни одного спутника – выведите 0.

Ограничения

Гарантируется, что координаты первых спутников орбит лежат в их плоскостях вращения.
Гарантируется, что R_i > 100 для любого i ∈ {1,…,k}

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

90 0
0
1

2
1 0 0
150 90 0
1

1
1 1

45 45
5
2

4
1 0 0
150 90 0
10

3
1 0 90
200 45 0
8

2
1 3
2 2

Задача B. Траектория космического аппарата ≡

Условие

Из начала координат запускают исследовательский аппарат, который должен достичь небесного тела,
движущегося по циркулярной орбите вокруг некоторого неподвижного центра.

Из-за больших масштабов размеры аппарата и целевого объекта можно считать незначительными.
В этом случае будем рассматривать их как две материальные точки.

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

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

Траектория небесного тела задается вектором, ортогональным к плоскости вращения N⃗ = (N_x, N_y, N_z),
координатами неподвижного центра (C_x, C_y, C_z), начальной точкой (P_x, P_y, P_z) и угловой скоростью Ω.

Движение происходит против часовой стрелки в правой системе координат, порожденной вектором N⃗ .

Известно, что до момента посадки аппарат не способен маневрировать, а также менять свою скорость.

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

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

Задачу следует решить для серии запросов из различных небесных тел.

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

В начале входного файла хранится целое число n, за которым следует набор из n запросов,
каждый из которых задается набором вещественных чисел:
N_x, N_y, N_z, C_x, C_y, C_z, P_x, P_y, P_z, Ω, V.

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

Выходной файл должен содержать ответы на каждый входной запрос,
которые должны включать в себя координаты точки орбиты
(D_x, D_y, D_z), в направлении которой
должен быть запущен аппарат,
указанные с точностью до 5-го знака после запятой.

Ограничения

 − 10 ≤ (N_x, N_y, N_z) ≤ 10,  − 10 ≤ (C_x, C_y, C_z) ≤ 10,
1 ≤ |P − C| ≤ 10, 10^− 1 ≤ (Ω, V) ≤ 10,
1 ≤ n ≤ 10⁴.

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

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

1
 1.00000  1.00000  1.00000
 2.00000 -1.00000  0.00000
 2.00000  0.00000 -1.00000
 0.50000
 2.00000

1.52932 0.14849 -0.67781

Задача C. Нервный друг ≡

Условие

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

Когда Вася заикается, он повторяет букву через дефис. А когда он чихает, он издает звук «atishoo», и слово, которое он начал произносить, становится не разобрать, и вы его игнорируете.

Формат входных данных

На вход программе подаётся одна строка S длины L - речь, которую вы услышали от Васи.

Формат выходных данных

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

Ограничения

0 < L ≤ 10⁵

A < S[i] ≤ z + !′,

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

Hel-l-l-llo w-w-woratishoowo-orl-ld

Hello world

L-La-a-atisho-o-o-ooLol-l-l

Lol

atishatisho-o-ooooh, f-futur-r-re self, please don'tatishooforgi-iv-ve me and do-o no-o-o-o-ot hit me with the baseball bat again-n!

ooh, future self, please forgive me and do not hit me with the baseball bat again!

Задача D. Мужики и яма ≡

Условие

n строителей несут одну балку. И вдруг перед ними оказываются k ям. Строители, не долго думая, двинулись прямиком через эти ямы.

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

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

Благо яма не глубокая, поэтому все отделаются легким испугом.

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

Формат входных данных

Первая строка входного файла содержит два числа: n количество строителей, k количество ям.

Вторая строка список координат относительно начала балки строителей и их веса: p₁, w₁, ..., p_n, w_n. Координаты рабочих считаются от левого конца балка

Третья строка координаты краёв ям: l₁, r₁, ..., l_k, r_k.

Формат выходных данных

Выходной файл должен содержать одно число - количество упавших строителей.

Ограничения

0 < N * K ≤ 10⁶

0 < l_i, r_i ≤ 10⁹

0 < p_i,  < p_i + 1 ≤ 10⁹

1 < ∑w_i ≤ 10⁹

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

3 1
0 1 1 1 2 1
1 1

0

3 1
0 1 1 3 2 1
1 1

1

Задача E. Роботы ДПС ≡

Условие

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

Каждую машину можно отнести к одному из типов нарушений. (Например «машина, превысившая скорость», «машина с выключенными фарами»)

Также всегда существует тип «машина без нарушений», который означает что машину оштрафовать не за что.

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

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

За километр до поста установлена скрытая камера, поэтому вы заранее знаете в какой последовательности и какого типа машины проедут через ваш пост.

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

Список нарушений, которые могут вам встретиться: speed - Превышение скорости. headlights - Езда с выключенным светом. phone - Использование телефона во время управления авто. walker - Не пропустил пешехода. belt - Не пристёгнут ремень безопасности.

Формат входных данных

Первая строка входного файла содержит два числа: N, K - Количество машин, которые проедут через пост, Количество машин, необходимое для смены режима камеры.

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

Сначала одно число M - количество нарушений у машины, затем перечисляются сами нарушения

Формат выходных данных

Выходной файл должен содержать одно целое число - максимальное количество штрафов, которое сможет сделать робот.

Ограничения

0 < N, K ≤ 10⁶

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

5 1
2 speed headlights
1 speed
1 phone
1 headlights
1 headlights

4

6 1
1 speed
0
1 phone
1 phone
0
1 headlights

4