Информатика

15 724 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Двоичный автомат - 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\), что сумма ax,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-й строке равно ai,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 523✗ 4 998200лёгкаяВойти и решать
Пара соседних элементов с одинаковыми знаками#33235

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


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

Выходные данные
Необходимо вывести слово YES, если существует пара соседних элементов с одинаковыми знаками. В противном случае следует вывести слово NO.
 
Примеры
№ Входные данные Выходные данные
1 5
1 -3 4 -2 1		 NO
 
Алгоритмы обработкиОдномерные массивы
✓ 4 773✗ 9 368200лёгкаяВойти и решать
Количество элементов, больших предыдущего#33234

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

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

Выходные данные
Необходимо вывести единственное число - количество элементов массива, больших предыдущего.
 
Примеры
№ Входные данные Выходные данные
1 5
1 2 3 4 5		 4
 
Алгоритмы обработкиОдномерные массивы
✓ 5 199✗ 9 050200лёгкаяВойти и решать
Наибольшая возрастающая подпоследовательность за O(n*log(n))#33231
Числовая последовательность задана рекуррентной формулой: ai+1=(k * ai + b) mod m. Найдите длину её наибольшей возрастающей подпоследовательности. 
mod - операция вычисления остатка от деления 
 
Входные данные
Программа получает на вход пять целых чисел: длину последовательности n (1≤n≤105), начальный элемент последовательности a1, параметры k, b, m для вычисления последующих членов последовательности (1≤m≤104, 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 строк находятся по три числа: Ai, Bi, Ci, разделенных пробелами, где Ci - стоимость прокладки линии электроснабжения (1 <= Ci <= 300) от школы Ai до школы Bi (i=1,2,…,N).
 
Выходные данные
В единственной строке выходного файла должны содержаться два натуральных числа S1 и S2, разделенных пробелом – две наименьшие стоимости схем (S1 <= S2). S1=S2 тогда и только тогда, когда существует несколько схем надежного электроснабжения наименьшей стоимости.
 
Гарантируется, что для входных данных существует две различные схемы надёжного электроснабжения.
 
Примеры
№ Входные данные Выходные данные
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). Необходимо вывести их в порядке возрастания.

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

Пример
Входные данные
9
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 двузначных положительных чисел numsi (1 ≤ i ≤ n, 10 ≤ numsi ≤ 99).

Формат выходных данных
Выведите ответ на задачу.
Квадратичные сортировкиОдномерные массивы
✓ 64✗ 88600лёгкаяВойти и решать
Пятый самый легкий#33205
Формат входных данных
В первой строке записано натуральное число n (n < 100). Вторая строка содержит n положительных целых чисел mi - вес i-го предмета (1 ≤ i ≤ n, 1 ≤ ai ≤ 105). 

Формат выходных данных
Напечатайте массу предмета, являющегося "пятым самым легким предметом".
Квадратичные сортировкиОдномерные массивы
✓ 167✗ 324400лёгкаяВойти и решать
Вставка элемента в вектор#33204
Дан массив из N положительных элементов, больших 1 (2<=N<=100). Вставить значение a перед всеми элементами, кратными а
 
Формат входных данных
На входе подаются в первой строке N - число элементов массива
Вторая строка содержит число a 
Третья строка содержит N чисел - значения элементов массива
Все числа положительные не больше 100.
 
Формат выходных данных
Выведите результирующий массив в строку
 
 
Алгоритмы обработкиОдномерные массивы
✓ 973✗ 1 970300лёгкаяВойти и решать
Средние в шеренге#33203
Формат входных данных
В первой строке записано натуральное число n (n < 100, n - четное). Вторая строка содержит n положительных целых чисел mi - рост i-го учащегося (1 ≤ i ≤ n, 1 ≤ ai ≤ 105). 

Формат выходных данных
Напечатайте рост тех двоих людей, которые бы оказались в середине шеренги в случае построения ее по ранжиру (по убыванию роста).
Квадратичные сортировкиОдномерные массивы
✓ 306✗ 392400лёгкаяВойти и решать
Использование сортировки 2#33202
В каждом из двух классов учатся по n человек (10 <= n <= 30). Известны средний балл каждого ученика каждого класса, подсчитанные по ряду предметов (все значения целые). Определить, в каком классе у "третьего из самых успевающих учеников" средняя оценка больше. Вывести цифру "1" - для первого класса, "2" - для второго. Если оценки равны, вывести эту оценку.


Формат входных данных
В первой строке записано натуральное число n (n < 100) - количество учеников в каждом классе . Вторая строка содержит n положительных целых чисел class1i - средний балл i-го ученика первого класса (1 ≤ i ≤ n, 1 ≤ class1i ≤ 105). Третья строка содержит n положительных целых чисел class2i - средний балл i-го ученика первого класса (1 ≤ i ≤ n, 1 ≤ class2i ≤ 105).

Формат выходных данных
Выведите ответ на задачу.
Квадратичные сортировкиОдномерные массивы
✓ 51✗ 132700средняяВойти и решать
Динамика - 09#33191
Исполнитель Громозека выполяет некоторые действия с числом на экране. Громозека знает всего три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Умножить на 4
Сколько существует программ, для которых при исходном числе 1 результатом является число 50 и при этом траектория вычислений содержит число 15 и не содержит число 30?
ЕГЭ_информатикаЕГЭ-13. Динамическое программирование
1 000средняяВойти и решать
Динамика - 08#33190
Исполнитель Громозека выполяет некоторые действия с числом на экране. Громозека знает всего три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Умножить на 3
Сколько существует программ, для которых при исходном числе 5 результатом является число 52 и при этом траектория вычислений содержит число 15 и не содержит число 29?
ЕГЭ_информатикаЕГЭ-13. Динамическое программирование
900средняяВойти и решать
Двоичный автомат - 3#33165
Автомат обрабатывает целое число N (0 ≤ N ≤ 255) по следующему алгоритму:
1) Строится восьмибитная двоичная запись числа N.
2) Все цифры двоичной записи заменяются на противоположные (0 на 1, 1 на 0).
3) Полученное число переводится в десятичную запись.
4) Из нового числа вычитается исходное, полученная разность выводится на экран.
Какое число нужно ввести в автомат, чтобы в результате получилось 99?
ЕГЭ_информатикаЕГЭ-05. Анализ простых алгоритмов
1 000средняяВойти и решать
Двоичный автомат - 4#33164
Автомат обрабатывает целое число N (0 ≤ N ≤ 255) по следующему алгоритму:
1) Строится восьмибитная двоичная запись числа N.
2) Все цифры двоичной записи заменяются на противоположные (0 на 1, 1 на 0).
3) Полученное число переводится в десятичную запись.
4) Из нового числа вычитается исходное, полученная разность выводится на экран.
Какое число нужно ввести в автомат, чтобы в результате получилось 113?
ЕГЭ_информатикаЕГЭ-05. Анализ простых алгоритмов
1 000средняяВойти и решать
Поделиться
Класснуть