Информатика

15 724 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Принадлежность точки лучу#27075
Входные данные
Шесть чисел – координаты точки и координаты начала и конца вектора.
 
Выходные данные
Одна строка “YES”, если точка принадлежит лучу, определяемому вектором, и “NO” в противном случае.

 

Примеры
№ Входные данные Выходные данные
1 4 0 4 2 4 5 NO
Вычислительная геометрия
✓ 560✗ 1 512300лёгкаяВойти и решать
МАРШРУТЫ#27073
В государстве Чудаков N городов ( 2 <=N <= 16 ), обозначаемых заглавными латинскими буквами, начиная с A, по порядку. Между некоторыми из них проложены дороги, которые могут быть как односторонними, так и двусторонними, причем не обязательно, что из каждого города можно проехать в любой другой.

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

Маршрут обозначается N буквами, начиная с города, из которого происходит выезд. Например, BCDCE – допустимый маршрут для государства из 5 городов ссоответствующими дорогами: выехать из B, проехать в C, затем в D, вернуться в C, проехать в E и вернуться в изначальный город B (последний пункт маршрута, совпадающий с первым, в маршруте не указывается).

Маршрут автобуса меняется каждый день так, что список маршрутов по дням расположен в словарном порядке и содержит все возможные маршруты. Когда список кончается, его обход начинается сначала. В первый день введения маршрута 'Ч' автобус шёл по первому по порядку маршруту. Выведите его маршрут на день K работы маршрута. Пример: В государстве четыре города: A, B, C, D. Наличие дорог между ними задано матрицей, где элемент равен 1, если из города, соответствующего строке, в город, соответствующий столбцу, есть дорога, и 0 – иначе (на главной диагонали нули – дорог, ведущих назад в тот же город, не бывает).

 
откуда/куда A B C D
A 0 0 1 1
B 1 0 1 1
C 0 1 0 0
D 0 1 1 0


Полное расписание маршрутов в таком государстве выглядит так:
ADCB
BADC
BCBC
BCBD
BDBC
BDBD
CBAD
CBCB
CBDB
DBCB
DBDB
DCBA

Таким образом, например, маршрут на день 30 – это BDBD.

Формат входных данных
В первой строке указывается количество городов N ( 2<= N <= 16 ). Далее следует N строк по N элементов (цифр), разделенных пробелом, содержащих матрицу, задающую дороги между городами. Далее следует строка содержащая целое число D – номер дня, маршрут которого требуется определить ( 1<= D <= 264 ).

Формат выходных данных
В единственной строке указывается маршрут, т.е. порядок посещения городов, например BDBD (см. предыдущий пример).
 
Ввод Вывод
3
0 1 1
1 0 1
1 1 0
4		 BCA

 
Комбинаторика
✓ 0✗ 41 200средняяВойти и решать
КОЛОНИЗАЦИЯ МАРСА#27072
Ученым удалось отправить на планету Марс мини-фабрику, которая может за одни сутки произвести мини-фабрику или дрона для сбора воды (мини-фабрика или дрон для сбора воды могут начать работу только со следующих суток). Дрон собирает одну единицу воды за одни сутки. Определите, за какое минимальное количество суток удастся собрать не менее N единиц воды.

Формат входных данных
Задается одно число N ( 1<= N <= 109 ) – необходимое количество воды.

Формат выходных данных
Одно целое число M – минимально необходимое количество суток.
 
Ввод Вывод
2 3


Замечание
Одна из правильных последовательностей действий выглядит так:
? В первые сутки мини-фабрика производит дрона для сбора воды;
? За вторые сутки мини-фабрика производит еще одного дрона, а первый дрон собирает одну единицу воды;
? За третьи сутки мини-фабрика может произвести еще одного дрона или мини- фабрику, при этом первый дрон собирает еще одну единицу воды (итого он собрал 2 единицы воды), а второй дрон собирает единицу воды. Таким образом, накоплено 3 единицы воды за трое суток.

Другая последовательность действий состоит в том, чтобы за первые сутки построить еще одну мини-фабрику, а за вторые сутки произвести двух дронов, которые на третьи сутки соберут 2 единицы воды.
Задача на реализацию
✓ 11✗ 151900средняяВойти и решать
ПИРАМИДА#27071
Для строительства двухмерной пирамиды используются прямоугольные блоки, каждый из которых характеризуется шириной и высотой. Можно поставить один блок на другой, только если ширина верхнего блока строго меньше ширины нижнего. Самым нижним в пирамиде может быть блок любой ширины.

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

Формат входных данных
В первой строке входных данных задается число N – количество блоков ( 1 <= N <= 100000 ). В следующих N строках задаются пары целых чисел wi и hi ( 1<= wi , hi <= 109), разделенные пробелом – ширина и высота блока, соответственно.

Формат выходных данных
Целое число – максимальная высота пирамиды.
 
Ввод Вывод
3
3 1
2 2
3 3		 5

Замечание.
В приведенном примере пирамида будет состоять из двух блоков: нижним будет блок с номером 3, а верхним – блок с номером 2. Блок с номером 1 нельзя использовать для строительства пирамиды, т.к. его ширина совпадает с шириной нижнего блока.
Использование сортировки
✓ 35✗ 112700средняяВойти и решать
Кузнечик собирает монеты#27069
Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего.
 
На каждом столбике Кузнечик может получить или потерять несколько золотых монет (для каждого столбика это число известно). Определите, как нужно прыгать Кузнечику, чтобы собрать наибольшее количество золотых монет. Учитывайте, что Кузнечик не может прыгать назад.
 
