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

Генераторы квадратов#48941

Множество \(A = \{a_1, a_2, \ldots, a_k\}\) различных натуральных чисел с суммой \(a_1+a_2+\ldots+a_k=n\) называется генератором квадратов, если сумма любых \(k-1\) элементов этого множества является полным квадратом целого числа.

Например, множество \(\{1, 22, 41, 58\}\) является генератором квадратов, так как \(1 + 22 + 41 = 64 = 8^2\), \(1 + 22 + 58 = 81 = 9^2\), \(1 + 41 + 58 = 100 = 10^2\), \(22 + 41 + 58 = 121 = 11^2\).

По заданным \(n\) и \(k\) постройте множество из \(k\) различных натуральных чисел с суммой \(n\), которое является генератором квадратов, либо выясните, что такого нет.

Формат входных данных
На ввод подаются два целых числа \(n\) и \(k\) (\(2 \le n \le 200\,000\), \(2 \le k \le 30\)).

Формат выходных данных
Если искомый генератор квадратов существует, выведите <<YES>> на первой строке, а на второй строке выведите \(k\) натуральных чисел "— искомое множество.

Если генератора квадратов с заданными параметрами не существует, выведите <<NO>>.

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

Подъемник#47205

На стройку многоэтажного дома завезли инструменты. Прорабу необходимо доставить инструменты с этажа A на этаж B. Для вызова подъемника на всех этажах строящегося здания, кроме первого и последнего, есть две кнопки. Кнопка вниз перемещает подъемник вниз, кнока вверх - перемещает вверх. Когда прораб нажал нужную кнопку, подъемник находился на этаже С и вез груз на этаж D. Работает подъемник следующим образом:

если подъемник проезжает мимо этажа, на котором нажата кнопка вызова, и, при этом, движется в подходящем направлении, то подъемник останавливается и в него можно зайти.

Подъемник перемещается между соседними этажами за одну единицу времени, также одну единицу времени занимает остановка подъемника на этаже для загрузки или разгрузки.

Определите сколько времени необходимо прорабу, чтобы доставить инструменты до этажа B, при условии, что никто больше не будет вызывать подъемник.

Входные данные
Первая строка ввода содержит четыре целых числа A, B, C и D, разделенных одним пробелом (1 <= A, B, C, D <= 20, A≠B, C≠D, A≠C).

Выходные данные
Вывести одно целое число – количество единиц времени, которое пройдет с момента вызова подъемника до момента, когда инструменты разгрузят из подъемника на этаже B.

Примеры

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

Примечание

Пояснение к примеру 1

Подъемник за 1 единицу времени доедет до 3-го этажа, остановится на 1 единицу времени, чтобы прораб смог погрузить инструменты на подъемник, затем через 2 единицы времени доедет до 5-го этажа и остановится на 1 единицу времени для разгрузки груза, через 4 единицы времени подъемник довезет инструменты до 9-го этажа, и через 1 единицу времени инструменты рагрузят.

Вывод формулы Условный оператор

✓ 0✗ 191 200средняяВойти и решать

Массив сумм#44508

Юля выписала на доску n последовательных натуральных чисел a, a+1, …, a+n−1 и написала под каждым из них сумму его цифр в десятичной записи, под i-м числом было выписано sum_i.

После этого Юра стёр исходные числа и оставил только их суммы цифр. От вас требуется восстановить первое число в исходной последовательности a.

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

В первой строке содержится одно целое число n (2 <= n <= 100000) - длина исходной последовательности.

В следующей строке содержатся n целых чисел sum₁, sum₂, …, sum_n (1 <= sum_i<= 90) - суммы цифр чисел исходной последовательности.

Гарантируется, что для всех тестов существует подходящее a, такое что 1 <= a <= 10¹⁸.

Выходные данные
Выведите одно число a (1 <= a <= 10¹⁸) - первое число исходной последовательности. В случае, если существует несколько подходящих a, можно вывести любое.

Примечание

В первом тестовом примере сумма цифр 1 равняется 1, сумма цифр 2 равняется 2, сумма цифр 3 равняется 3, что соотносится с массивом sum, поэтому a = 1 подходит под условие задачи.

Во втором тестовом примере сумма цифр 77 равняется 14, сумма цифр 78 равняется 15, сумма цифр 79 равняется 16, сумма цифр 80 равняется 8, сумма цифр 81 равняется 9, что соотносится с массивом sum, поэтому a = 77 подходит под условие задачи.

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3	1
2	5 14 15 16 8 9	77

Вывод формулы Задачи на моделирование

✓ 5✗ 1381 200средняяВойти и решать

Раз-два-три-четыре-пять корову поменять#39514

