Задачи командных соревнований PRIME TIME 2024
1. Сумма квадратов простых чисел
Ограничения: время – 800ms/1600ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В 1770 году Варинг предположил, что для каждого натурального числа `k` существует
некоторое `s` такое, что любое натуральное число может быть представлено в виде суммы не более чем `s`
`k`-х степеней некоторых натуральных чисел. Например, любое натуральное число можно представить как сумму не более 4 квадратов или 9 кубов
или 19 четвертых степеней. Эта гипотеза была доказана Гильбертом в 1909 году.
Более сложной проблемой является представление натурального числа в виде суммы `k`-х степеней простых чисел.
Даже предположение Гольдбаха, что любое число, большее 1, можно представить в виде суммы не более чем 3 простых чисел (для `k=1`),
было доказано только в 2013 году.
Математик Гэри Селдон доказал в 12010 GE (23596 году), что любое число, большее 23, можно представить в виде суммы не более 8 квадратов простых чисел.
Напишите программу, которая находит представление заданного числа из минимального количества квадратов простых чисел.
Первая строка ввода содержит одно целое число `N` (`24<=N<=10^7`).
Вывести в первой строке одно целое число `K` (`1<=K<=8`) -- минимальное количество слагаемых.
Во второй строке вывести `K` простых чисел, сумма квадратов которых равна `N`.
Если существует несколько вариантов для такого представления, то можно вывести любой вариант из них, в любом порядке.
```sample Пример ввода
1001
```
```sample Пример вывода
6
2 3 3 3 3 31
```
2. Dice
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Cleon rolls a regular six faced dice `N` times.
He starts with an initial score of 0.
Let the number rolled by him in a particular round be `X`.
If Cleon rolls the number `X` `k` times in a row, he will add `k*X` to his score.
For example, if Cleon rolls 1,2,2,2,5,2, he gets `1+2+2*2+3*2+5+2=20` points.
Calculate the Cleon's score after `N` rounds.
The first line of input contains of a single integer
`N` (`1<=N<=1000`) -- the number of rounds. The second line contains `N` space-separated integers
`D_i` (`1 <= D_i <= 6`) -- the number rolled in `i`th round.
Output the Cleon's score.
```sample Sample Input
6
1 2 2 2 5 2
```
```sample Sample Output
20
```
3. Секретное сообщение
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Гааль Дорник отправляет Гэри Селдону секретное сообщение вида 00...0011...11, то есть в начале
сообщение состоит из некоторого количества 0, затем идет некоторое количество 1.
Количество 0 или 1 может быть нулевым. Гааль шифрует сообщение, добавляя несколько 1 среди нулей и несколько 0 среди 1.
Напишите программу, удаляющую наименьшее количество символов из зашифрованного сообщения так, чтобы после
удаления получилась строка вида 00...0011...11.
Первая строка ввода содержит непустую последовательность из 0 и 1 -- зашифрованное сообщение. Длина строки не превышает 100000 символов.
Вывести расшифрованное сообщение.
```sample Пример ввода
10011010
```
```sample Пример вывода
00111
```
4. Освоение бюджета
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Основное занятие жителей Трантора -- имперской столицы -- это освоение бюджетов.
Ежегодно Имперское Министерство Счастья выделяет деньги на различные проекты,
каждый из которых требует определенной суммы денег, делает счастливыми некоторое
количество людей и завершается в конце года. Сумма затрат по всем проектам не должна превышать годового бюджета
Министерства. Если бюджет потрачен полностью, то в следующем году его величина остается такой же, как в текущем. Но
если бюджет на год равен `X`, а потрачена в течение года меньшая сумма `Y`, то за неполное освоение средств Министерство наказывают: доступный
бюджет на следующий год уменьшается на `2*(X-Y)` (или даже полностью обнуляется,
если потрачена только половина бюджета или меньше). Император приказывает вам осчастливить максимальное количество людей за время вашей работы.
В первой строке вводятся 3 целых числа: бюджет Министерства в первый год `B` (`1<=B<=100`, в гигакредитах), количество
проектов `N` (`1<=N<=10^5`) и горизонт планирования `T` (`1<=T<=10^3`, в годах). Затем следует `N` строк, по два целых числа в каждой, описывающих
возможные проекты: сумма расходов на проект `C_i` (`1<=C_i<=B`, в гигакредитах) и количество людей `H_i` (`0<=H_i<=10^4`), которых финансирование проекта
делает счастливыми за год. Набор возможных проектов не меняется год от года, но распределение
финансирования можно менять. Любой проект должен быть в течение года профинансирован полностью, либо не профинансирован
вообще (иначе вы будете привлечены к ответственности за нецелевое использование средств).
Выведите одно целое число -- максимальное общее количество людей, которых Министерство может сделать счастливыми за `T` лет работы.
```sample Пример ввода
100 2 3
60 10000
10 1000
```
```sample Пример вывода
12000
```
Пояснение к примеру. В первый год мы можем профинансировать оба проекта, сделав
счастливыми `10000+1000=11000` людей и потратив `60+10=70` гигакредитов. Значит, 30 гигакредитов останутся
не потраченными, и бюджет на второй год будет равен `100-2*30 = 40` гигакредитов. Во второй год мы сможем профинансировать
только второй проект и сделать счастливыми еще 1000 человек. При этом мы потратили меньше
половины от текущего бюджета (10 из 40 гигакредитов), поэтому на третий год бюджет полностью обнулится.
5. Путешествие по Трантору
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Гааль Дорник и Рейч Фосс должны посетить несколько районов Трантора, которые пронумерованы числами от `L` до `R`.
При этом Фосс посещает их по порядку от `L` до `R`, а Дорник на `i`-м шаге выбирает район `X_i`,
номер которого является взаимно простым числом с номером района, в котором на этом шаге находится Фосс, то есть
`"gcd"(X_i,L+i-1)=1`. Номера `X_i` должны быть перестановкой чисел от `L` до `R`
(каждое число должно быть в последовательности ровно один раз).
Выведите порядок, в котором Дорник посещает районы Трантора, или определите, что это невозможно.
Первая строка ввода содержит два целых числа `L` и `R` (`1<=L<R<=10^5`).
Вывести -1, если перестановка не существует, иначе вывести перестановку чисел от `L` до `R`. Можно вывести любой вариант,
соответствующий условиям.
```sample Пример ввода 1
1 5
```
```sample Пример вывода 1
5 1 4 3 2
```
```sample Пример ввода 2
2 4
```
```sample Пример вывода 2
-1
```
Пояснение к примеру 1: gcd(5,1)=1, gcd(1,2)=1, gcd(4,3)=1, gcd(3,4)=1, gcd(2,5)=1.
6. Первое Основание
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Планета Терминус, на которой размещается Первое Основание, бедна ресурсами. Всю энергию жители получают от
ядерных реакторов, которым требуется урановое топливо. Немногочисленные месторождения урана залегают глубоко под землей, поэтому
для его добычи построена разветвленная сеть из `N` горных выработок, связанных между собой соединительными тоннелями.
Выработка номер 1 имеет выход на поверхность, все остальные расположены в глубине. Прокладка соединительных тоннелей -- тяжелое и затратное дело,
поэтому проложить удалось только минимально необходимое их количество. Из-за этого существует ровно один путь от каждой из
выработок до выхода на поверхность.
Когда роботы-шахтеры добывают в одной из выработок очередную партию урана, её нужно доставить на поверхность.
Подъем партии по тоннелю требует определенного количества энергии (не зависящего от размера партии).
Стоимость подъема может меняться: увеличиваться (например, если в тоннеле произошел обвал и передвижение по нему затруднено)
или уменьшаться (например, если в тоннеле построили эффективный подъемник). Из-за этого некоторые партии становится выгоднее
поднимать на поверхность не сразу после добычи, а дождавшись более подходящего момента в будущем, но в обоих случаях поднимать
партию урана нужно сразу до поверхности, а до не какой-то промежуточной точки.
Некоторые партии имеет смысл и вовсе бросить и не доставлять на поверхность, если затраты на их подъем не окупятся в любом случае.
Ваша задача -- по информации о добываемых партиях урана и стоимостях подъема определить, сколько энергии получит Терминус при оптимальном
планировании добычи.
В первой строке ввода содержится два целых числа: количество выработок `N` (`1<=N<=10^5`) и количество событий `Q` (`1<=Q<=10^5`).
Затем следует `N-1` строка -- описания тоннелей. Каждое описание включает три целых числа: номера пары выработок,
соединенных тоннелем (от 1 до `N`), и стоимость подъема в начальный момент времени (от 0 до `10^5`, в энергетических единицах).
Затем следует `Q` строк -- описания событий в том порядке, в котором они происходили, первое число в каждой строке -- тип события.
* Тип 1 -- добыта партия урана, затем следует два целых числа: номер выработки, в которой добыта партия (от 1 до `N`) и количество добытого урана (в энергетических единицах, от 1 до `10^5`).
* Тип 2 -- изменилась стоимость подъема по тоннелю, затем следует два целых числа: номер тоннеля (от 1 до `N-1`, соответствует номеру строки описания), и изменение стоимости (от `-10^5` до `10^5`; гарантируется, что стоимость в любой момент неотрицательна).
Выведите единственное неотрицательное целое число -- максимально возможное количество добытой
энергии (общее количество поднятого на поверхность урана за вычетом затрат на его подъем). Любую из партий разрешается
поднимать в любой момент времени (в том числе, после последнего события), но не раньше момента её добычи.
Любые партии разрешается бросать в выработке (в этом случае партия не приносит энергии, но и не требует затрат на подъем).
```sample Пример ввода
4 5
1 2 10
2 3 50
2 4 15
1 4 200
1 3 50
2 2 -45
2 1 35
1 4 50
```
```sample Пример вывода
210
```
*Пояснение к примеру*
* Первую партию стоит доставить на поверхность сразу же после добычи, затраты на подъем составят 15 (от выработки 4 до 2) + 10 (от выработки 2 до 1).
* Вторую партию стоит доставить на поверхность в промежутке между событиями 3 и 4 (когда стоимость подъема по тоннелю 2 уже уменьшилась, а по тоннелю 1 -- еще не увеличилась). В этом случае затраты на подъем составят 5 (от выработки 3 до 2) + 10 (от выработки 2 до 1).
* Третью партию стоит бросить, так как затраты на подъем из выработки 4 к этому моменту составляют 60 и превышают выгоду от доставки её на поверхность.
Итоговое количество равно: (200-15-10) + (50-5-10) = 175 + 35 = 210 энергетических единиц.
7. Третье основание
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Опасаясь нападения Империи, все последователи Гэри Селдона эвакуируются на огромную
космическую станцию "Третье Основание". Станция состоит из отдельных модулей, связанных жестким невесомым каркасом.
Для каждого модуля известно его положение в пространстве и масса. Чтобы станцией было легче управлять,
её центр тяжести должен располагаться в точке с координатами `(0,0,0)`. Чтобы достичь этого,
можно переместить какой-нибудь один модуль.
При этом расстояние, на которое модуль перемещается,
должно быть минимальным (чтобы не тратить зря энергию). По заданной
информации о станции определите, какой из модулей нужно переместить и на какое расстояние.
В первой строке ввода находится одно целое число `N` (`1<=N<=10^5`) -- количество модулей. Каждая из `N` последующих
строк содержит по четыре целых числа, описывающих модуль: координаты модуля `x_i, y_i, z_i` (`-10^5<=x_i,y_i,z_i<=10^5`)
и его масса `M_i` (`1<=M_i<=10^5`). Гарантируется, что центр тяжести станции не находится в точке `(0,0,0)`.
Выведите два числа: номер модуля, который нужно переместить (от 1 до `N`), и расстояние, на которое он должен переместиться,
чтобы центр тяжести станции оказался в точке с координатами `(0,0,0)`. Относительная погрешность
вычисленного расстояния не должна превышать `10^{-6}`. Если есть несколько вариантов с одинаковым
минимальным расстоянием, выведите тот, в котором номер перемещаемого модуля минимален.
```sample Пример ввода
2
-1 0 0 10
1 0 0 20
```
```sample Пример вывода
2 0.5000000
```
Координаты центра тяжести можно рассчитать по формулам
`{ (x_{"ЦТ"}=(sum_{i=1}^N M_i*x_i)/(sum_{i=1}^N M_i)), (y_{"ЦТ"}=(sum_{i=1}^N M_i*y_i)/(sum_{i=1}^N M_i)), (z_{"ЦТ"}=(sum_{i=1}^N M_i*z_i)/(sum_{i=1}^N M_i)) :}`
*Пояснение к примеру:* Центр тяжести станции до перемещения находится в точке `(1//3, 0, 0)`.
Можно переместить первый модуль на расстояние 1 в точку `(-2, 0, 0)`, либо второй модуль
на расстояние `1//2` в точку `(1/2, 0, 0)`. Во втором варианте расстояние перемещения меньше.
8. Глобальное потепление
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Из-за глобального потепления на планете Геликон начинает повышаться уровень океана.
Математик Гэри Селдон пытается оценить возможный ущерб от затопления, чтобы доказать
своё мастерство в предсказании будущего и отправиться в столицу Империи. Ущерб определяется тем,
сколько жителей попадает в зону затопления. Жители проживают в городах, каждый из которых относится
к одному из секторов. Город считается затопленным, если вода поднялась до уровня строго большего,
чем высота этого города над уровнем моря. Требуется
определить наиболее пострадавший сектор и количество людей в этом секторе,
которых нужно эвакуировать из затопляемых городов.
К сожалению, точный уровень повышения воды пока
неизвестен, поэтому вычисления нужно произвести для каждой из возможных гипотез.
В первой строке ввода содержится три целых числа: количество секторов `M` (`1 <= M <= 10^5`),
количество городов `N` (`1 <= N <= 10^5`) и количество гипотез об уровне поднятия воды `Q` (`1 <= Q <= 10^5`).
Далее идет `N` строк, каждая из которых описывает один город и состоит из трех целых чисел: номер сектора `m_i`,
к которому город принадлежит (`1 <= m_i <= M`), количество жителей `p_i` (`1 <= p_i <= 10^9`),
высота над уровнем моря `h_i` (`1 <= h_i <= 10^9`).
Затем идет `Q` строк, каждая из которых содержит одно целое число -- предполагаемый
подъем уровня воды `d_j` (`1 <= d_j <= 10^9`).
Для каждой из `Q` гипотез выведите на отдельной строке два числа:
номер наиболее пострадавшего сектора и количество людей, проживающих в затопляемых городах этого сектора.
Если максимально пострадавших секторов несколько, выведите сектор с минимальным номером.
```sample Пример ввода
2 3 3
1 70 60
1 1000 160
2 150 120
100
150
200
```
```sample Пример вывода
1 70
2 150
1 1070
```
*Пояснение к примеру:*
* В первом случае вода поднимется на 100 метров и затопит только первый город, относящийся к первому сектору.
* Во втором случае вода поднимется на 150 метров и затопит по одному городу в секторах 1 и 2. Второй сектор пострадает больше, т.к. соответствующий город больше.
* В третьем случае вода поднимется на 200 метров и затопит все города. Общее население сектора 1 больше, чем население сектора 2, поэтому он пострадает максимально.
9. Трантор в упадке
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Вся поверхность столичной планеты Трантор покрыта огромным городом. Самый быстрый способ
перемещения по нему -- скоростной монорельс. Все станции монорельса связаны двусторонними линиями
в единую сеть и от любой станции можно добраться до любой другой (возможно, с пересадками).
К сожалению, инфраструктура Трантора находится в упадке, и работоспособность сохраняет
только минимально необходимое количество линий. Из-за этого между каждой парой станций остается
только 1 возможный маршрут. Что еще хуже, поезда регулярно ломаются: в этом случае пассажиры не
доезжают до конечной станции, а застревают на одной из промежуточных остановок и вынуждены ждать другого поезда.
Прибывший на Трантор математик Гэри Селдон не привык к подобным проблемам, и в первый же день заблудился
по дороге из космопорта (станция 1).
Селдон описал свои поездки в дневнике следующим образом:
* он садился в поезд и запоминал номер конечной станции, до которой поезд следовал по расписанию;
* во время поездки он считал количество станций, которые поезд успешно миновал по дороге;
* если поезд ломался, не доехав до конечной станции, Селдон покидал его на текущей станции, а затем садился в первый же подошедший на эту станцию поезд (возможно, следующий другим маршрутом или в другую сторону);
* в новом поезде все повторялось снова.
К сожалению, во время одной из пересадок Селдон забыл на станции свой портфель с бесценными записями. Помогите
ему определить, на каких станциях он побывал, чтобы попытаться его найти.
В первой строке ввода содержатся два целых числа: количество станций `N` (`2<=N<=10^5`) и
количество записей Селдона о его поездках `M` (`1<=M<=10^5`).
Затем следует `N-1` строка -- описание сети монорельса. Каждая строка содержит по два целых числа:
номера станций, связанных между собой линией (станции нумеруются от `1` до `N`).
Затем следует `M` строк, описывающих поездки Селдона.
Каждая строка содержит по два целых числа: номер конечной станции, в направлении которой следовал поезд (от 1 до `N`), и
количество станций `K`, которые Селдон проехал на поезде до поломки (считая станцию отправления, но не считая станцию, на которой поезд остановился).
Гарантируется, что `K` не меньше 1 и не больше, чем количество станций до конечной. Первая поездка начинается со станции с номером 1.
Выведите `M` целых чисел -- номера станций, на которых Селдон оказывался по окончании каждой из своих поездок.
```sample Пример ввода
7 4
1 2
2 3
3 4
4 5
3 6
6 7
7 3
5 2
2 1
7 2
```
```sample Пример вывода
6 4 3 7
```
*Пояснение к примеру.*
* Первая поездка (7, 3): поезд от станции 1 до станции 7 следует по маршруту 1-2-3-6-7; проехав на нем 3 станции, Селдон остановился на станции 6.
* Вторая поездка (5, 2): поезд от станции 6 до станции 5 следует по маршруту 6-3-4-5; проехав на нем 2 станции, Селдон остановился на станции 4.
* Третья поездка (2, 1): поезд от станции 4 до станции 2 следует по маршруту 4-3-2; проехав на нем 1 станцию, Селдон остановился на станции 3.
* Четвертая поездка (7, 2): поезд от станции 3 до станции 7 следует по маршруту 3-6-7; проехав на нем 2 станции, Селдон добрался до конечной станции 7.
11. Game
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Gaal Dornick and Hari Seldon decided to play a game with following rules.
There are `N` buckets where `i`th bucket contains `B_i` balls initially.
1. Both players take turns with Gaal going first.
2. If there are no balls left, the game ends.
3. In his/her turn, the player will remove a ball from any bucket which contains at least one ball.
4. If, after the move, the bucket from which the ball is removed becomes empty, the player gets a point.
If both players play optimally, find the player who will get more points. If both players get same points, print ``Draw``.
The first line of input contains `N` (`1 <= N <= 10^5`) -- the number of buckets. The second line contains `N` space-separated integers
`B_i` (`1 <= B_i <=10^9`) -- the number of balls in `i`th bucket initially.
Output ``Gaal``, if Gaal gets more points; or ``Hari``, if Hari gets more points; else ``Draw``, if both get same number of points.
```sample Sample Input 1
3
1 2 3
```
```sample Sample Output 1
Hari
```
```sample Sample Input 2
3
3 3 3
```
```sample Sample Output 2
Gaal
```
Expain for sample 1.
* Gaal picks a ball from first bucket and gets a point.
* Hari picks a ball from third bucket.
* Gaal picks a ball from second bucket.
* Hari picks a ball from second bucket and gets a point.
* Gaal picks a ball from third bucket.
* Hari picks a ball from third bucket and gets a point.
* Game ends. Thus, Hari has more points than Gaal.
12. Далекая Звезда
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Космические пираты преследуют новейший гравитационный корабль Основания "Далекая Звезда". Корабль
находится в точке с координатами `(0,0,0)` и летит c постоянной скоростью строго по прямой в направлении
безопасной планеты-убежища
с координатами `(X,Y,Z)`.
Корабли пиратов находятся в известных точках пространства, могут двигаться в
любых направлениях и имеют некоторую силу и скорость. Пиратам известны курс и
скорость "Далекой Звезды", они согласуют
действия между собой и действуют оптимальным образом. "Далекая Звезда" достаточно
хорошо защищена, поэтому может отбиться от пиратских кораблей с суммарной силой `P` одновременно.
Но если в одной точке пространства с "Далекой Звездой" одновременно окажутся
пиратские корабли с суммарной силой `P+1` или больше, то они смогут преодолеть защиту
и взять корабль на абордаж. Найдите минимальную скорость движения, с которой "Далекой Звезде" удастся
добраться до цели и не быть пойманной пиратами.
В первой строке ввода указаны пять целых чисел: координаты цели полета `X,Y,Z` (не превышают `10^3` по модулю,
не совпадают с `(0,0,0)`), сила защиты корабля `P` (`0<=P<10^6`) и количество пиратских кораблей `N` (`1<=N<=10^3`).
Затем следует `N` строк, содержащих по пять целых чисел и описывающих каждый из пиратских
кораблей: его координаты `x_i, y_i, z_i` (не превышают `10^3` по модулю), максимальную
скорость `M_i` (`1<=M_i<=10`) и силу `S_i` (`1<=S_i<=10^3`). Суммарная сила пиратов
строго больше `P`. Ни один пиратский корабль не находится в точках `(0,0,0)` или `(X,Y,Z)`.
Координаты нескольких кораблей могут совпадать.
Выведите единственное вещественное число -- минимальную
скорость "Далекой Звезды", достаточную для достижения цели. Абсолютная или относительная
погрешность ответа не должна превышать `10^{-6}`. Гарантируется, что
во всех тестах требуемая скорость не превышает `3*10^6`. Если спастись от пиратов невозможно
при любом значении скорости, выведите `-1`.
```sample Пример ввода 1
2 2 0 1 2
1 1 0 10 1
3 2 0 1 1
```
```sample Пример вывода 1
2.8284271
```
```sample Пример ввода 2
0 10 0 0 1
3 4 0 2 100
```
```sample Пример вывода 2
3.3333333
```
*Пояснение к примерам.*
* В первом случае: если скорость корабля будет меньше, чем `sqrt(8)`, то первый пират встретит его по пути и сможет сопровождать, а второй пират успеет присоединиться к первому прямо перед планетой-целью.
* Во втором случае: при скорости меньшей, чем `10/3`, пират сможет перехватить корабль в точке `(0, 6.25, 0)` в момент времени `1.875`.
12. Отражения
Ограничения: время – 1500ms/3000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Гааль Дорник экспериментирует с передачей информации с помощью зеркал.
Площадка размером `N xx M` разбита на клетки единичного размера.
Нужно отправить луч света из одной клетки в другую. Луч проходит параллельно осям координат.
Специальные зеркала установлены в некоторых клетках площадки и по всему периметру площадки. Зеркало изменяет направление луча на 90 градусов,
при этом часть света направляется в одну сторону, а часть в противоположную.
Так как при каждом отражении энергия луча уменьшается, то желательно, чтобы отражений было как можно меньше.
Необходимо определить начальное направление, которое позволит лучу добраться до целевой клетки с минимальным количеством отражений.
Первая строка ввода содержит семь целых чисел -- размеры площадки `N` и `M` (`2<=N, M<=10^5`), координаты
начальной клетки `R_1, C_1` и целевой клетки `R_2, C_2` (`1 <= R_1, R_2 <= N`, `1 <= C_1, C_2 <= M`, `(R_1,C_1)!=(R_2,C_2)`),
количество зеркал на площадке `K` (`0<=K<=10^5`).
Далее следует `K` строк, каждая строка содержит два целых числа -- координаты `i`-го зеркала `r_i,c_i` (`1 <= r_i<=N`, `1<=c_i<=M`).
Координаты зеркал не совпадают между собой и не совпадают с координатами начальной и конечной точки.
Кроме того, зеркала установлены в клетках с координатами `(0,j)`, `(N+1,j)`,`(i,0)`, `(i,M+1)`, где `i in 0...N+1`, `j in 0...M+1`.
Вывести минимальное количество отражений и начальное направление (N, E, S, W) или -1, если луч не может достичь конечной клетки.
Если есть несколько вариантов направления для начальной клетки, обеспечивающих минимальное количество отражений, то можно вывести любой из них.
```sample Пример ввода
5 7 4 6 1 3 3
2 3
2 5
5 5
```
```sample Пример вывода
4 N
```
*Пояснение к примеру:*
При выборе других направлений получится не менее 5 отражений.
13. Солярианские роботы
Ограничения: время – 250ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Жители планеты Солярия -- мастера в создании роботов, и они что-то замышляют!
Агенту Основания удалось узнать, что на солярианской фабрике роботов в производстве находятся две модели: роботы-рабочие и роботы-солдаты.
Для сборки рабочего требуется стандартный корпус и `W` позитронных схем, а солдата - такой же корпус и `S` схем. На
фабрику было поставлено `B` корпусов и `P` позитронных схем, которые были израсходованы для сборки роботов без остатка.
Сколько рабочих и солдат изготовили солярианцы?
Единственная строка ввода содержит четыре целых числа `W`, `S`, `B` и `P` (все от `1` до `10^18` включительно).
Выведите два неотрицательных целых числа: количество рабочих и солдат соответственно.
Если агент ошибся и данные противоречивы, выведите -1. Если данных недостаточно, и однозначно установить количество рабочих и солдат
невозможно, выведите -2.
```sample Пример ввода 1
2 4 2 6
```
```sample Пример вывода 1
1 1
```
```sample Пример ввода 2
2 4 2 5
```
```sample Пример вывода 2
-1
```
```sample Пример ввода 3
1 1 2 2
```
```sample Пример вывода 3
-2
```
Начало
Соревнования
Разделение на 2 (или более) подзадачи