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

КП 09#33373

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [258274; 258297], числа, имеющие ровно 4 различных делителя. Выведите эти четыре делителя для каждого найденного числа в порядке возрастания

ЕГЭ_информатика ЕГЭ-25. Поиск делителей числа

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

КП 08#33372

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [222987; 223021], числа, имеющие ровно 4 различных делителя. Выведите эти четыре делителя для каждого найденного числа в порядке возрастания

ЕГЭ_информатика ЕГЭ-25. Поиск делителей числа

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

КП 07#33371

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [113012; 113061], числа, имеющие ровно 4 различных делителя. Выведите эти четыре делителя для каждого найденного числа в порядке возрастания

ЕГЭ_информатика ЕГЭ-25. Поиск делителей числа

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

КП 06#33370

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [251811; 251826], числа, имеющие ровно 4 различных делителя. Выведите эти четыре делителя для каждого найденного числа в порядке возрастания

ЕГЭ_информатика ЕГЭ-25. Поиск делителей числа

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

КП 05#33369

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [150750; 150764], числа, имеющие ровно 4 различных делителя. Выведите эти четыре делителя для каждого найденного числа в порядке возрастания

ЕГЭ_информатика ЕГЭ-25. Поиск делителей числа

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

Type Printer#33314

Вам нужно напечатать N слов на Movable Type Printer. Movable Type Printers — это старые принтеры, для работы которых требуется ставить маленькие металлические кусочки (каждый из кусочков содержит одну букву) в определенном порядке, образуя таким образом слова. Потом все они вдавливаются в лист бумаги. Таким образом печатается одно слово. Ваш принтер позволяет делать следующие операции:

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

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

Каждая из трёх операций занимает одну единицу времени. Вам нужно найти последовательность операций, которая печатает данные N слов за минимальное время. Если минимальных последовательностaей несколько, выведите любую.

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

Ваша программа должна считать следующие входные данные:

На первой строке число N (1<=N<=25000).

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

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

Ваша программа должна вывести следующие данные:

На первой строке M — число операций.

На следующих M строках по одному символу — описание операций. Каждая операция описывается одним символом:

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

Удаление символа обозначается символом «-» (минус, ASCII-код 45).

Операция «напечатать текущее слово» обозначается символом «P» (заглавная латинская буква P).

Ввод	Вывод
3 print the poem	20 t h e P - - - p o e m P - - - r i n t P

Бор Обход в глубину

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

Цепочка слов#33313

Цепочкой слов длины n назовем последовательность слов w₁, w₂, ..., w_n такую, что для 1 ≤ i ≤ n слово wi является собственным префиксом слова w_i + 1.

Напомним, что слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u.

Задано множество слов S = {s₁, s₂, ..., s_m}. Найдите максимальную длину цепочки слов, которую можно построить, используя (возможно, не все) слова этого множества.

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

Первая строка входного файла содержит целое число m(1 ≤ m ≤ 255). Каждая из последующих m строк содержит по одному слову из множества S.

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

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

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

Ввод	Вывод
3 a ab abc	3
5 a ab bc bcd add	2

Бор Обход в глубину

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

Двоичный автомат - 1#33261

Автомат обрабатывает натуральное число N по следующему алгоритму:
1) Строится двоичная запись числа N.
2) Удаляются две последние цифры
3) Полученное число переводится в десятичную запись и выводится на экран.
Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 20 до 600?

ЕГЭ_информатика ЕГЭ-05. Анализ простых алгоритмов

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

Двоичный автомат - 2#33260

Автомат обрабатывает натуральное число N по следующему алгоритму:
1) Строится двоичная запись числа N.
2) Из записи удаляются все нули.
3) Полученное число переводится в десятичную запись и выводится на экран.
Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 10 до 2500?

ЕГЭ_информатика ЕГЭ-05. Анализ простых алгоритмов

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

КУКАРЕКУ#33259

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Е, И, К, Р, У. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 1111, Б – 00, Р – 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КУКАРЕКУ?

ЕГЭ_информатика ЕГЭ-04. Кодирование и декодирование информации

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

КАМЧАТКА#33258

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, К, М, Т, Ч, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Т – 00, Б – 01, Я – 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КАМЧАТКА?

ЕГЭ_информатика ЕГЭ-04. Кодирование и декодирование информации

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

Кот Гусь и случайная матрица#33256

Кот Гусь подготовил для Ника Фьюри прямоугольную таблицу a размера \(n \cdot m\), содержащую числа от 0 до p−1. Ник Фьюри сразу понял, что каждое число в этой таблице выбрано случайно равновероятно от 0 до p−1, независимо от остальных.

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

Формально, вам необходимо найти такие \(1 <= i_1 <= i_2 <= n\), \(1 <= j_1 <= j_2 <= m\), что сумма a_x,y по всем \(i_1 <= x <= i_2\), \(j_1 <= y <= j_2\) делится на p, и среди таких имеет максимальную сумму.

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

В первой строке расположено три целых числа n, m, p (\(1 <= n·m, p <= 1 000 000\)) — размерности матрицы и число, на которое должна делится сумма подматрицы.

