Информатика

2 621 задачавместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Не равные максимальному#27037

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

Напишите эффективную по времени и по памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения переменных программы, не превышает одного килобайта и не увеличивается с ростом N.
 
Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 <= 𝑁 <=100 000\)). В каждой из последующих 𝑁 строк записано одно целое число, не превышающее по модулю 1000.
 
Выходные данные
Выведите одно число - ответ на задачу
 

 

Примеры
№ Входные данные Выходные данные
1
5
7
-5
9
8
9
 3

В приведённом наборе из 5 чисел имеются три элемента — 7, –5 и 8, значения которых не равны значению максимального элемента этого набора — 9.
ЕГЭ - вычислительные задачи
✓ 312✗ 178500лёгкаяВойти и решать
Рекурсивный DFS#27034
Дана матрица N (1 <= N <= 100) на M (1 <= M <= 100). В матрице имеются ‘.’ – пустые клетки и ‘#’ – клетки, которые нельзя посетить. Ходить можно только вверх, вниз, влево и вправо. Дано q запросов: номер строки и номер столбца, если эта клетка – ‘#’, то она станет ‘.’, иначе – ‘#’. Для каждого из q запросов определить, достижима ли из клетки (Sx; Sy) клетка (tx; ty). Вывести на каждой строчке “Yes”, если достижима, и “No” - иначе.
Гарантируется, что клетка (Sx; Sy) и клетка (tx; ty)не являются ‘#’ клеткой в каждом запросе.

Формат входных данных
На первой строчке вводятся числа Sx (1 <= Sx <= 100), Sy (1 <= Sy <= 100), tx (1 <= tx <= 100), ty (1 <= ty <= 100), N (1 <= N <= 100), M(1 <= M <= 100) и q (1 <= q <= 100). На следующих N строках дается матрица, где ‘.’ – пустая клетка и ‘#’ – клетка, которую нельзя посетить. На следующих q строках дан номер строки и номер столбца, которые надо изменить.

Формат выходных данных
Вывести на каждый из q запросов “Yes”, если из клетки (Sx; Sy) в клетку (tx; ty) можно попасть, “No” – иначе.
 
Пояснение
В тестовом примере после первого запроса матрица будет такой:
..#
##.
###
Из точки (1; 1) в (2; 3) нет прохода, следовательно, выводим “No”.

После второго запроса матрица будет такой:
..#
#..
###
Из точки (1; 1) в (2; 3)есть проход, следовательно, выводим “Yes”. Выделен путь, по которому мы сможем идти.
 
Обход в глубину
✓ 425✗ 565700средняяВойти и решать
Дилемма Кубратова#27027
Маленькому Егору в школе задали простую задачу: вывести абсолютное значение числа. Посмотрим, сможет ли он справится с этим без использования строк (даже в выводе).
 
Формат входных данных:
В единственной строке выходных данных содержится целое число M (-2^63 <= M < 2^63)
 
Формат выходных данных:
Выведите число, равное модулю числа M.
 
Пример:
Ввод Вывод
5 5
-7 7
 
 
P.S. Задача была проверена неоднократно. Все тесты верные. Ошибок быть не может.
P.P.S Все имена вымышлены, все совпадения с реальными людьми случайны.

(c) Ярослав Свиридов и Владимир Линд
Вывод формулы
✓ 11✗ 27700средняяВойти и решать
Алгоритм#27017
Реализуйте на одном из языков программирования алгоритм, представленный на схеме.
В первой строке ввода содержатся два целых числа N и K (1 ≤ N, K ≤ 10001).
Вывести одно целое число – сумму N и K после завершения работы алгоритма.


Ввод Вывод
30 15 19

Линейные алгоритмы
✓ 53✗ 125700средняяВойти и решать
Сумма ряда - 10#27012
Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):
\(a_n = {(2)^{n} \over{(n-1)!}}\)
 
Выведите на экран сумму такого ряда.
Циклы
✓ 58✗ 228700средняяВойти и решать
Сумма ряда - 9#27011
Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):
\(a_n = {{n!} \over{(2^n)!}}\)
 
Выведите на экран сумму такого ряда.
Циклы
✓ 31✗ 121700средняяВойти и решать
Сумма ряда - 8#27010
Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):
\(a_n = {n! \over{3 \cdot n^n}}\)
 
Выведите на экран сумму такого ряда.
Циклы
✓ 52✗ 245700средняяВойти и решать
Сумма ряда - 6#27008
Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):
\(a_n = {n! \over{n^n}}\)
 
Выведите на экран сумму такого ряда.
Циклы
✓ 37✗ 130700средняяВойти и решать
Сумма ряда - 5#27007
Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):
\(a_n = {{n!} \over{(2\cdot n)!}}\)
 
Выведите на экран сумму такого ряда.
Циклы
✓ 33✗ 159700средняяВойти и решать
Сумма ряда - 3#27005
Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):
\(a_n = {{2\cdot n-1} \over{2^n}}\)
 
Выведите на экран сумму такого ряда.
Циклы
✓ 50✗ 191600лёгкаяВойти и решать
Сумма ряда - 2#27004
Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):
\(a_n = {{1\over 2^n} + {1 \over 3^n}}\)
 
Выведите на экран сумму такого ряда.
Циклы
✓ 48✗ 159700средняяВойти и решать
Разбиение на пары#26982

Мария Ивановна написала на доске четыре числа: a, b, c и d. После чего предложила своему классу разбить эти числа на две пары так, чтобы сумма произведений чисел в парах была максимальна.

Например, если на доске написаны числа 5, 6, 7 и 8, то оптимально разбить их на пары (5, 6) и (7, 8), в этом случае искомая сумма равна 5 × 6 + 7 × 8 = 86.

