Информатика

15 732 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Конечный ряд чисел - 3#27045
Дано вещественное число X (X<10). Вычислить



Входные данные: в первой строке вводится единственное число Х

Выходные данные: Выведите сумму данного ряда
(В проверяющей программе установлена точность 3 знака после запятой)
Цикл for
✓ 134✗ 593600лёгкаяВойти и решать
Линейная классификация#27044

В машинном обучении часто возникает задача линейной классификации объектов, когда классы объектов разделяются между собой линейной поверхностью. Например, у нас есть информация о количестве дней с момента регистрации аккаунта в социальной сети и количество отправленных сообщений за последний
день, а также информация о том, является ли этот аккаунт спам-ботом. Возраст аккаунта мы можем взять за X координату точки, а количество сообщений  за Y
коордианату. Задача классификации состоит в том, чтобы провести какую-либо прямую так, чтобы объекты одного типа находились по одну сторону этой прямой, а объекты другого типа  по другую.
 
При наличии такой прямой мы сможем пронозировать тип даже незнакомого объекта по известному возрасту аккаунта и количеству отправленных сообщений в зависимости от того, с какой стороны от прямой оказался объект. Естественно, в реальных данных могут быть ошибки измерений или необычные объекты и провести такую прямую не всегда возможно, потому что, например, объект первого типа может случйно попасть в скопление объектов второго типа и отделить его прямой невозможно.
 
Вам необходимо по информации о параметрах и типе объектов определить, существует ли прямая, которая однозначно разделеят классы объектов. Прямая не должна проходить ни через один объект.
 
Формат входных данных
В этой задаче входной файл содержит несколько тестовых блоков.
В первой строке задано число T  количество тестовых блоков (1 <= T <= 100).
Каждый тестовый блок состоит из числа N  количество описанных объектов (1 <= N <= 2000).
В следующих N строках содержится описания объектов, состоящие из трех целых чисел X, Y , Type (0 <= X, Y <= 107 , 0 <= Type <= 1).

Формат выходных данных
Выведите T слов "YES" или "NO" по одному в строке для каждого из тестовых блоков. "YES" необходимо выводить если разделение на классы возможно, "NO"  если невозможно.

Система оценки
Решения, верно работающие при T <= 10, N <= 100, будут набирать не менее половины баллов.

Ввод Вывод
2
6
1 1 1
1 2 1
1 3 0
2 1 1
2 2 0
3 1 0
6
1 3 0
2 2 0
1 2 1
3 1 1
2 1 1
1 1 0		 YES
NO

Вычислительная геометрия
✓ 2✗ 241 200средняяВойти и решать
Время полета#27040
При  полутах  на  самолетах  в  качестве  времени  вылета  и  прилета  используется  местное  время аэропортов вылета и прилета.
Часовые пояса характеризуются разницей во времени с меридианом, на котором расположена Гринвичская обсерватория. Для каждого часового пояса вводится отклонение от UTC (Всемирного координированного времени).
Например, Москва расположена в часовом поясе UTC+3, а Новосибирск в часовом поясе UTC+7.  Если  вылететь  из  Москвы  рейсом  в  11:15  и  временем  полјта  ровно  в  4  часа,  то  прилет будет в Новосибирск будет в 19:15 (4 часа полёта и 4 часа разницы во времени).
Например, Москва расположена в часовом поясе UTC+3, а Новосибирск  в часовом поясе UTC+7. Если вылететь из Москвы рейсом в 11:15 и временем полјта ровно в 4 часа, то прилјт будет в Новосибирск будет в 19:15 (4 часа полёта и 4 часа разницы во времени).
Часовые пояса могут изменяться от UTC-11 (Американское Самоа) до UTC+14 (острова Лайн, Кирибати).
По заданному времени вылета и времени полёта, а также по часовым поясам аэропортов вылета и прилёта, вам необходимо определить местное время прилёта и количество дней, прошедших в
пути.

