Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Морской бой - 3#30781

Всем известна увлекательная игра «Морской бой». Сейчас играть в Морской бой можно не только с соседом по парте, но и с компьютером. Игра c компьютером ведется на прямоугольном поле произвольных размеров N×M, где N - количество строк, M - количество столбцов. Приближается чемпионат мира по Морскому бою. Планируется вести его трансляцию в режиме реального времени: демонстрировать карту с кораблями и выводить статистику: количество целых, подбитых и уничтоженных кораблей, находящихся на поле. Требуется написать программу для подсчета статистики.

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

Входные данные
Первая строка содержит два целых числа N и M ($1<= N,M <= 10^3$), разделённых пробелами. Это размеры игрового поля. Далее идут N строк по M символов - описание игрового поля. Английская буква 'X' обозначает подбитую клетку корабля, 'S' - не подбитую клетку корабля, '-' – свободное водное пространство.

Выходные данные
В ответе выведите через пробел три числа:
- количество целых кораблей;
- количество подбитых кораблей;
- количество уничтоженных кораблей.

Примеры

№	Входные данные	Выходные данные
1	3 8 ---SSS-- XX--S-X- X-S---S-	2 1 1

Очередь

✓ 269✗ 352800средняяВойти и решать

Упрощение номеров#30776

Как, вы не можете запомнить 6 или 7-значный номер телефона, появившийся на секунду на экране телевизора?! С помощью специальной методики, описываемой далее, Вы превратитесь в ходячий телефонный справочник!

Очевидно, что число 402 запомнить легче, чем число 110010010, а число 337377 запомнить легче, чем число 957472. Значит, нужно чтобы запоминаемое число, с одной стороны, содержало как можно меньше цифр, а с другой стороны, желательно, чтобы в числе было как можно больше повторяющихся цифр. В качестве критерия сложности запоминания примем сумму количества цифр в числе и количества различных цифр в числе. Запоминаемое число можно записать в другой системе счисления, возможно, тогда его окажется легче запомнить. Например, число 65535 в шестнадцатеричной системе исчисления выглядит как FFFF.
Напишите программу подбора основания системы счисления для минимизации критерия сложности. Основание системы счисления нужно выбирать в диапазоне от 2 до 36, тогда для представления числа можно использовать цифры 0-9 и английские буквы A-Z.

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

Первая строка содержит в первой строке целое число n ($1 <= n <= 100$). Далее следует n строк, каждая строка содержит целое число от 1 до 999999999.

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

Ответ должен содержать n строк. Для каждого из n заданных чисел строка содержит: основание системы счисления (от 2 до 36), минимизирующее критерий сложности запоминания, и число в выбранной системе исчисления, разделенные одним пробелом. Если несколько оснований дают одинаковое значение критерия, то выбрать наименьшее среди них.

Пример

№	Входные данные	Выходные данные
1	2 2 65535	3 2 16 FFFF

Разные системы счисления

✓ 38✗ 73900средняяВойти и решать

Максимальное произведение смежных элементов#30768

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

Примеры

№	Входные данные	Выходные данные
1	7 2 3 -2 -3 -1 4 6	72

Пояснения: наибольшее произведение можно получить для последовательности -3 -1 4 6.

ЕГЭ - вычислительные задачи

✓ 118✗ 246900средняяВойти и решать

Тройки чисел#30756

Напишите программу, находящую количество троек целых чисел a, c, p таких, что p — простое число, числа удовлетворяют равенству: $$ \sqrt{a} - \sqrt{c} = \sqrt{p}. $$ Каждое из чисел a, c и p лежит в промежутке от N до M (то есть $N<=a<= M,\ N<=c<= M,\ N<=p<= M$).

Входные данные
Вводятся два целых числа N и M ($0<=N<=M<=100000$).

Выходные данные
Выведите искомое количество троек чисел a, c, p.

Примеры

№	Входные данные	Выходные данные
1	1 8	1
2	5 20	1
3	1 7	0

Простые числа и разложение на множители

✓ 123✗ 785900средняяВойти и решать

Покраска забора#30713

Том Сойер уговорил n своих друзей помочь ему в нелегком деле покраски забора, окружающего дом тетушки Полли. Забор представляет собой k последовательных досок, пронумерованных от 1 до k, причем после k-й доски опять идет первая.

