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

Universe#21788

Наша вселенная представляет собой n-мерный прямоугольный параллелепипед. Множество измерений вселенной B = {a[i] : 1<=i<=n}.

Множество B такого, что его первые b элементов являются измерениями b-мерного подпараллелепипеда.

Перед учеными встал ряд вопросов типа: какое пространство находится внутри k-мерного подпараллелепипеда, если предположить, что пространство внутри m-мерного нулевое.

Напишите программу, которая даст ответ на вопросы ученых.

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

Все числа неотрицательные.

В первой строке вводятся целые числа (n, q <= 10^5) размерность нашей вселенной и количество вопросов, интересующих ученых соответственно.

Во второй строчке вводятся n целых чисел - измерения вселенной, каждое из которых не превосходит (10^18 - 14)

Далее следует q строк по два числа, однозначно задающие вопрос указанного типа, интересующий ученых - m, k. (m, k <= n)

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

Программа должна выводить q строк по одному числу. На i-ой строке должен распологаться ответ на i вопрос указанного типа.

Пример:

INPUT:

3 1

1 2 3

0 3

OUTPUT:

Пояснение:

Т.к. пространство внутри 0 мерного подпараллелепипеда (точки) нулевое (по условию), то пространство внутри 3-х мерного (пространство внутри 3-х мерного - объем) считается по обычной формуле: 1*2*3 = 6

Автор: Иван Шершнев

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

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

Dank numbers#21778

Число является dank number, если все его цифры идут в неубывающем порядке. Чтобы получить dank kush, Bonkisilver должен назвать все n-значные dank numbers. Вас не просят узнать все такие числа, Вам лишь нужно вывести их количество.

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

На вход подается число n (0 <= n <= 50).

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

Выведите одно число - количество n-значных dank number.

Примеры

№	Входные данные	Выходные данные
1	9	24310

Динамическое программирование

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

Запросы по Флойду#21777

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

Входные данные
В первой строчке дано целое число n - количество вершин в графе. Дальше на вход подается матрица смежности, в которой -1 означает отсутствие ребра между вершинами. После матрицы идет число k - количество запросов, в следующих k строках содержится по 2 числа, a и b - вершины в запросе.

Выходные данные
Выведите k чисел - расстояние между парой чисел из запроса в порядке их ввода, если нельзя добраться из вершины a в вершину b, следует вывести Imp. Каждое число выводится в отдельной строке.

Примеры

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

Алгоритм Флойда

✓ 277✗ 465500лёгкаяВойти и решать

Дейкстра: Расстояние до всех вершин#21776

Дан неориентированный взвешенный граф, необходимо найти расстояние от вершины 1 до всех остальных, используя алгоритм Дейкстры.

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

В 1 строке даны 2 целых числа n и m (n>=1, m >= 0), число вершин и ребер в графе соответсвенно. В следующих m строках дается по 3 числа a и b - вершины которые соединяет ребро и c - вес этого ребра .

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

Необходимо вывести n-1 число через пробел - расстояния от вершины 1 до всех остальных, если нет возможного пути из 1 в i вершину, то необходимо вывести Impossible.

Ввод	Вывод
5 5 1 2 3 2 3 1 3 4 3 1 4 1 4 2 1	2 3 1 Impossible

P.S. Внимательно проверяйте ограничения

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

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

Беллман#21775

Дан ориентированный взвешенный граф с отрицательными ребрами (без отрицательных циклов).

Дана стартовая и конечная вершина, определить минимальное расстояние между ними.

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

Дано 4 числа n, m, s, f - количество вершин, количество ребер, стартовая и конечная вершина(начиная с 1) соответственно.

В следующих m строках содержится по 3 числа - вершина 1, вершина 2 и цена перехода между вершинами.

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

Требуется вывести одно число - ответ на поставленную задачу. Если ответа нет - следует вывести Inf.

Примеры

№	Входные данные	Выходные данные
1	4 2 1 4 1 2 100500 2 3 100500	Inf

Алгоритм Форда-Беллмана