N коров (1 ≤ N ≤ 10⁵) Фермера Джона стоят в ряд. i-ая корова слева имеет метку i (1 ≤ i ≤ N).
ФД дал коровам M пар целых чисел s (L₁,R₁)…(L_M,R_M), где 1 ≤ M ≤ 100. Затем он сказал коровам повторить ровно K (1 ≤ K ≤ 10⁹) раз процесс из M шагов:

Для каждого i от 1 до M:
Последовательность коров на позициях Li…Ri слева реверсивно меняют свой порядок.
Выведите метки всех коров слева направо для каждого i, (1 ≤ i ≤ N) после завершения описанного процесса.

Входные данные
Первая строка содержит числа N, M, K. Для каждого 1 ≤ i ≤ M строка i+1 содержит L_i и R_i, два целых числа в интервале 1…N, где L_i<R_i.

Выходные данные
На i-ой строке вывода, выведите i-ый элемент массива после выполнения всех инструкций K раз.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 2 2 2 5 3 7	1 2 4 3 5 7 6	Изначально порядок коров слева направо такой [1,2,3,4,5,6,7] После первого шага процесса порядок станет таким [1,5,4,3,2,6,7] После второго шага процесса порядок станет таким [1,5,7,6,2,3,4]. Повторив оба шага ещё раз получим результат, приведенный в выводе.

Быстрое возведение в степень Вывод формулы Перестановки

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

Треугольники - 2#39513

Фермер Джон хочет создать треугольное пастбище для своих коров.
Всего имеется N столбов забора (3 ≤ N ≤ 10⁵) как различных (X₁,Y₁)…(X_N,Y_N) точек на карте фермы. Он может выбрать три из них чтобы сформировать вершины треугольного пастбища, но так чтобы одна из сторон была параллельна оси x, а другая - параллельно оси y.

Какова сумма площадей всех возможных пастбищ, которые может сформировать ФД?

Входные данные
Первая строка содержит N.
Каждая из последующих N строк содержит два целых числа Xi и Yi, каждое в интервале −10⁴…10⁴ включительно, описывающих положение столба.

Выходные данные
Поскольку сумма площадей может быть числом не целым и очень большим, выведите остаток от деления удвоенной суммы площадей на 10⁹+7.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 0 0 0 1 1 0 1 2	3	Точки (0,0), (1,0), (1,2) образуют треугольник с площадью 1. Точки (0,0), (1,0), (0,1) образуют треугольник с площадью 0.5. Поэтому ответ 2⋅(1+0.5)=3.

Алгоритмы сортировки Вывод формулы

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

Тюрьма для Зедда#38918

Черный рейнджер нашел в жерле заброшенного вулкана n прямоугольных листов металла разного размера, i-й лист имеет размер a_i на b_i метров.
Зордон поручил построить Черному рейнджеру тюрьму для злобного генерала Зедда, и эта находка оказалась для него просто подарком судьбы. Тюрьма должна иметь вид прямоугольного параллелепипеда каждая грань которого представляет собой цельный лист металла. Так что рейнджер собирается взять 6 из найденных им листов металла, сложить из них параллелепипед, и показать его Зордону. Листы нельзя гнуть или разрезать, листы, из которых будет сложена тюрьма не должны выступать за её края.
Поскольку чем больше тюрьма, чем надежнее, параллелепипед должен иметь максимальный возможный объем. Помогите герою выбрать 6 листов прямоугольников так, чтобы собрать из них самую большую тюрьму.
Листы можно поворачивать, таким образом, например, листы 4 на 7 метров и 7 на 4 метра считаются одинаковыми.

Формат входных данных
В первой строке дано одно число n — количество листов металла у Черного Рейнджера (6 ≤ n ≤ 200 000).
В следующих n строках даны пары чисел a_i; b_i — размеры i-го куска металла (1 ≤ a_i; b_i ≤ 10⁶).

Формат выходных данных
Выведите одно целое число — максимальный объем прямоугольного параллелепипеда, который можно собрать из этих кусков металла.
Если из данных листов невозможно собрать прямоугольный параллелепипед, выведите -1.

Примеры

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

Вывод формулы Задача на реализацию Разбор случаев

✓ 0✗ 81 200средняяВойти и решать

Двухтуровая олимпиада#38358

Как известно, личная олимпиада по информатике проходит в два тура. На каждом из туров участники получают какие-то баллы, при этом итоговый балл определяется как сумма полученных баллов. Известны баллы, которые каждый участник получил на каждом из туров. Жюри хочет фальсифицировать итоги олимпиады так, чтобы победил «нужный» участник.

При этом жюри может делать следующие «подтасовки» (можно делать несколько «подтасовок» применительно как к одному и тому же, так и к разным турам):