Формат ввода

На вход подаются четыре целых числа: a, b, c и d. Все числа по модулю не превышают 1000.

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

Выведите искомую максимальную сумму.

Пример

Ввод Вывод 
5 6 7 8

86

Линейные алгоритмы
✓ 59✗ 65500лёгкаяВойти и решать
Максимальная сумма, не делящаяся на 4#25980

На вход программы поступает последовательность из N натуральных чисел. Нужно выбрать из них произвольное количество чисел так, чтобы их сумма была максимальной и не делилась на 4. 

В результате программа должна вывести количество выбранных чисел и их сумму. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Входные данные
На вход программе подаётся натуральное число N (\(N <= 1000\)), а затем N натуральных чисел, каждое из которых не превышает 10000. 
 
Выходные данные
Программа должна вывести два числа: сначала количество выбранных чисел, а затем их сумму. 
 

 

Примеры
№ Входные данные Выходные данные
1
3 
1
2
1
 2 3
ЕГЭ - вычислительные задачи
✓ 484✗ 907500лёгкаяВойти и решать
Задача#25974

Для чего производится описание массивов?

1) чтобы самому запомнить сколько ячеек в массиве
2) чтобы компьютер запомнил имя массива
3) чтобы компьютер зарезервировал память для хранения элементов массива
4) чтобы компьютер зарезервировал количество энергии для обработки массива
Одномерные массивы
300лёгкаяВойти и решать
По мотивам ЕГЭ 2017#25970

Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых \(1 <= i < j <= N\) и произведение элементов кратно 14.
Напишите эффективную по времени и по памяти программу для решения этой задачи. 


Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 < N <= 10000\)). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.


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

 

Примеры
№ Входные данные Выходные данные
1 5
14
7
7
2
19		 6
ЕГЭ - вычислительные задачи
✓ 483✗ 678500лёгкаяВойти и решать
3-ий минимум#25969
От цифровых датчиков в компьютер поступает информация о характеристиках физического процесса. Результатом каждого измерения является целое число.

Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет выводить третье по величине (считая от минимума) значение измерения. Если несколько измерений имеют одинаковые значения, то они учитываются как одно измерение. Если искомого значения не существует (например, когда все значения измерений равны), то нужно вывести символ "#". Следует учитывать, что количество измерений может быть очень велико.

На вход программе в первой строке подается общее количество N значений измерений.
В каждой из последующих N строк записано целое число. Гарантируется, что \(N>0\), то есть всегда имеется хотя бы одно измерение.
 

 

Примеры
№ Входные данные Выходные данные
1 5
100
10
100
10
100		 #

 

ЕГЭ - вычислительные задачи
✓ 271✗ 631600лёгкаяВойти и решать
Дипломы#25961
Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось n дипломов, причём, как оказалось, все они имели одинаковые размеры: w — в ширину и h — в высоту. Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером w на h. Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек. Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

Входные данные: на вход подаются три целых числа: w, h, n (\(1<=w,\ h,\ n <= 10^9\) ).
 
Выходные данные: необходимо вывести ответ на поставленную задачу.
 
Примеры
№ Входные данные Выходные данные
1 2 3 10 9
2 1 1 1 1
Бинарный поиск по ответу
✓ 926✗ 1 884500лёгкаяВойти и решать
Левый и правый двоичный поиск#25960
Дано два списка чисел, числа в первом списке упорядочены по неубыванию. Для каждого числа из второго списка определите номер первого и последнего появления этого числа в первом списке.
 
Формат входных данных
В первой строке входных данных записано два числа N и M (\(1<=N,\ M <=20000\)). Во второй строке записано N упорядоченных по неубыванию целых чисел — элементы первого списка. В третьей строке записаны M целых неотрицательных чисел - элементы второго списка.
Все числа в списках - целые 32-битные знаковые.
 
Формат входных данных
Программа должна вывести M строчек. Для каждого числа из второго списка нужно вывести номер его первого и последнего вхождения в первый список. Нумерация начинается с единицы. Если число не входит в первый список, нужно вывести одно число 0.
 
Бинарный поиск в массиве
✓ 849✗ 1 683600лёгкаяВойти и решать
Слажал - отжался#25917
Когда в очередной раз на уроке физкультуры дети не смогли сразу выстроиться по росту и это заняло 5 минут занятия, физрук придумал новое правило. Дети заходят все вместе и сразу встают в ряд. После этого могут меняться местами только два школьника, стоящих рядом. При этом они, конечно же, должны отжаться столько раз, какая у них оказалась разница в росте. Сколько раз в результате суммарно отожмутся школьники, прежде чем у них получится выстроиться по росту в порядке убывания?
 
Формат входных данных
В первой строке число содержится число N (2 <= N <= 1000)  количество детей в классе. В
следующей строке записана исходная расстановка школьников: N чисел через пробел, i-е число
обозначает рост i-го школьника ri (1 <= ri <= 109) в нанометрах.
 
Формат выходных данных
Одно число  суммарное количество отжиманий. Гарантируется, что школьники суммарно отожмутся не более 2 · 109 раз.

Ввод Вывод
3
1 2 3		 8

Замечание
В примере школьники с ростом 1 и 2 поменяются местами и каждый отожмјтся по разу, затем школьники 1 и 3 (каждый отжимается 2 раза, суммарно плюс 4 отжимания), и последними школьники 2 и 3 (плюс 2 отжимания).

Использование сортировкиреализация
✓ 194✗ 273400лёгкаяВойти и решать
Поделиться
Класснуть