✓ 89✗ 137400лёгкаяВойти и решать

N0SC0P3 360#21774

Джон aka xXx_1337_7R1k$#073R_xXx учится великому искусству стрельбы без прицеливания. Он уже освоил несколько простых выстрелов, и сейчас он учится одному из самых основных - так называемому noscope 360. Это достаточно трудно, но у него наконец-то начало получаться, и теперь он хочет узнать, поразил ли он цель своим выстрелом (который мы представим в виде луча).

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

В первой строке вводятся 2 числа X₀ и Y₀ - координаты точки, в которой стоит Джон (-10 <= X0, Y0 <= 10).

Во второй строке вводятся 2 числа vX и vY - координаты вектора, по которому направлен луч (-10 <= vX, vY <= 10).

В третьей строке вводятся 2 числа X и Y - координаты цели (-50 <= X, Y <= 50).

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

Выведите слово "Yes", если Джону удалось попасть, и "No" в противном случае.

Примеры

№	Входные данные	Выходные данные
1	1 1 -1 1 -2 3	No

Элементарная геометрия

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

Ленивый Вася и релиз Half-Life 3#21773

Свершилось чудо! Наконец-то вышел долгожданный Half-Life 3, о котором мечтали миллионы людей по всему миру! Вася тоже с нетерпением ждал продолжения легендарной серии, и даже не ел в школьной столовой целый месяц, чтобы ему хватило на покупку этого шедевра! Единственная проблема, которая стоит у него на пути - огромное домашнее задание по алгебре. В классе он прошёл новую тему - прямые, и теперь ему нужно сделать аж N задач на построение прямой через 2 точки. Но ведь так хочется поиграть, а на следующий день рассказывать друзьям, какой же там классный графон... Поэтому он попросил Вас, своего друга, помочь ему.

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

В первой строке вводятся координаты первой точки (X₁, Y₁), ($-50 <= X_1, Y_1 <= 50$).

Во второй строке вводятся координаты второй точки (X₂, Y₂), ($-50 <= X_2, Y_2 <= 50$).

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

В единственной строке выведите подряд 3 целых числа: коэффициенты a, b, c уравнения прямой.

Примечание: если у вас не заходит задача, но вы уверены, что всё правильно - попробуйте умножить все коэффициенты на -1. Задача предполагает, что вы использовали формулы, взятые с лекции/теории.

Примеры

№	Входные данные	Выходные данные
1	-1 -1 1 1	-2 2 0

Вычислительная геометрия

✓ 71✗ 65600лёгкаяВойти и решать

Перевод часов#21772

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

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

В первой строке задаётся точка, куда указывает стрелка. Она задаётся координатами X₁ и Y₁ ($-10 <= X_1, Y_1 <= 10$).

Во второй строке задаётся точка, куда должна указывать стрелка. Она задаётся координатами X₂ и Y₂ ($-10 <= X2, Y2 <= 10$).
Координаты задаются вещественным типом.

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

В единственной строке выведите "Clockwise", если стрелку нужно крутить по часовой стрелке, "Counter-clockwise", если её нужно крутить против часовой стрелки, и "Doesn't matter", если это займёт одинаковое время, в какую сторону её бы не крутили. Выводить фразы следует без кавычек.

Примеры

№	Входные данные	Выходные данные
1	1 0 -1 1	Counter-clockwise

Вычислительная геометрия

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

Пикап-мастер#21771

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

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

В первой строке вводятся координаты концов тропинки (X₁, Y₁) и (X₂, Y₂), по которой гуляет Венцеслав ($-20 <= X1, Y1, X2, Y2 <= 20$).

Во второй строке вводится целое число N - количество тропинок, по которым гуляют девушки ($0 <= N <= 5$).

В последующих N строках вводятся координаты концов тропинок, по которым гуляют девушки (X_i1, Y_i1) и (X_i2, Y_i2), по i-ой тропинке гуляет i-ая девушка ($-20 <= X_{i1}, Y_{i1}, X_{i2}, Y_{i2} <= 20$)
Координаты концов тропинок - вещественные числа.

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

