Задачи командных соревнований PRIME TIME 2025
1. Изумрудная корона
Ограничения: время – 600ms/1200ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
 Корона правителя Изумрудного города украшена
большим треугольным изумрудом, поверхность которого состоит
из одинаковых треугольных граней, по `N` вдоль каждой из сторон (на рисунке `N=5`).
Крепление изумруда к короне находится на его вертикальной оси, за одной из граней
(выделены цветом). Когда правителем города стал Страшила, корона оказалась для него
слишком тяжелой, и он захотел огранить изумруд заново, отрезав какое-то положительное
количество лишних граней. После огранки изумруд по-прежнему должен иметь форму
правильного треугольника, и грань с креплением должна остаться
нетронутой (хотя и не обязана больше лежать на оси изумруда). Помогите
Страшиле подсчитать количество способов выполнить огранку.
В первой строке ввода находится единственное натуральное число `T` (`1<=T<=10^5`) – количество тестов.
В каждой из следующих `T` строк вводятся описания тестов, состоящие
из двух натуральных чисел:
`N` (`1<=N<=10^6`) – количество граней вдоль стороны треугольника,
`h` (`1<=h<=N`) – номер горизонтального ряда граней, в центре которого расположено
крепление (обозначены на рисунке серыми цифрами).
Выведите `T` чисел, по одному на строке: количество способов огранить изумруд для соответствующего теста.
```sample Пример ввода
3
5 5
5 2
1 1
```
```sample Пример вывода
4
11
0
```
Пояснение к примеру.\
В первом случае крепление находится за гранью ABC, после огранки изумруд может иметь форму треугольников ABC, ADF, AGJ или AKO (всего 4 варианта).\
Во втором случае крепление находится за гранью HIM, после огранки изумруд может иметь форму треугольников HIM, DFM, GIR, HJS, ELN, EQT, BTP, CQU, BKN, CLO, AKO (всего 11 вариантов).\
В третьем случае невозможно удалить единственную грань, не нарушив условий.
2. Gifts
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
All travelers visiting the Emerald City are given glasses with green lenses.
In honor of the city's anniversary, Great and Powerful Oz decided to add a box with a gift to the glasses.
The box has a cubic shape with an edge size of `R`. The box must be covered with green paper.
Determine how many boxes can be covered with `R xx R` squares cut from a sheet of paper measuring `W xx H`.
The first line of input contains three integers `R`, `W`, `H` (`1<=R<=min(W,H), W*H<=10^9`).
Output one integer — the number of boxes.
```sample Sample Input
2 5 10
```
```sample Sample Output
1
```
3. T-shirts
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
All residents of the Emerald City must wear green T-shirts for the party. There are five sizes
of T-shirts in stock: XS, S, M, L, XL. A resident can wear either their size or one size larger.
For example, a person who wears size M will also wear a T-shirt of size L, but T-shirts of sizes XS
and S will be small for them, and a T-shirt of size XL will be too big. Determine how many residents of
the city can wear T-shirts and come to the party.
The first input line contains five integers `XS, S, M, L, XL` (`0<= XS, S, M, L, XL <= 10^9`) — the number of T-shirts
of the corresponding size. The second input line contains five integers `A, B, C, D, E` (`0<= A, B, C, D, E <= 10^9`) — the
number of city residents who wear T-shirts of sizes XS, S, M, L, XL respectively.
Output one integer — the maximum number of residents who will be able to attend the event in green T-shirts.
```sample Sample Input
2 3 0 1 10
4 2 1 2 2
```
```sample Sample Output
10
```
Example explanation: 4 residents of size XS can take 2 T-shirts of size XS and 2 T-shirts of size S, one
of the 2 residents of size S takes 1 T-shirt of size S and the other stays at home, 1 resident of
size M takes 1 T-shirt of size L, 2 residents of size L and 2 residents of size XL take 4 T-shirts of size XL.
In total, 10 residents will be able to attend the party.
4. Сферы влияния
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Волшебная страна и её окрестности состоят из квадратных районов, образующих правильную сетку.
После победы над злыми Волшебницами Запада и Востока добрые Волшебницы Севера и Юга договорились разделить
страну на две сферы влияния по следующим правилам:
1. Каждый из районов страны целиком принадлежит или Северу, или Югу.
2. Районы, принадлежащие каждой из сторон, образуют связную область (т.е. обойти сферу влияния каждой из волшебниц можно, перемещаясь только между районами, соседними по стороне).
3. Две сферы влияния имеют одинаковые размеры и форму (т.е. соответствующие фигуры можно перевести друг в друга последовательностью поворотов, сдвигов и отражений).
4. Каждая из сфер влияния содержит одинаковый по длине участок внешней границы Волшебной страны.
5. Если есть несколько подходящих разбиений страны, подойдет любое.
Помогите волшебницам разделить Волшебную страну и не поссориться между собой.
В первой строке ввода находятся натуральные числа `N` и `M` (`1<=N,M<=15`) — размеры карты.
Затем следуют `N` строк по `M` символов в каждой — карта страны и окрестностей. Символ ``'#'`` обозначает часть Волшебной страны,
а символ ``'.'`` - окружающую страну пустыню. Гарантируется, что в стране не менее 1 и не более 15 районов, и они образуют
связную (по сторонам районов) область, не содержащую фрагментов пустыни внутри себя. Внешняя граница страны - линия, разделяющая ``'#'`` и ``'.'``.
Если не существует ни одного способа разделить страну, удовлетворяющего всем условиям, выведите единственную строку ``Impossible``.
Иначе выведите `N` строк по `M` символов — описание разделения: пустынные районы (``'.'``) должны остаться нетронутыми,
районы в сфере влияния Севера отмечены как ``N``, в сфере влияния Юга — как ``S``.
```sample Пример ввода 1
4 5
.#...
.#...
##.#.
.###.
```
```sample Пример вывода 1
.N...
.N...
NN.S.
.SSS.
```
```sample Пример ввода 2
2 6
######
##....
```
```sample Пример вывода 2
Impossible
```
Пояснение к примеру 1: обе части связны, имеют одинаковую форму и содержат по 9 участков внешней границы страны.\
Пояснение к примеру 2: можно разделить страну на 2 связные части одинаковой площади, но они будут иметь разную
форму и включать разные по длине участки внешней границы.
5. Подземные короли
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В огромной пещере под Волшебной страной есть `N` королей, большую часть времени погруженных для экономии средств в волшебный сон.
Встречаются между собой короли только раз в году на празднике урожая, и происходит это следующим образом.
В начале праздника сонные мастера пробуждают королей с промежутками в 1 минуту в случайном порядке. Через `N-1` минуту
после пробуждения первого короля (то есть, сразу же при пробуждении последнего), начинается праздничный пир.
После окончания пира процесс повторяется похожим образом: сразу в момент окончания пира мастера усыпляют кого-нибудь из королей, и
далее усыпляют по 1 случайному королю через минуту (порядок каждый раз выбирается случайно и не зависит от порядка пробуждения). Вычислите
среднее время бодрствования королей во время праздника урожая.
В единственной строке ввода находятся два натуральных числа: `N` – количество королей и `T` — продолжительность пира (`1<=N,T<=10^9`).
Выведите одно вещественное число — среднее время бодрствования. Ответ будет считаться верным, если он отличается от точного значения не более, чем на `10^(-6)`.
```sample Пример ввода
2 100
```
```sample Пример вывода
101.0
```
Пояснение к примеру: два короля могут пробуждаться в порядке 1-2 или 2-1, и засыпать также в порядке 1-2 или 2-1. В каждом из случаев:\
1-2, 1-2: король 1 бодрствует 101 минуту (пир и 1 минуту до него), король 2 также 101 минуту (пир и минуту после него);\
1-2, 2-1: короли бодрствуют 102 и 100 минут соответственно;\
2-1, 1-2: короли бодрствуют 100 и 102 минуты соответственно;\
2-1, 2-1: оба короля бодрствуют по 101 минуте.\
Среднее время: (101+101+102+100+100+102+101+101)/8 = 101.
6. Разноцветные дуболомы
Ограничения: время – 600ms/1200ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Войско дуболомов выстроилось поотрядно перед своим командующим Урфином Джюсом и ждет указаний.
Войско состоит из `N` отрядов, `i`-й отряд включает дуболомов, покрашенных в цвет `c_i`, и имеет
численность `a_i` (цвета отрядов могут повторяться). Урфин Джюс планирует `Q` операций, в `j`-й из которых будут
участвовать отряды с номерами от `l_j` до `r_j` включительно (отряд может участвовать и в нескольких операциях). Для каждой из
операций нужно выбрать командующего, им должен стать дуболом-капрал того цвета, в который покрашено наибольшее количество дуболомов-участников
операции. Если несколько цветов представлены одинаковым числом дуболомов, командовать будет
капрал цвета с наименьшим номером. Помогите Урфину определить всех требуемых командующих.
В первой строке ввода находятся два натуральных числа: `N` – количество отрядов (`1<=N<=10^5`) и Q (`1<=Q<=10^5`) – количество операций.
Затем следует `N` строк, по два числа в каждой: цвет (`1<=c_i<=10^5`) и численность (`1<=a_i<=10^5`) каждого из отрядов.
Затем следует `Q` строк, по два числа в каждой: номера первого и последнего отрядов (`1<=l_j<=r_j<=N`), которые примут участие
в операции с соответствующим номером.
Выведите строку из `Q` натуральных чисел, разделенных пробелами: цвета командующих в каждой из операций.
```sample Пример ввода
3 2
1 10
2 12
1 5
1 2
1 3
```
```sample Пример вывода
2 1
```
7. Часы
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
 На главной башне Изумрудного города находятся часы. Время от времени Гудвин устанавливает эти часы на точное время по своему хронометру.