Друзья Тома очень привередливы, i-й друг согласен участвовать в покраске только в том случае, если ему дадут покрасить участок из ровно ai последовательных досок. Кисточка у Тома только одна, поэтому друзья будут красить по очереди и сразу весь отведенный им отрезок. Тому остается лишь выбрать порядок, в котором приглашать друзей, а также выбрать для каждого желаемое количество последовательных досок.

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

Помогите Тому понять, сколько радости он сможет доставить своим друзьям.

Формат входных данных
Первая строка входного файла содержит два целых числа n (1 ≤ n ≤ 10⁵ ) и k (1 ≤ k ≤ 10⁹ ). Следующая строка содержит n целых чисел — значения a_i (1 ≤ a_i ≤ k).

Формат выходных данных
Выведите одно число — максимальное возможное значение x.

Ввод	Вывод
2 100 5 10	5
4 10 7 8 3 5	2

Пояснение
В первом примере x = 5, так как один из друзей просто не хочет красить больше пяти досок. Он придет первым, покрасит свои пять, после чего еще 10 неокрашенных досок достанется второму другу Тома. Оставшиеся 85 досок Тому придется красить самому.
Во втором примере достичь x = 2 можно, например, так. Сначала третий друг красит доски с 4 по 6 (3 неокрашенных доски). Затем четвертый друг красит доски с 1 по 5 (3 неокрашенных доски). Затем второй друг красит доски с 1 по 8 (2 неокрашенных доски). Наконец, первый друг красит доски с 6 по 10 и с 1 по 2 (2 неокрашенных доски, заметим, что забор идет по циклу и эти доски образуют последовательный отрезок).

Сканирующая прямая

✓ 20✗ 2201 000средняяВойти и решать

Защищенное соединение#30707

В свете недавних новостей о прослушке каналов связи, два непримиримых интернет-гиганта Урагании <<Laim.UR>> и <<Xenda>> решили подписать соглашение об установлении защищенного канала связи между дата-центрами друг друга. В Урагании $n$ городов, но, к сожалению, ни в одном городе нет дата-центров обоих гигантов. Поэтому для формирования защищенного канала придется прокладывать междугородние линии связи.

Специалисты компаний определили $m$ пар городов, которые можно соединить, проложив сегмент канала связи, и оценили стоимость создания такого сегмента для каждой из этих пар.

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

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

Формат входных данных
В первой строке находятся целые числа $n$ и $m$ ($2 \le n \le 5\,000$, $1 \le m \le 10^5$) — количество городов и количество пар городов, которые можно соединить сегментом канала связи.

Во второй строке находятся $n$ целых чисел $a_i$ ($0 \le a_i \le 2$). Если $a_i = 0$, то в $i$-м городе нет дата-центра ни одного из гигантов. Если $a_i = 1$, то в $i$-м городе есть дата-центр <<Laim.UR>>, а если $a_i = 2$, то в $i$-м городе находится дата-центр <<Xenda>>. Гарантируется, что среди этих чисел есть как минимум одна единица и одна двойка.

В каждой из следующих $m$ строк находится по три целых числа — $s_i$, $t_i$ и $c_i$, которые означают, что города $s_i$ и $t_i$ ($1 \le s_i, t_i \le n$, $s_i \ne t_i$) можно соединить сегментом канала связи стоимостью $c_i$ ($1 \le c_i \le 10^5$). Каждую пару городов можно соединить не более чем одним сегментом канала.

Формат выходных данных
Если соединить защищенным каналом связи два дата-центра разных интернет-гигантов возможно, то выведите в выходной файл три числа: $x$, $y$ и $d$, означающие, что между городами $x$ и $y$ возможно провести канал связи суммарной стоимостью $d$. В городе $x$ должен находиться дата-центр <<Laim.UR>>, в городе $y$ — дата-центр <<Xenda>>. Если существует несколько оптимальных ответов, выведите любой. Если провести искомый канал невозможно, выведите $-1$.

В первом примере оптимально построить канал связи из двух сегментов: $3-2$ и $2-4$.

Алгоритм Дейкстры