Формат входных данных
В первой строке записаны целые числа HD , MD (0 <= HD <=  23, 0 <= MD <= 59)  время вылета.
Во второй строке записаны целые числа HF , MF (0 <= HF <= 109, 0 <= MF <= 59)  время полёта.
В третьей строке записаны целые числа D, A (-11 6 D, A <= 14)  часовые пояса аэропорта вылета и прилёта.
 
Формат выходных данных
Выведите три числа HA;MA; Days  время прилёта в часах и минутах, а также разницу в датах между датой вылета и датой прилёта.

Система оценки
Решения, верно работающие для рейсов, дата вылета и прилјта которых не отличаются, будут набирать не менее половины баллов.
Ввод Вывод
11 15
4 0
3 7
 19 15 0
12 0
1 0
-10 13
 12 0 1
 
Замечание
Первый тест соответствуте разобранному в условии примеру с Москвой и Новосибирском.
Второй тест соответствует, например, часовому перелету из Американского Самоа на Самоа.
Самолет вылетает в 12:00, летит в течение часа и приземляется в 12:00 местного времени. Т.к. он пересёк линию перемены даты, то на Самоа уже наступил следующий день.
В реальности существуют часовые пояса, которые отличаются от UTC на нецелое число часов, однако в задаче они не рассматриваются.
Вывод формулы
✓ 28✗ 114800средняяВойти и решать
Не равные максимальному#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лёгкаяВойти и решать
Обход по графу. Построение дерева решений#27035
Разработан шифр, при использовании которого каждой цифре ставится в
соответствие определенная буквенная последовательность как приведено в таблице.
1 2 3 4 5 6 7
AB CB CBA ABC BC BBC CCB
С клавиатуры дана буквенная последовательность, содержащая символы только из шифра.
 
Сколько существует вариантов расшифровки приведенной буквенной последовательности, если каждая цифра может встречаться в результате расшифровки любое количество раз. В ответе не нужно приводить все варианты получившихся последовательностей цифр.
Напишите целое число, соответствующее количеству вариантов расшифровки.
Ввод Вывод
ABCCBABBCCBABC 6

Динамическое программирование: один параметр
✓ 15✗ 8900средняяВойти и решать
Рекурсивный 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средняяВойти и решать
Алгоритмизация и программирование#27033
Дан фрагмент программы: 

 

Операции MOD, mod и функция ост_дел вычисляют остаток от деления первого аргумента на второй. Операции \, div и функция цел_дел осуществляют целочисленное деление. Какое минимальное значение целочисленной переменной X должно было быть перед началом выполнения этого фрагмента, если после его выполнения получилось значение R=A?, где А - вводится с клавиатуры. 
В ответе укажите целое число. 
Задача на реализацию
✓ 16✗ 34900средняяВойти и решать
Дилемма Кубратова#27027
Маленькому Егору в школе задали простую задачу: вывести абсолютное значение числа. Посмотрим, сможет ли он справится с этим без использования строк (даже в выводе).
 
Формат входных данных:
В единственной строке выходных данных содержится целое число M (-2^63 <= M < 2^63)
 
Формат выходных данных:
Выведите число, равное модулю числа M.
 
Пример:
Ввод Вывод
5 5
-7 7
 
 
P.S. Задача была проверена неоднократно. Все тесты верные. Ошибок быть не может.
P.P.S Все имена вымышлены, все совпадения с реальными людьми случайны.

(c) Ярослав Свиридов и Владимир Линд
Вывод формулы
✓ 11✗ 27700средняяВойти и решать
Матвей и замок#27025
Всемирно известному взломщику Матвею поступил заказ на инновационный сейф, выпущенный компанией "British Scientists, Inc". Этот сейф почти целиком сделан из адамантита, не поддающемуся ни одной из дрелей Матвея. Поэтому его единственным уязвимым местом является патентованный кодовый замок. К счастью, Матвей похитил чертежи сейфа ещё во время его разработки, поэтому точно знает принцип работы замка.