В часах есть 3 рычага для передвижения секундной, минутной и часовой стрелки на 1 деление вперед (назад, против часовой стрелки,
двигать стрелки нельзя). При передвижении секундной стрелки двигаются на соответствующую величину минутная и часовая.
При передвижении минутной стрелки секундная не двигается, но двигается часовая. При передвижении часовой стрелки остальные стрелки не двигаются.
Определить минимальное (в сумме) количество нажатий на рычаги для перемещения стрелок из начального в конечное.
Первая строка ввода содержит три целых числа `H_1, M_1, S_1` (`1<=H_1<=12, 0<=M_1<=59, 0<=S_1<=59`) – начальное состояние часов.
Вторая строка ввода содержит три целых числа `H_2, M_2, S_2` (`1<=H_2<=12, 0<=M_2<=59, 0<=S_2<=59`) – конечное состояние часов.
Вывести три целых числа — минимальное количество нажатий на рычаги для перемещения часовой, минутной и секундной стрелки.
```sample Пример ввода
9 59 50
11 0 0
```
```sample Пример вывода
1 0 10
```
Пояснение к примеру: после 1 нажатия на часовой рычаг на часах будет 10:59:50, после 10 нажатий на секундный рычаг секундная стрелка дойдет до 0,
минутная стрелка тоже сдвинется к 0, а часовая стрелка - к 11 и на часах будет 11:00:00.
8. Книга Виллины
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В волшебной книге Виллины записано число из `N` цифр, с которым волшебница проделывает 2 вида экспериментов.
Во-первых, Виллина может разом заменить все цифры с номерами от `L` до `R` включительно на цифру `C`.
Во-вторых, Виллина может сделать заклинание из цифр с номерами от `L` до `R`, не меняя их порядка. Чтобы определить
силу получившегося заклинания, нужно рассмотреть все его непустые подстроки. Каждая подстрока, образующая число,
кратное магическому числу `K`, увеличивает силу заклинания на 1. Число-подстрока
может совпадать с целой строкой, а также иметь ведущие нули (все такие числа учитываются, если они кратны `K`).
Помогите Виллине предсказать заранее силу всех полученных заклинаний.
В первой строке ввода находятся три натуральных числа: `N` – количество цифр в книге (`1<=N<=10^5`), `Q` – количество
экспериментов (`1<=Q<=10^4`) и магическое число `K` (`2<=K<=10`).
Следующая строка состоит из `N` цифр без пробелов, описывающих начальное состояние книги.
Затем следует `Q` строк, описывающих эксперименты в порядке их проведения.
Эксперименты-замены описываются как "`1 \quad L \quad R \quad C`" (`1<=L<=R<=N`, `0<=C<=9`);
Эксперименты-заклинания записываются как "`2 \quad L \quad R`" (`1<=L<=R<=N`).
Для каждого из экспериментов-заклинаний выведите одно число — силу полученного заклинания.
```sample Пример ввода
5 6 3
60311
2 1 3
2 4 5
1 3 4 2
2 4 5
2 1 5
2 2 2
```
```sample Пример вывода
6
0
1
4
1
```
Пояснение к примеру:
- в первом запросе строка "603" включает 6 подстрок: "6", "0", "3", "60", "03", "603" - все они образуют числа, кратные 3;
- во втором запросе строка "11" не содержит не одной подходящей подстроки;
- после третьего запроса строка приобретает вид "60221";
- в четвертом запросе строка "21" содержит ровно одну подходящую подстроку - себя саму;
- в пятом запросе учитываются подстроки "6", "0", "60", "21";
- в шестом запросе учитывается единственная подстрока "0".
9. Поле Страшилы
Ограничения: время – 1500ms/3000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
До появления Элли в стране жевунов Страшила жил посреди большого прямоугольного поля и пугал ворон.
Поле Страшилы состоит из одинаковых квадратных участков и имеет размеры `N xx M`. На каждом участке
выращивается `с_{ij}` сельскохозяйственных культур по принципу севооборота: первая культура выращивается в первый год,
вторая - во второй, ..., `c_{ij}`-я культура - в `c_{ij}`-ый, а в `(c_{ij}+1)`-ый год участок пустует для восстановления плодородия,
затем всё повторяется: первая культура - `(c_{ij}+2)`-ый год и так далее. Некоторые участки не возделываются (`c_{ij}=0`).
Кроме фермерства, жевуны очень любят праздники. Для каждого из праздников они занимают подходящий (для каждого праздника - свой)
прямоугольный кусок поля и ставят на нем шатры и аттракционы. Но чтобы не терять урожай, все занятые под празднование участки
должны в соответствующий год пустовать. Определите, как скоро жевуны смогут провести каждый из праздников.
В первой строке ввода указаны три натуральных числа: `N` и `M` - размеры поля (`1<=N,M <= 200`), `Q` - количество праздников (`Q <= 10^6`).
Затем следует `N` строк по `M` чисел в каждой - схема поля. Каждый участок описывается одним целым числом `c_{ij}` (`0<=c_{ij}<=40`) - количеством культур,
выращиваемых на нем.
Затем следует `Q` строк по 4 целых числа в каждой - описания частей поля, необходимых для проведения каждого
из праздников: `i_1, j_1` - координаты поля, находящегося в верхнем левом углу нужной территории, `i_2, j_2` - координаты поля
в правом нижнем углу (`1<=i_1<=i_2<=N`, `1<=j_1<=j_2<=M`).
Выведите `Q` натуральных чисел, по одному для каждого из праздников: минимальный номер года,
в который все соответствующие участки будут свободны.
```sample Пример ввода
2 5 3
3 1 2 0 1
0 0 5 0 0
2 1 2 2
1 4 2 5
1 1 2 5
```
```sample Пример вывода
1
2
12
```
Пояснение к примеру.\
В первом случае, оба требуемых участка всегда пустуют и их можно занять в первый же год.\
Во втором случае, единственный возделываемый участок (1,5) будет занят в первый год и освободится во второй.\
В третьем случае, в каждый из первых 11 лет хотя бы один из участков поля будет занят. На 12 год все участки освободятся.
10. Летучие обезьяны
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В волшебной стране `N` поселений, для каждого из которых известно его местоположение и численность жителей.
Жители страдают от налетов летучих обезьян, поэтому для защиты решено было построить в некоторых из поселений
экспериментальные защитные башни. Башня в поселении защищает его и все поселения на расстоянии не более `D` от него.
Для каждого из поселений определите, какое количество жителей будет защищать построенная в нем башня.
Первая строка ввода содержит два натуральных числа: количество поселений `N` (`1<=N<=10^5`) и `D` – радиус защиты башни (`1<=D<=100`).
Затем следует `N` строк, каждая из которых описывает поселение и содержит три целых числа: `x, y, p` – координаты и
численность жителей (`0<=x,y<=10^6`, `1<=p<=10^9`). Каждое поселение считается точкой на плоскости с
координатами `(x, y)`. Координаты всех поселений различны.
Выведите `N` чисел, по одному на строке: количество жителей, которое окажется под защитой при постройке башни в соответствующем поселении.
```sample Пример ввода
4 2
1 3 100
2 2 50
4 2 70
9 1 90
```
```sample Пример вывода
150
220
120
90
```
Пояснение: башня в первом поселении защищает поселения 1 и 2, во втором - 1, 2 и 3, в третьем - 2 и 3, в четвертом - только 4.
11. Азартные прыгуны
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
У народа прыгунов очень популярны ставки на исход спортивных состязаний, например, по боксу.
В чемпионате страны прыгунов участвует `N` спортсменов, каждый из которых обладает силой `p_i`, и каждый спортсмен
проводит по одному поединку с каждым из остальных. Предсказуемостью поединка между спортсменами с
номерами `i` и `j` называют величину `abs(p_i-p_j)`. Определите `F` самых непредсказуемых и `L` самых предсказуемых поединков.
В первой строке ввода находятся три неотрицательных целых числа: `N` – количество спортсменов (`2<=N<=10^5`), `F` и `L`
(`1<=F+L<=min(10^5, N(N-1)//2)`) – количество поединков с наименьшей и наибольшей предсказуемостью, которые требуется найти.
Во второй строке ввода содержится `N` натуральных чисел `p_i` (`1<=p_i<=10^9`) – силы спортсменов.
В первой строке выведите `F` целых чисел в порядке неубывания — значения предсказуемости `F` наименее предсказуемых поединков.
Во второй строке выведите `L` целых чисел в порядке неубывания — значения предсказуемости `L` наиболее предсказуемых поединков.
В случае `F=0` или `L=0` соответствующая строка должна пустой.
```sample Пример ввода
4 2 3
1 2 4 1
```
```sample Пример вывода
0 1
2 3 3
```
12. Зелье Гингемы
Ограничения: время – 600ms/1200ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Зелье колдуньи Гингемы может иметь много злобных эффектов, а общая сила зелья вычисляется как сумма сил всех
отдельных эффектов. Каждый эффект может проявляться в зелье только 1 раз, поэтому при попытке добавления
к зелью эффекта, которое оно уже имеет, сила зелья не изменится.
Каждый из эффектов может вызываться определенным ингредиентом, добавленным в зелье. Но (колдовство — сложная штука!) один и тот
же ингредиент вызывает разные эффекты в зависимости от того, какой ингредиент добавлялся в зелье непосредственно
перед ним. Хуже того, если положить в зелье непосредственно друг за другом несовместимые ингредиенты — оно испортится и полностью потеряет свою силу.
Помогите Гингеме сварить зелье с максимальной возможной силой из заданного набора ингредиентов.
В первой строке ввода находятся два целых числа: `N` – количество ингредиентов (`1<=N<=10^5`) и `M` – количество возможных эффектов (`0<=M<=10^5`).
Затем следует `M` строк по три натуральных числа в каждой, описывающих возможные эффекты:
- `a_i` - номер ингредиента (`1<=a_i<=N`), вызывающего эффект;
- `p_i` – номер предшествующего ингредиента (`1<=p_i<=N, p_i!=a_i`), который должен быть положен в зелье непосредственно перед `a_i`-ым, чтобы эффект появился;
- `s_i` – сила эффекта (`1<=s_i<=10^9`).
Например, строка "2 1 10" означает: если добавить в зелье ингредиент 2 сразу после ингредиента 1, то он вызовет эффект с силой 10. Обратите внимание,
что пара "1 после 2" может быть несовместимой, даже если "2 после 1" приносит положительный эффект.
Любые пары ингредиентов, кроме `M` описанных, являются несовместимыми. Гарантируется, что добавление
одного и того же ингредиента два раза подряд не приносит эффекта, а одна и та же пара
ингредиентов встречается в описании не более 1 раза. Один и тот же ингредиент разрешается добавлять в
зелье несколько раз. Первый добавленный в зелье ингредиент (тот, перед которым ничего не добавлялось) никогда не
приносит самостоятельного эффекта.
Выведите одно целое число — максимальную силу зелья.
```sample Пример ввода 1
7 6
2 1 2
2 3 2
3 2 1
3 4 1
5 3 3
5 6 6
```
```sample Пример вывода 1
8
```
```sample Пример ввода 2
10 0
```
```sample Пример вывода 2
0
```
Пояснение к примеру 1: в первом случае можно добавлять ингредиенты в зелье в последовательности 1-2-3-2-3-5,
общая сила эффектов 2+1+2+0+3=8. Эффект «3 после 2» добавляется только 1 раз, при первом появлении соответствующей пары.
Компонент 7 не совместим ни с каким другим и его нельзя добавить в зелье, не испортив его.
Пояснение к примеру 2: все 10 ингредиентов несовместимы между собой. Из них нельзя сварить ни одного зелья с положительной силой.
13. Дележ изумрудов
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Правитель Изумрудного города Страшила преподнес в дар добрым волшебницам Севера и Юга мешок замечательных изумрудов. К сожалению,
изумрудов оказалось нечетное количество, и справедливо разделить их пополам оказалось непростой задачей. Поэтому волшебницы договорились
упростить Страшиле задачу следующим образом: во-первых, один из изумрудов можно распилить на 2 части. Во-вторых, справедливым
дележом волшебницы будут считать любой такой, при котором суммарный вес и суммарное количество изумрудов у волшебниц будет одинаковым.
Помогите Страшиле достичь справедливости.
В первой строке ввода находится нечетное натуральное число N (`1<=N<10^5`) – количество изумрудов. Во второй строке ввода
находятся `N` положительных вещественных чисел - веса изумрудов (`1<=W_i<=100`).
В первой строке выведите 2 числа: натуральное `x` (`1<=x<=N`) — номер изумруда, который нужно распилить, и вещественное `W` (`0<W<W_x`) – вес части,
которую нужно отделить от изумруда номер `x`. Отпиленная часть весом `W` будет считаться новым изумрудом с номером `N+1`, а вес изумруда
номер `x` уменьшится на `W`.
Во второй строке укажите `(N+1)//2` натуральных чисел: номера изумрудов (от 1 до `N+1` включительно и не повторяются),
которые нужно отдать волшебнице Севера. Все остальные `(N+1)//2` изумрудов достанутся волшебнице Юга.
Ответ будет считаться верным, если суммы весов изумрудов Севера и Юга будут отличаться с относительной погрешностью не более, чем `10^{-6}`. Если
существует несколько решений, выведите любое из них. Гарантируется, что хотя бы одно решение всегда существует.
```sample Пример ввода
7
2.0 1.0 1.0 5.0 7.0 3.0 2.0
```
```sample Пример вывода
1 0.5
1 2 3 5
```
Пояснение: после распиливания изумруды имеют веса 1.5, 1, 1, 5, 7, 3, 2, 0.5. Северу достанутся изумруды 1, 2, 3, 5 с весами 1.5 + 1 + 1 + 7 = 10.5. Югу достанутся изумруды 4, 6, 7, 8 с весами 5 + 3 + 2 + 0.5 = 10.5.
14. Ограда
Ограничения: время – 600ms/1200ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
У Страшилы есть несколько прямых секций забора. Необходимо окружить забором часть поля
пшеницы как можно большей площади. Можно использовать не все секции, но секцию нужно использовать
полностью (секции можно соединять только краями, не к точкам внутри).
Помогите Страшиле найти максимальную площадь огороженного поля.
В первой строке содержится одно целое число `N` (`3<=N<=1000`).
В второй строке содержится `N` целых чисел от 1 до 1000 — длины секций забора.
Вывести одно вещественное число – максимальную площадь с *относительной* точностью `10^{-7}`.
```sample Пример ввода
4
3 4 5 13
```
```sample Пример вывода
6.0000000
```
Начало
Соревнования
Комбинаторика, теория Пойа