В первой строке выведите число M - количество девушек, пути которых пересекутся с путём Венцеслава (касание путей считается пересечением).

Во второй строке выведите M чисел - номера девушек, с которыми встретится наш герой. Девушки нумеруются с единицы!

Примеры

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

Вычислительная геометрия

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

1 - k BFS#21770

Дан ориентированный взвешенный граф. Необходимо найти расстояние от вершины 1 до всех остальных, используя алгоритм 1 - k BFS.

Входные данные
В первой строке даны 2 целых числа n и m, число вершин и ребер в графе соответственно. В следующих m строках дается по 3 числа a и b - вершины которые соединяет ребро и c - вес этого ребра (a, b, c >= 0).

Выходные данные
Необходимо вывести n-1 число через пробел - расстояния от вершины 1 до всех остальных, если нет возможного пути из 1 в i вершину, то необходимо вывести Impossible.

Примеры

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

0-1 BFS

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

Простые числа - 1#21768

Найти количество всех четырехзначных простых чисел, оканчивающиеся на цифру k.

Входные данные
Число k.

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

Примеры

№	Входные данные	Выходные данные
1	1	266
2	0	Absent

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

✓ 794✗ 1 382400лёгкаяВойти и решать

Постулат Бертрана#21767

Постулат Бертрана (теорема Бертрана-Чебышева, теорема Чебышева) гласит, что для любого $n > 1$ найдется простое число p в интервале $n < p < 2n$. Такая гипотеза была выдвинута в 1845 году французским математиком Джозефом Бертраном (проверившим ее до $n=3000000$) и доказана в 1850 году Пафнутием Чебышевым. Раманужан в 1920 году нашел более простое доказательство, а Эрдеш в 1932 – еще более простое.

Ваша задача состоит в том, чтобы решить несколько более общую задачу – а именно по числу n найти количество простых чисел p из интервала $n < p < 2n$.

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

Входные данные
Целое число n ($2 <= n <= 50000$).

Выходные данные
Выведите одно число – ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	3000	353

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

✓ 630✗ 1 075500лёгкаяВойти и решать

21764#21764

Дано натуральное число N (N<=255). Найти сумма цифр данного числа в восьмеричной системе счисления.

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

✓ 52✗ 96600лёгкаяВойти и решать

Максимальная цифра в восьмеричной СС#21763

Дано натуральное число N . Необходимо найти максимальную цифру данного числа при его записи в восьмеричной системе счисления.

Входные данные
На вход подается натуральное число N ($N<=255$).

Выходные данные
Выведите на экран ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	255	7

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

✓ 506✗ 350300лёгкаяВойти и решать

Количество единиц в двоичной СС#21762

Дано натуральное десятичное число N. Найдите количество единиц в двоичной записи данного числа. Ответ вывести в десятичной системе счисления.

Входные данные
На вход подается одно натуральное число N ($N<=255$).

Выходные данные
Выведите на экран ответ на задачу.

Пример

№	Входные данные	Выходные данные
1	100	3

Двоичная система счисления

✓ 588✗ 460300лёгкаяВойти и решать

21761#21761

Можно ли открыть файл собственного формата в бесплатной программе?

1. да
2. нет
3. не всегда
4. в случае, если программа поддерживает этот формат

Задача на реализацию

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

21760#21760

Можно ли открыть файл универсального формата в платной программе?

1. да
2. нет
3. не всегда
4. в случае, если в списке программы есть этот формат

Задача на реализацию

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

21759#21759

Формат графического файла - это

1. название редактора
2. домен файла
3. протокол файла
4. способ представления данных

Кодирование информации

—Войти и решать

21758#21758

Растровое изображение сохраняется в файл как

1. информация о координатах пикселей
2. информация о цвете каждого пикселя
3. информация о координатах и цвете пикселей
4. сетка пикселей

Кодирование графики

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

21757#21757

При уменьшении векторного изображения

1. происходит потеря качества
2. качество не теряется
3. увеличивается объем файла
4. появляется ступенчатый эффект

Кодирование графики

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