Код вводится с помощью клавиатуры с числами от нуля до девяти. Как только введено необходимое количество цифр, код проверяется по следующему алгоритму. К нулю прибавляется первая введённая цифра, затем отнимается вторая, потом эта разность умножается на третью, и наконец, результат нацело делится на четвёртую. Потом этот алгоритм повторяется для следующих четырёх цифр, и так, пока они не кончатся. Если количество цифр не делится на четыре, то лишние действия просто отбрасываются.  Если при выполнении алгоритма встречается деление на ноль, то он тут же аварийно завершает работу, блокируя сейф. Если в результате получилось число X - секретная константа, которую Матвей тоже знает - замок открывается. 
Матвей внимательно изучил клавиатуру и понял, что по отпечаткам пальцев на кнопкам он может определить, какие цифры используются в коде, и сколько раз. Тут ему стало интересно - а сколько всего комбинаций, подходящих под эти данные, открывают замок? Комбинации считаются различными, если в них отличается порядок следования цифр. 
Но увы, с математикой у Матвея не очень, поэтому, без труда выполнив заказ, он задал этот вопрос всемирно известному хакеру - Вам. Помогите Матвею. 
 
Входные данные
В первой строке на вход подаются два числа N (1 <= n <= 8) и Х (1 <= X <= 10^9) - количество цифр в коде и секретная константа. Во второй находится n цифр, разделённых пробелами. Разумеется, цифры могут повторяться. 
 
Выходные данные
Вывести необходимо единственное число - ответ на вопрос Матвея.
 
Ввод Вывод
4 0
2 2 3 6
 4
2 1
1 1		 0

 
Перестановки
✓ 6✗ 28900средняяВойти и решать
Вывод паролей#27024
Однажды, на уроке информатики Леше Васильеву дали придумать специальную задачу с перестановками для Дамира.  Леше очень понравилась эта затея, поэтому он взял ноутбук с полки, включил и заметил, что Антон Витальевич сменил пароли. Леше известно, что пароль содержит в себе все символы лексикографически максимальной подстроки в строке S, однако у него не так много времени на перебор, задачи необходимо сдать через 40 минут!
Помогите Леше и напишите программу, которая способна вывести все варианты паролей для строки S.
Пароли выводятся в алфавитном порядке.
Подстрокой называется некоторая непустая подпоследовательность подряд идущих символов строки. Лексикографически максимальная подстрока это подстрока, стоящая на последнем месте в отсортированном по алфавиту списке всех подстрок исходной строки.
 

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

Программа получает на вход строку S. Длина S не более 15 символов. Строка записана строчными английскими буквами.
 

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

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


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

Линейные алгоритмы
✓ 53✗ 125700средняяВойти и решать
Алгоритм#27013
Реализуйте на одном из языков программирования алгоритм, представленный на схеме.
В первой строке ввода содержится два целых числа, разделенных пробелом - S (0 ≤ S ≤ 20000 ≤ S ≤ 2000) и P (0 ≤ P ≤ 10000000 ≤ P ≤ 1000000).
Вывести два целых числа I и J через пробел.
 
Ввод Вывод
22 120 10 12
Простые задачи на перебор
✓ 34✗ 70800средняяВойти и решать
Сумма ряда - 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средняяВойти и решать
Сумма ряда - 7#27009
Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):
\(a_n = {2^n \cdot n! \over{n^n}}\)
 
Выведите на экран сумму такого ряда.
Циклы
✓ 23✗ 186800средняяВойти и решать
Сумма ряда - 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средняяВойти и решать
Сумма ряда - 4#27006
Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):
\(a_n = {1 \over{(3 \cdot n - 2)\cdot(3\cdot n+1)}}\)
 
Выведите на экран сумму такого ряда.
Циклы
✓ 25✗ 85800средняяВойти и решать
Сумма ряда - 3#27005
Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):
\(a_n = {{2\cdot n-1} \over{2^n}}\)
 
Выведите на экран сумму такого ряда.
Циклы
✓ 50✗ 191600лёгкаяВойти и решать
Поделиться
Класснуть