✓ 68✗ 1621 000средняяВойти и решать

Заправки-2#30702

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

В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-й, потратив как можно меньшее денег.

В каждом городе можно заправить бак, заправить бак и канистру или же перелить бензин из канистры в бак. Это позволяет экономить деньги, покупая бензин в тех городах, где он стоит дешевле, но канистры хватает только на одну заправку бака!

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

В первой строке вводится число N (1<=N<=100), в следующей строке идет N чисел, i-е из которых задает стоимость бензина в i-м городе (всё это целые числа из диапазона от 0 до 100). Затем идет число M – количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами – номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.

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

Требуется вывести одно число – суммарную стоимость маршрута или -1, если добраться невозможно.

Алгоритм Дейкстры

✓ 133✗ 443900средняяВойти и решать

Банды Фомина#30691

Банда Фомина состоит из n групп, в каждой из которых a_i человек. Планируется провести q рейдов. В i-ом рейде будет участвовать ровно один разбойник из каждой группы, номер которой лежит в отрезке $[l_i, r_i]$.

Мелехов тоскует, поэтому для каждого рейда он решил посчитать количество возможных отрядов по модулю $10^9 + 7$. Однако Григорий постоянно находится в раздумьях о смысле жизни и поиске правды, поэтому он не может сконцентрироваться на расчетах и просит вас помочь.

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

В первой строке дано число n ($1 <= n <= 10^5$) – количество групп в банде Фомина.

Во второй строке дано n натуральных чисел a_i ($1 <= a_i <= 2$) – количество человек в i-ой группе.

В третьей строке дано число q – количество рейдов.

Далее дано q строк, в каждой из которых дано два числа – l_i и r_i ($1 <= l_i <= r_i <= n$) – номера групп, участвующих в i-ом рейде.

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

Выведите q чисел, каждое в отдельной строке – ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	6 1 2 1 1 2 2 3 1 3 3 4 2 6	2 1 8

Префиксные суммы(минимумы, ...)

✓ 29✗ 195900средняяВойти и решать

Отрезки#30685

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

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

В частности, считайте, что если один отрезок заканчивается в точке x, а другой отрезок начинается в точке x, то эти два отрезка лежат в одной компоненте связности.

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

В первой строке следует целое число n (1 ≤ n ≤ 200 000) — количество отрезков.

i-я из следующих n строк содержит два целых числа li и ri (1 ≤ li < ri ≤ 10⁹) — координаты левого и правого концов отрезка номер i. Отрезки перечислены в порядке их добавления на белую прямую.

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

Выведите n целых чисел — количество компонент связности из черных отрезков после каждого добавления отрезка.

Примеры

№	Входные данные	Выходные данные
1	3 1 3 4 5 2 4	1 2 1
2	9 10 20 50 60 30 40 70 80 90 100 60 70 10 40 40 50 80 90	1 2 3 4 5 4 3 2 1

Множества

✓ 54✗ 164900средняяВойти и решать

Финал#30658

Ежегодно в Санкт-Петербурге, Барнауле и некоторых городах ближнего зарубежья проходят соревнования по программированию. Эти соревнования проходят в рамках студенческого чемпионата мира по программированию, организованного одной из самых авторитетных ассоциаций АСМ (Association for Computing Machinery). На этих соревнованиях проходит отбор команд с Северо-Восточного Европейского Региона NЕЕRС (North-Eastern European Regional Contest). Ежегодно перед организаторами соревнований встает проблема определения команд, которые будут приглашены к участию в финале чемпионата мира по программированию. По новым правилам в финал проходят не более N команд, представляющих NEERC. Кроме этого, от одного вуза не может проходить более чем k команд. При этот из всех таких множеств выбирается то, в котором сумма мест занятых этими командами в полуфинальных соревнованиях минимальная возможная. Ваша задача по итоговому протоколу полуфинальных соревнований и числам N и k определить, какие команды будут приглашены к участию в финале чемпионата мира.

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