Входные данные
- в первой строке вводятся два натуральных числа: N и K (\(2 <= N ,\ K <= 10000\)), разделённые пробелом;
- во второй строке записаны через пробел N-2 целых числа – количество монет, которое Кузнечик получает на каждом столбике, от 2-го до N-1-го. Если это число отрицательное, Кузнечик теряет монеты.
Гарантируется, что все числа по модулю не превосходят 10000.
 
Выходные данные
- в первой строке программа должна вывести наибольшее количество монет, которое может собрать Кузнечик;
- во второй строке выводится число прыжков Кузнечика;
- в третьей строке – номера всех столбиков, которые посетил Кузнечик (через пробел в порядке возрастания).
 
Если правильных ответов несколько, выведите любой из них.
Динамическое программирование: один параметр
✓ 404✗ 1 223700средняяВойти и решать
Capybara. Канатная дорога#27068
Побывав недавно в лесу, Вася решил построить на деревьях канатную дорогу. Он хочет, чтобы дорога была как можно более длинной, но он плохо помнит высоты деревьев в лесу. К счастью, он уверен, что правильно помнит высоты всех деревьев, кроме, возможно, одного из них.

Известно, что лес состоит из n деревьев, стоящих в ряд и пронумерованных слева направо числами от 1 до n. Высота i-го дерева, по воспоминаниям Васи, равна hi. Канатная дорога длины k должна опираться на k (1 <= k <= n) деревьев i1, i2, . . . , ik (i1 < i2 < . . . < ik), таких что их высота возрастает, то есть, hi1 < hi2 < . . . < hik.
Петя тоже был в лесу, и у него есть q предположений о том, где именно ошибается Вася. Его i-е предположение задаётся числами ai и bi , означающими, что, по мнению Пети, высота дерева
с номером ai на самом деле равна bi . Обратите внимание, Петины предположения независимы между собой.

Ваша задача состоит в том, чтобы для каждого предположения Пети найти максимальную длину канатной дороги, которую можно построить с опорой на эти деревья.
Отметим, что в рамках данной задачи длиной дороги Вася считает количество опорных деревьев в ней.
 
Формат входных данных
Первая строка входных данных содержит два числа n и m (1 <= n, m <= 400 000) — количество деревьев в лесу и количество предположений Пети соответственно.
В следующей строке содержатся n целых чисел hi (1 <= hi <= 109 ) — высоты деревьев по предположению Васи.

Каждая из следующих m строк содержит по два целых числа ai и bi (1 <= ai <= n, 1 <= bi <= 109 ).

Формат выходных данных
Для каждого предположения Пети выведите в отдельной строке одно число — максимальную длину канатной дороги.

Ввод Вывод
4 4
1 2 3 4
1 1
1 4
4 3
4 5		 4
3
3
4
4 2
1 3 2 6
3 5
2 4		 4
3
Замечание
Рассмотрим первый пример. Первое Петино предположение совпадает с предположением Васи.
Согласно его второму предположению, высоты деревьев были (4, 2, 3, 4), третьему (1, 2, 3, 3), а по четвёртому предположению — (1, 2, 3, 5).
Динамическое программированиедп
✓ 1✗ 411 300средняяВойти и решать
Возрастающая подпоследовательность#27052
Даны N целых чисел X1, X2, ..., XN. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.
 
Входные данные
В первой строке находится число N. В следующей строке - N чисел через пробел. 1 <= N <= 10 000, 1 <= Xi <= 60 000.
 
Выходные данные
В первой строке выводится количество невычеркнутых чисел, во второй - сами невычеркнутые числа через пробел в исходном порядке. Если вариантов несколько, вывести любой.
 
 
Примеры
№ Входные данные Выходные данные
1
5
1 3 5 2 4
3
1 3 4
Динамическое программирование: последовательности
✓ 221✗ 1 024700средняяВойти и решать
Числовая последовательность - 4#27049
Дано вещественное число х. Вычислить
\(s = {{(x-1)\cdot(x-3)\cdot(x-7)\cdot...\cdot(x-63)}\over{(x-2)\cdot(x-4)\cdot(x-8)\cdot...\cdot(x-64)}}\)

 
Входные данные
Вводится вещественное число х (-50 <= х <= 50). Гарантируется, что для заданного х решение существует.

Выходные данные
Выведите значение S.
Циклы
✓ 75✗ 460700средняяВойти и решать
Числовая последовательность - 3#27048
Дано натуральное число N, вещественное число А. Вычислить
\(S = {{1 \over A} + {1 \over {A^2}} + {1 \over A^4} +... + {1 \over A^{2\cdot N - 2}} }\)

 
Входные данные
В первой строке вводится натуральное число N (0 < N <= 10). Во второй строке вводится вещественное число А (-5 <= А<= 5, А!=0).


Выходные данные
Выведите значение S.
 
Циклы
✓ 45✗ 418700средняяВойти и решать
Числовая последовательность - 2#27047
Дано натуральное число N, вещественное число А. Вычислить
\(P = A \cdot (A  -  N) \cdot (A - 2 \cdot N) \cdot...\cdot (A - N^2)\)
 
Входные данные
В первой строке вводится натуральное число N (0<N<=10). Во второй строке вводится вещественное число А (-10<=А<=10).


Выходные данные
Вывести число P.
Циклы
✓ 44✗ 330600лёгкаяВойти и решать
Числовая последовательность - 1#27046
Дано натуральное число N, вещественное число А. Вычислить
\(P = A \cdot (A  +  1) \cdot...\cdot (A + N - 1)\)
 
Входные данные
В первой строке вводится натуральное число N (0<N<=10). Во второй строке вводится вещественное число А (-100<=А<=100).

Выходные данные
Вывести число P.

 
Циклы
✓ 84✗ 462500лёгкаяВойти и решать
Конечный ряд чисел - 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средняяВойти и решать
Поделиться
Класснуть