В следующих n строках расположено по m целых чисел, j-е число в i-й строке равно a_i,j (\(0 <= a_{i,j} <= p ? 1\)).

Гарантируется, что каждое число в a выбрано независимо случайно равновероятно от 0 до p−1.

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

Выведите одно целое число — максимальную сумму прямоугольной подматрицы, в которой сумма делится на p. Если таких нет, выведите 0.

Примеры

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

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

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

Средний балл по предметам - 2#33237

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

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

В первой строке задается количество учащихся n (\(0 < n <=100\)). Далее идет n строк, каждая из которых содержит фамилию, имя и три числа (оценки по трем предметам: математике, физике, информатике). Данные в строке разделены одним пробелом. Оценки принимают значение от 1 до 5.

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

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

Примеры

№	Входные данные	Выходные данные
1	2 Markov Valeriy 4 5 2 Kozlov Georgiy 5 1 2	4.5 3 2

Строки Структуры

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

Элементы, которые больше соседних#33236

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

Входные данные
Сначала задано число N — количество элементов в массиве (1<=N<=100). Далее через пробел записаны N чисел — элементы массива. Массив состоит из целых чисел.

Выходные данные
Необходимо вывести количество элементов массива, у которых два соседа и которые при этом строго больше обоих своих соседей.

Примеры

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

Алгоритмы обработки Одномерные массивы

✓ 4 539✗ 5 004200лёгкаяВойти и решать

Пара соседних элементов с одинаковыми знаками#33235

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

Входные данные
Сначала задано число N — количество элементов в массиве (1<=N<=10000). Далее через пробел записаны N чисел — элементы массива. Массив состоит из ненулевых целых чисел, каждое число по модулю не больше 100.

Выходные данные
Необходимо вывести слово YES, если существует пара соседних элементов с одинаковыми знаками. В противном случае следует вывести слово NO.

Примеры

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

Алгоритмы обработки Одномерные массивы

✓ 4 793✗ 9 381200лёгкаяВойти и решать

Количество элементов, больших предыдущего#33234

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

Входные данные
Сначала задано число N — количество элементов в массиве (1<=N<=10000). Далее через пробел записаны N чисел — элементы массива. Массив состоит из целых чисел.

Выходные данные
Необходимо вывести единственное число - количество элементов массива, больших предыдущего.

Примеры

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

Алгоритмы обработки Одномерные массивы

✓ 5 232✗ 9 100200лёгкаяВойти и решать

Наибольшая возрастающая подпоследовательность за O(n*log(n))#33231

Числовая последовательность задана рекуррентной формулой: a_i+1=(k * a_i+ b) mod m. Найдите длину её наибольшей возрастающей подпоследовательности.
mod - операция вычисления остатка от деления

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

Программа получает на вход пять целых чисел: длину последовательности n (1≤n≤10⁵), начальный элемент последовательности a₁, параметры k, b, m для вычисления последующих членов последовательности (1≤m≤10⁴, 0≤k<m, 0≤b<m, 0≤a1<m).

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

Требуется вывести длину наибольшей возрастающей подпоследовательности данной последовательности.

Примеры

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

Динамическое программирование Динамическое программирование: последовательности Динамическое программирование: последовательности

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

Школа#33230

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

Считается, что школа имеет надежное электроснабжение, если она напрямую связана с источником “Майбуття”, либо с одной из тех школ, которые имеют надежное электроснабжение.

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

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

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

В первой строке входного файла находятся два натуральных числа, разделенных пробелом: N (3 <= N <= 100), количество школ в городе, и M – количество возможных соединений между ними. В каждой из последующих M строк находятся по три числа: A_i, B_i, C_i, разделенных пробелами, где C_i - стоимость прокладки линии электроснабжения (1 <= C_i <= 300) от школы A_i до школы B_i (i=1,2,…,N).

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

В единственной строке выходного файла должны содержаться два натуральных числа S₁ и S₂, разделенных пробелом – две наименьшие стоимости схем (S₁ <= S₂). S₁=S₂ тогда и только тогда, когда существует несколько схем надежного электроснабжения наименьшей стоимости.

Гарантируется, что для входных данных существует две различные схемы надёжного электроснабжения.

Примеры

№	Входные данные	Выходные данные
1	5 8 1 3 75 3 4 51 2 4 19 3 2 95 2 5 42 5 4 31 1 2 9 3 5 66	110 121

Алгоритмы на графах Минимальный каркас

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

Сортировка по цифрам числа 2#33207

Дано N трехзначных чисел (1<=N<=1000). Необходимо вывести их в порядке возрастания.

Нельзя использовать встроенную сортировку

Пример
Входные данные

639 265 915 993 436 202 573 906 490

Выходные данные
202 265 436 490 573 639 906 915 993

Квадратичные сортировки Одномерные массивы

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

Сортировка по цифрам числа 1#33206

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

Формат входных данных
В первой строке записано натуральное число N (1<=N<=1000). Вторая строка содержит n двузначных положительных чисел nums_i (1 ≤ i ≤ n, 10 ≤ nums_i ≤ 99).

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

Квадратичные сортировки Одномерные массивы

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