Прибавить к результатам всех участников по одному из туров одно и то же положительное число.
Умножить результаты участников по одному из туров на некоторый коэффициент, больший 1.
При этом должна сохраниться правдоподобность результатов, которая заключается в том, что никто из участников не должен получить больше 100 баллов за каждый из туров.

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

Входные данные
Во входном файле записано сначала число участников N (1 ≤ N ≤ 1000), затем N пар чисел — результаты каждого участника за 1-й и за 2-й туры (результат участника за тур — это вещественное число от 0 до 100) не более, чем с 3 знаками после десятичной точки.

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

Примеры

№	Входные данные	Выходные данные
1	4 45 90 70 80 0 0 75 75	2 2 4

Вывод формулы Разбор случаев

✓ 3✗ 61 200средняяВойти и решать

Разбиение последовательности#32948

Последовательность натуральных чисел от 1 до `N` нужно разбить на две части от 1 до `K` и от `K+1` до `N` так, чтобы абсолютное значение разности суммы чисел в первой и второй части последовательности было как можно меньше. То есть нужно найти такое `K`, что значение выражения `|\ sum_{i=1}^K\ i\ -\ sum_{i=K+1}^N\ i\ |` минимально. Например, для последовательности чисел от 1 до 4 разбиение будет минимальным для `K=3`, так как `|\ (1+2+3)-(4)\ |\ =\ 2`, что меньше значения разности для `K=1` равного `|\ (1)-(2+3+4)\ |\ =\ 8` и для `K=2` равного `|\ (1+2)-(3+4)\ |\ =\ 4`.

Напишите программу, которая для заданного `N` находит минимальное разбиение.

Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 10^9`).

Вывести одно целое число `K`. Если существует несколько вариантов разбиения, то вывести меньшее из возможных `K`.

Ввод	Вывод
4	3

Вывод формулы Вычисление по заданной формуле

✓ 2✗ 351 300средняяВойти и решать

Идеальный сад#22026

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

возникла идея завести сад из синих и красных цветов на заднем дворе своего коттеджа. Ежедневная работа с таблицами ему изрядно надоела,

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

граница между синими и красными должна быть на одинаковом расстоянии L от него.

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

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

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

радиус сада R, но расстояние от кресла на веранде до центра сада он попросил посчитать Вас.

Входной файл содержит целое число R - радиус сада (1 < R < 10000) и целое число L - расстояние от кресла до границы между синими и красными

цветами (1 < L < 10000). Ваша задача вывести расстояние от кресла на веранде до центра сада. Ответ округлите до сотых, или выведите -1,

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

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

12 15

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

13.262

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

100 1

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

-1

(с) Линд Владимир

Вывод формулы Элементарная геометрия

1 300средняяВойти и решать

Разности#21846

У Джона Доу есть массив a из n элементов. Джон хочет найти величину , то есть сумму квадратов разностей элементов массива по всем возможным парам i, j.

Например для массива {1, 2, 3} такая величина будет равна (1 - 1)2 + (1 - 2)2 + (1 - 3)2 + (2 - 1)2 + (2 - 2)2 + (2 - 3)2 + (3 - 1)2 + (3 - 2)2 + (3 - 3)2 = 0 + 1 + 4 + 1 + 0 + 1 + 4 + 1 + 0 = 12

Найдите остаток от деления S на 10⁸.

Напомним, как работать с остатками от деления. Остаток от деления числа a на число b обозначим как . Верны следующие соотношения:

(для a ≥ b).

К примеру, вы хотите посчитать величину . Перемножить эти три числа в стандартном типе данных вам не удастся, но можно воспользоваться первым соотношением и посчитать сначала Теперь можно перемножить получившееся число и 107 + 3 и получить .

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

В первой строке записано целое число n (1 ≤ n ≤ 10⁶) — количество элементов массива. Во второй строке через пробел записаны n целых чисел a1, ..., an (1 ≤ a_i ≤ 10⁹).

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

Выведите остаток от деления S на 10⁸.

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

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

3
1 2 3

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

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

5
100 1 9 1 3

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

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

2
1000000000 1

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

Примечание

Тесты поделены на несколько групп, но оцениваются отдельно.

n, a_i ≤ 1000 – 10 баллов
n ≤ 5000 – 10 баллов
n ≤ 10⁶ a_i≤ 5000 – 30 баллов
Без дополнительных ограничений — 50 баллов

Например, если вы решили задачу для n ≤ 5000 и произвольных a_i вы получите 20 баллов (первая и вторая группы).

Вывод формулы Вычисление по заданной формуле

✓ 2✗ 1141 200средняяВойти и решать

21743#21743

Написание конспекта является процессом

1. сбора информации
2. обработки информации
3. хранения информации
4. передачи информации

Вывод формулы

1 200труднаяВойти и решать