В первой сроке входного файла находится три натуральных числа Р (1 ≤ P ≤ 100000) — количество команд, принявших участие в полуфинале, N (1 ≤ N ≤ P ) и k (1 ≤ k ≤ P ) . В следующих P строках, по одному в строке перечислены названия университетов, команды которых заняли соответствующие места. Название университета содержит строчные и прописные латинские буквы и пробелы. Длина названия университета не превышает 30 символов. В следующей строке перечислены номера команд соответствующих университетов. Таким образам если название университета записано в i -той строке (2 ≤ i ≤ P + 1) , то эта команда заняла i - 1 место на полуфинале и имеет номер, записанный на i - 1 месте в P + 2 строке.

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

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

Пример

№	Входные данные	Выходные данные
1	9 5 2 Fantasy University Crazy University Fantasy University Fantasy University Very Good U Good U Very Good U Crazy University Good U 1 1 2 3 2 1 1 2 2	Fantasy University #1 Crazy University #1 Fantasy University #2 Very Good U #2 Good U #1

Словари

✓ 366✗ 663800средняяВойти и решать

Cart Sorting#29658

У Акакия есть колода, состоящая из n карт. На каждой карте написано ровно одно целое число от 1 до 100 000. Возможно, что на некоторых картах написаны одинаковые числа.

Акакий решил отсортировать все карты в колоде. Для этого он по очереди берёт одну верхнюю карту из колоды и если число, написанное на ней, равно минимальному среди всех оставшихся чисел в колоде, он откладывает эту карту в сторону. В противном случае, Акакий кладёт эту карту вниз колоды и берёт сверху колоды следующую карту. Процесс заканчивается, когда в колоде не останется карт. Можно считать, что Акакий в любой момент времени знает минимальное число, записанное на какой-то из оставшихся в колоде картах, но не знает, где эта карта (или карты) находится в колоде.

Перед вами стоит задача определить суммарное количество раз, которое Акакий посмотрит верхнюю карту из колоды.

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

В первой строке следует целое положительное число n (1 ≤ n ≤ 100 000) — количество карт в колоде.

Во второй строке следует последовательность из n целых положительных чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 100 000), где a_i равно числу, написанному на i-й сверху карте из колоды.

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

Выведите суммарное количество раз, которое Акакий посмотрит верхнюю карту из колоды.

Ввод	Вывод
4 6 3 1 2	7
1 1000	1
7 3 3 3 3 3 3 3	7

Примечание

В первом примере Акакий посмотрит сначала карту с числом 6, положит ее вниз колоды, затем карту с числом 3, также положит ее вниз колоды, и затем карту с числом 1. Он отложит карту с числом 1, так как на ней написан минимальное число из оставшихся в колоде. После этого карты в колоде будут лежать в порядке [2, 6, 3] сверху вниз. После этого Акакий посмотрит верхнюю карту с числом 2 и отложит её. После этого карты в колоде будут лежать в порядке [6, 3] сверху вниз. Затем Акакий посмотрит карту с числом 6, положит ее вниз колоды, а затем карту с числом 3, которую отложит. После этого в колоде останется одна карта с числом 6, которую Акакий посмотрит и отложит. Таким образом, Акакий посмотрит 7 карт.

(с) Курбатов Е., 2018

Декартово дерево

✓ 1✗ 31 100средняяВойти и решать

Рубка деревьев#29655

Чубатый учит Григория Мелехова выполнять баклановский удар шашкой. В качестве целей, они используют n деревьев, стоящих в ряд и пронумерованных от 1 до n. Чубатый, оценил прочность всех деревьев натуральными числами, и записал их. За каждое дерево, которое Мелехов смог разрубить, он получает количество очков равное числу, записанному на дереве, а если не смог - то теряет столько же.

Чубатый просит Григория выполнить удары на деревьях с l по r, в порядке возрастания их номеров. Мелехов недавно ушиб плечо, потому он может успешно срубить дерево через раз, т. е. если он срубил дерево с номером i, то он не сможет срубить дерево с номером i + 1, но сможет срубить дерево с номером i + 2 и т. д.

Чубатый m раз попросил Григория выполнить удары, но он забыл, какие деревья Мелехов смог срубить. Помогите ему определить, сколько очков набрал Григорий за каждую попытку.

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

В первое строке содержатся 2 числа n и m ($1 <= n, m <= 100000$)

Во второй строке содержатся n чисел - прочность всех деревьев, где на позиции i написана прочность дерева i.

В следующих m строках содержатся пары чисел l и r ($1 <= l <= r <= n$), означающие какой отрезок деревьев попросил срубить Чубатый.

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

На каждый запрос выведите сколько очков в эту попытку заработал Григорий.

Примеры

№	Входные данные	Выходные данные
1	6 6 1 2 3 4 5 6 1 6 1 5 2 6 2 5 2 4 2 2	-3 3 4 -2 3 2

Префиксные суммы(минимумы, ...)

✓ 39✗ 84800средняяВойти и решать

Поиск числа на отрезке#29653

Дан массив a длины n ($1 <= n <= 10^6$, $1 <= a_i <= 10^9$). Также даны m ($1 <= m <= 500$) запросов вида +, l, r, k ($1 <= l <= r <= n$, $-10^9 <= k <= 10^9$) и запросов вида ?, l, r, k ($1 <= l <= r <= n$, $-10^9 <= k <= 10^9$).

В первом случае нужно добавить к числам на отрезке от l до r включительно, число k.
Во втором случае нужно вывести 1, если на отрезке от l до r включительно, есть число k, иначе вывести 0.

Элементы нумеруются с 1 до n.

Гарантируется, что после любого запроса любой элемент массива a лежит в диапазоне от $-10^9$ до $10^9$ включительно.

Примеры

№	Входные данные	Выходные данные
1	5 1 2 1 1 3 3 ? 1 4 3 + 2 3 2 ? 1 4 3	0 1

sqrt декомпозиция

✓ 6✗ 311 000средняяВойти и решать

Умножение на отрезке#29652

Дан массив a длины n ($1 <= n <= 2 \cdot 10^6$, $1 <= a_i <= 10^9$). Также даны m ($1 <= m <= 500$) запросов вида *, l, r, k ($1 <= l <= r <= n$, $0 <= k <10$) и запросов вида ?, i ($1 <= i <= n$).

В первом случае нужно умножить числа на отрезке от l до r включительно на k.

Во втором случае нужно вывести число, стоящее на позиции i.

Элементы нумеруются с 1 до n.

Примеры

№	Входные данные	Выходные данные
1	5 1 1 1 1 1 3 ? 3 * 2 3 9 ? 3	1 9

sqrt декомпозиция

✓ 15✗ 66800средняяВойти и решать

Максимум на матрице#29651

Дана матрица a размером $n \cdot n$ ($1 <= n <= 1000$, $1 <= a_i <= 10^9$). Также даны m ($1 <= m <= 1000$) запросов вида x₁, y₁, x₂, y₂ ($1 <= x_1 <= n$, $1 <= y_1 <= n$, $x_1 <= x_2 <= n$, $y_1 <= y_2 <= n$).

На каждый запрос нужно вывести максимальный элемент в подматрице с координатами краёв x₁, y₁иx₂, y₂.

Примеры

№	Входные данные	Выходные данные
1	4 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 1 1 1 3 4	6

sqrt декомпозиция

✓ 7✗ 251 000средняяВойти и решать

Сумма на отрезке - 2#29650

Дан массив a длины n ($1 <= n <= 2 \cdot 10^6$, $1 <= a_i <= 10^9$). Также даны m ($1 <= m <= 500$) запросов вида t, l, r ($0 <= t <= 1$, $1 <= l <= r <= n$).

Если $t = 0$, то на запрос нужно вывести сумму чисел на отрезке от l до r включительно. Если $t = 1$, то элементу с номером l присваивается значение r. Элементы нумеруются с 1 до n.

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 4 5 4 0 1 2 1 1 5 0 1 2 0 1 1	3 7 5

sqrt декомпозиция

✓ 19✗ 52800средняяВойти и решать

Сумма на отрезке - 1#29649

Дан массив a длины n ($1 <= n <= 2 \cdot 10^6$, $1 <= a_i <= 10^9$). Также даны m ($1 <= m <= 500$) запросов вида l, r ($1 <= l <= r <= n$).

На каждый запрос нужно вывести сумму чисел на отрезке от l до r включительно. Элементы нумеруются с 1 до n.

Примеры

№	Входные данные	Выходные данные
1	4 1 2 3 4 2 1 4 1 1	10 1
2	5 5 5 5 5 5 1 5 5	5

sqrt декомпозиция

✓ 26✗ 252900средняяВойти и решать

Тихий Дон №3#29638

Наталья Коршунова очень скучает по Григорию Мелехову и хочет вернуться к нему. Но, к сожалению, Григорий любит Аксинью, поэтому Наталья решила доказать любимому, что она лучше нее.

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

Григорий дает Наталье массив A, состоящий из n целых неотрицательных чисел. Затем он просит ее сделать q однотипных операций, заключающихся в следующем: "Даны числа l, r и k. Далее для каждого индекса i от l до r происходит подстановка числа k вместо числа A_i и считается побитовое исключающее “или” всех чисел на отрезке $[l;r]$, после чего на iое место опять возвращается число A_i".
Таким образом, происходит $r – l + 1$ независимых подстановок, не меняющих массив, и соответственно $r – l + 1$ результатов побитового исключающего “или”. Наталье необходимо сообщить Григорию побитовое исключающее “или” всех результатов подстановок (для лучшего понимания ознакомьтесь с примерами).

Помогите Наталье Коршуновой справиться с этой задачей! Тогда Григорий точно вернется к ней!

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

В первой строке дано целое число n ($1 <= n <= 10^5$) – количество элементов массива.

Во второй строке содержится n целых неотрицательных чисел, не превышающих по значению $10^8$.

В третьей строке дано целое число q ($1 <= q <= 10^5$) – количество запросов.

Далее содержится q строк, в каждой из которых содержится 3 целых числа: l, r, k ($1 <= l <= r <= n$, $0 <= k <= 10^8$).

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

Вам необходимо вывести q ответов на каждый запрос в одной строке через пробел.

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 4 5 2 1 3 7 4 5 10	7 1

Пояснение

Первый запрос:

1) 7 ⊕ 2 ⊕ 3 = 6

2) 1 ⊕ 7 ⊕ 3 = 5

3) 1 ⊕ 2 ⊕ 7 = 4

6 ⊕ 5 ⊕ 4 = 7

Ответ: 7.

Второй запрос:

1) 10 ⊕ 5 = 15

2) 4 ⊕ 10 = 14

15 ⊕ 14 = 1

Ответ: 1.

Префиксные суммы(минимумы, ...)

✓ 66✗ 242800средняяВойти и решать

Вложенный вложенный тернарный поиск: Космические спасатели#29495

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

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

Поскольку планеты достаточно удалены друг от друга, их можно считать точками в евклидовом трехмерном пространстве. Расстояние между точками (x_i, y_i, z_i) и (x_j, y_j, z_j) вычисляется по формуле:

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

Галактика в опасности! Спасите космических спасателей и укажите им искомую точку.

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

В первой строке входного файла содержится целое число n — количество планет (1 ≤ N ≤ 100). Каждая из последующих n строк содержит информация о планетах. i-я из этих строк содержит три целых числа xi, yi, zi — координаты i-й планеты ( - 10⁴ ≤ xi, yi, zi ≤ 10⁴, 1 ≤ i ≤ n). Никакие две планеты не совпадают.

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

В первой строке выходного файла следует вывести три вещественных числа через пробел x₀, y₀, z₀ — координаты будущей базы. Если существует несколько решений, то разрешается вывести любое. Ответ будет засчитан, если расстояние от данной точки до самой удаленной планеты будет отличаться от результата жюри не более чем на 10^-6 по абсолютному или относительному значению.

Ввод	Вывод
5 5 0 0 -5 0 0 0 3 4 4 -3 0 2 2 -2	0.000 0.000 0.000

Тернарный поиск

✓ 8✗ 61800средняяВойти и решать

Вложенный тернарный поиск: футбольные ворота#29484

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

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

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

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

В единственной строке записаны целые числа a, b — длины палок ($1 <= a, b <= 10 000$). Известно, что суммарная длина палок строго меньше высоты берёзы.

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

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

Примеры

№	Входные данные	Выходные данные
1	2 2	4.828427125

Источник: Уральская региональная командная олимпиада по программированию 2011

Тернарный поиск

✓ 34✗ 78900средняяВойти и решать