Информатика

15 724 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
RAID#28422
При хранении данных одна из основных задач – соблюдение баланса между расходами на количество дисков и надёжностью записи. Одним из компромиссных по надёжности и стоимости хранения данных является RAID-3 – избыточный массив независимых дисков с выделенным диском для хранения блоков чётности. Наш RAID-3 состоит из пяти дисков, на четырёх из которых содержится информация, а на пятом – блоки контрольных битов чётности. При записи четырёх байтов (по байту на каждый из четырёх дисков) вычисляется контрольный байт четности, составленный из контрольных битов. Для каждого из восьми разрядов вычисляется сумма значений битов в этих разрядах во всех байтах данных, при этом значение контрольного бита выбирается так, чтобы сумма значений во всех разрядах (включая контрольный) была чётной. Например, у нас есть два основных диска и на них записывается байты 10010010 и 01110111. Тогда значение контрольного байта равно 11100101 – в каждом разряде сумма получается чётной.

Один из четырёх основных дисков в RAID-3 вышел из строя. Известны значения байтов в трёх оставшихся дисках и значение байта на контрольном диске. Какой байт был записан на сломавшемся диске? Все числа приведены в десятичной системе счисления.
 
– значения на первых трех дисках: 177, 177, 177, контрольный байт: 177;
– значения на первых трех дисках: 79, 79, 79, контрольный байт: 0;
– значения на первых трех дисках: 46, 56, 248, контрольный байт: 90;
– значения на первых трех дисках: 255, 0, 150, контрольный байт 96;
– значения на первых трех дисках: 137, 232, 23, контрольный байт 212.

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

Битовые операцииВывод формулы
✓ 0✗ 11 000средняяВойти и решать
Точки на прямой#28417
Маленький Петя очень любит точки. Недавно мама подарила ему n точек, лежащих на прямой OX. Пете стало интересно, сколькими способами он может выбрать три различные точки так, чтобы расстояние между двумя самыми удаленными из выбранных точек не превышало d.
Обратите внимание, что порядок точек внутри выбранной тройки значения не имеет.

Входные данные
Первая строка содержит два целых числа: n и d (1 ≤ n ≤ 105; 1 ≤ d ≤ 109). Следующая строка содержит n целых чисел x1, x2, ..., xn, по модулю не превосходящих 109 — x-координаты точек, подаренных Пете.
Гарантируется, что координаты точек во входных данных строго возрастают.

Выходные данные
Выведите единственное целое число — количество троек точек, в которых расстояние между двумя самыми удаленными точками не превосходит d.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
 
Ввод Вывод
4 3
1 2 3 4
 4
4 2
-3 -2 -1 0
 2
5 19
1 10 20 30 50
 1
 
В первом примере нам подходит любая тройка различных точек.
Во втором примере нам подходят всего 2 тройки: {-3, -2, -1} и {-2, -1, 0}.
В третьем примере нам подходит одна тройка: {1, 10, 20}.
 
"Два указателя"Комбинаторика
✓ 354✗ 711600лёгкаяВойти и решать
Таблица умножения#28405
Дано число N (0 < N < 100)Напишите программу, которая выводит на экран таблицу умножения на заданное число.

Входные данные
С клавиатуры задается одно число N.

Выходные данные 
Необходимо вывести таблицу умножения (см примеры). Для знака умножения используйте английскую букву x. Знаки равенства (=) и умножения (x) отделяется с двух сторон одним пробелом. Других пробелов нет.
 
Примеры
Входные данные 
7

Выходные данные 
7 х 1 = 7
7 х 2 = 14
7 х 3 = 21
7 х 4 = 28
7 х 5 = 35
7 х 6 = 42
7 х 7 = 49
7 х 8 = 56
7 х 9 = 63
Ввод, вывод данныхЦикл for
✓ 223✗ 695200лёгкаяВойти и решать
Таблица истинности - 06#28388
Юра Баранкин заполнял таблицу истинности функции \((\bar z \vee \bar y) \rightarrow (x \equiv z)\). В тот момент когда его позвал гулять Костя, Юра успел заполнить лишь фрагмент из двух различных строк таблицы. После прогулки Юра заметил, что не указал, к какому столбцу таблицы соответствует каждая из переменных x, y, z.
? ? ? F
1     0
1   1 0

Помогите Юре восстановить столбцы таблицы. Укажите какому столбцу соответствует каждая из переменных x, y, z. 
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
ЕГЭ_информатикаЕГЭ-02. Таблицы истинности
900средняяВойти и решать
Таблица истинности - 07#28387
Юра Баранкин заполнял таблицу истинности функции \((\bar x \vee \bar z) \rightarrow (x \equiv y)\). В тот момент когда его позвал гулять Костя, Юра успел заполнить лишь фрагмент из двух различных строк таблицы. После прогулки Юра заметил, что не указал, к какому столбцу таблицы соответствует каждая из переменных x, y, z.
? ? ? F
1   1 0
1     0

Помогите Юре восстановить столбцы таблицы. Укажите какому столбцу соответствует каждая из переменных x, y, z. 
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
ЕГЭ_информатикаЕГЭ-02. Таблицы истинности
900средняяВойти и решать
Таблицы истинности - 08#28386
Юра Баранкин заполнял таблицу истинности функции \((x \vee y) \rightarrow (x \equiv z)\). В тот момент когда его позвал гулять Костя, Юра успел заполнить лишь фрагмент из двух различных строк таблицы. После прогулки Юра заметил, что не указал, к какому столбцу таблицы соответствует каждая из переменных x, y, z.
? ? ? F
  0 0 0
    0 0

Помогите Юре восстановить столбцы таблицы. Укажите какому столбцу соответствует каждая из переменных x, y, z. 
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.  
ЕГЭ_информатикаЕГЭ-02. Таблицы истинности
900средняяВойти и решать
Два одинаковых массива#28345
На вход подаются два массива A и В, отсортированных по неубыванию. Вам нужно узнать, существует ли такое число, которое содержится в обоих массивах. Если такое число существует, выведите 1, иначе выведите 0.

Входные данные
В первой строке записано натуральные числа N и M– количество элементов первого и второго массива соответственно,  (1 <= N, M <= 108). В следующих двух строках записаны элементы массива A и B. Во второй строке - элементы массива A, в третьей - элементы массива B. Все элементы массива неотрицательные числа, не превышающие 1018.

Выходные данные
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 4 4
1 2 3 4
2 4 7 8		 1
"Два указателя"Хеш
✓ 807✗ 1 970500лёгкаяВойти и решать
Пары точек#28344
На прямой находятся N точек. Требуется подсчитать количество пар индексов (i, j) таких, что i не равно j и |ai - aj|  <= D.

Формат входных данных
В первой строке находятся два числа N и D (1 <= N <= 105, 1 <= D <= 109). Во второй строке находится N неотрицательных чисел, каждое из котороых не более чем 2*109.

Формат выходных данных
Выведите на экран ответ на задачу.
"Два указателя"Использование сортировки
✓ 529✗ 2 794600лёгкаяВойти и решать
Palindromic Paths#28324
Ферма Джона представлена решёткой из N×N полей(2≤N≤18), каждое из которых помечено буквой алфавита. Например,
ABCD
BXZX
CDXB
WCBA
Каждый день корова Беси идёт с левого верхнего угла в правый нижний, двигаясь либо на одну клетку вправо, либо на одну клетку вниз. Беси записывает строку, которая получается в результате её маршрута, построенную из букв, по которым она прошла. Он будет очень расстроена, если в результате построенная строка окажется палиндромом (читается одинаково от начала к концу и от конца к началу), поскольку она запутается в каком направлении она шла.
 
Пожалуйста, помогите Беси определить количество различных палиндромов, которые она сможет сформировать во время своего путешествия. Различные способы формировать один и тот же палиндром следует учитывать только один раз. Например, в примере выше имеется несколько способов сформировать палиндром ABXZXBA, однако существует всего 4 различных палиндрома, которые Беси может сформировать ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.
 
ФОРМАТ ВВОДА :
Первая строка ввода содержит N, а последующие N строк содержат N описание поля. Каждая строка содержит по N символов в диапазоне A..Z.

ФОРМАТ ВЫВОДА :
Выведите количество различных палиндромов, которые Беси может сформировать.
 
Ввод Вывод
4
ABCD
BXZX
CDXB
WCBA
 4

 
meet in the middleПеребор
✓ 7✗ 261 100средняяВойти и решать
Генерация ПСП#27312

Самой инновационной разработкой "British Scientists, Inc" является способ нахождения решения для любой задачи, которую возможно решить с помощью тильда-омега-лямбда-исчисления (то есть, для никакой). Для этого они перебирают все возможные скобочные последовательности длины x, где х - первая цифра секретной константы, использующейся во многих разработках компании. Если x нечётное, они просто прибавляют к нему единицу. Потом они используют продвинутые алгоритмы, использующие нейролингвистическое программирование и вычисленные по спирали Фибоначчи числа Каталана гуголдцатого порядка для определения местонахождения термов. Но эти алгоритмы уже реализованы и запатентованы. 

Ваша же задача - реализовать алгоритм перебора. 


Входные данные
На вход подаётся первая цифра секретной константы - x (\(1 <= x <= 9\)). 
 

Выходные данные
Нужно вывести все ПСП длины x (или x+1, если \(x \% 2 ==1\)) в лексикографическом порядке.

 

Примеры
№ Входные данные Выходные данные
1 1
( )
[ ]
{ }
Рекурсивный переборСтроки
✓ 8✗ 4501 200средняяВойти и решать
Тильда-омега-лямбда-исчисление#27311
Тильда-омега-лямбда-исчисление - ещё более инновационная разработка "British Scientists, Inc" в сфере функционального программирования. Его отличие от омега-лямбда-исчисления только в возможности ставить квадратные и фигурные скобки. Планировались также скобки в форме слоников, но стандарт ЮНИКОД у компании изменить не получилось. 
На вход подаётся тильда-омега-лямбда-выражение длиной не более 10^7 символов. Нужно вывести результат его тильда-иззи-редукции, работающей так же, как и иззи-редукция для омега-лямбда-выражений, но с учётом квадратных и фигурных скобок.

Напомним, иззи-редукция - одна из операций над такими выражениями. При её выполнении проверяется, является ли скобочная последовательность в выражении правильной. Термы при этом игнорируются. Если последовательность правильная - она превращается в терм gg, если нет - в терм wp. 
 

 

Примеры
№ Входные данные Выходные данные
1 main{izzy[lol](ttt)} gg
Конечные автоматыСтроки
✓ 96✗ 43500лёгкаяВойти и решать
Омега-лямбда-исчисление#27310
Омега-лямбда-исчисление - инновационная разработка "British Scientists, Inc" в сфере формальной логики. Любое выражение омега-лямбда-исчисления состоит из круглых скобок и термов (термом может быть любая последовательность из букв латинского алфавита). 
Иззи-редукция - одна из операций над такими выражениями. При её выполнении проверяется, является ли скобочная последовательность в выражении правильной. Термы при этом игнорируются. Если последовательность правильная - она превращается в терм gg, если нет - в терм wp. 
На вход подаётся омега-лямбда-выражение длиной не более 107 символов. Нужно вывести результат его иззи-редукции.
 

 

Примеры
№ Входные данные Выходные данные
1 a(b(xx)f(g(x))m(y)) gg
Линейные алгоритмыСтроки
✓ 115✗ 197600лёгкаяВойти и решать
27309#27309
Вы должны реализовать алгоритм или структуру данных, эффективно реализующих следующие запросы:
1)Добавление в массив элемента
2)Извлечение k-того по величине элемента массива (первым по величине будет считаться наименьший элемент)
Гарантируется, что каждый элемент встречается в массиве всего один раз
 
Входные данные:
В первой строке указано натуральное число n, за ним следует n целых чисел. 
Далее вводится натуральное m - количеств запросов.
В каждой из следующих m строк содержится слово "add" или "get" и целое число k.
Все численные значения по модулю не превосходят 1000. 
В первом случае вы должны дополнить массив элементом со значением k. Иначе - вывести k-тый элемент отсортированного текущего массива (индексация с единицы).
 
Выходные даннные: 
Вы должны ответить на запрос извлечения k-того элемента массива, а именно вывести его значение на экран.

(c) Ибрахим Ахмад, 2017
Двоичное дерево поискаПорядковые статистики
✓ 0✗ 41 300средняяВойти и решать
Экзамен#27308

Ведущий разработчик тильда-омега-лямбда-исчисления, сэр Чарльз, в интервью рассказывал, что интерес к этой проблеме у него появился давным-давно. 
Когда он был ребёнком, Чарльз очень любил общаться в социальных сетях. Свои эмоции (грусть и веселье) он обычно выражал последовательностью из открывающих и закрывающих скобок, поскольку эмоджи и, тем более, стикеров тогда не было. Но дело, которому он в будущем посвятил всю свою жизнь, сэр Чарльз любил уже тогда, поэтому из его сообщений за день гарантированно можно было составить хотя бы одну правильную скобочную последовательность. 
По крайней мере, так он сказал. Однако недавно анонимные хакеры взломали его старую страничку в той самой соцсети и выложили историю сообщений. Увы, приватных фото и других интересностей там не нашлось, но скандал всё равно разразился. Наблюдательные люди заметили, что сообщения за некоторые из дней ну никак не складываются в ПСП. 
Чарльз вскоре выпустил видеообращение, в котором объяснил, что по личным причинам ему приходилось удалять некоторые сообщения, но больше одного сообщения в день он не удалял никогда, и длина таких сообщений не превышала 5 символов. 
Вам стало интересно, не врёт ли сэр Чарльз на этот раз, и вы решили написать программу, чтобы это проверить. 

 
Входные данные:
В первой строке подаётся N (\(1 <= N <= 6\)) - количество сообщений Чарльза в подозрительный день. В следующих N строках находятся скобочные последовательности суммарной длины не больше \(10^6\). Обратите внимание, что способ составить из них ПСП может всё-таки существовать - Вы могли его просто не заметить.

Выходные данные
Выведите "True", если Чарльз не соврал, и есть способ собрать правильную скобочную последовательность, добавив ещё одно сообщение. Выведите "Liar", если это не так.


Примеры
№ Входные данные Выходные данные
1
2
((()())
))))))
 True
Разбор случаевСтроки
✓ 53✗ 747900средняяВойти и решать
Кедор и Гихаил#27305
Меллерт Гихаил сегодня был в прекрасном настроении до того, как его одноклассник Фусков Кедор не заговорил о политике. Гихаил очень сильно разозлился, поэтому придумал задачу по информатике для Кедора, чтобы тот начал решать и наконец-то заткнулся. 
Задача была такая:  “Существует n логических функций, которые зависят от одного и того же множества переменных. Даны n чисел, битовое представление которых определяет таблицу истинности для каждой функции. Вам необходимо найти такой порядок расположения функций, чтобы из каждой функции логически следовала любая из последующих или сказать, что это  невозможно. Если ответ существует, то необходимо найти лексикографически минимальный порядок. Можно показать, что размер множества переменных, от которого зависят функции, не влияет на решение задачи”.
 Кедор – ваш лучший друг, а Гихаил – заклятый враг, поэтому вы решили помочь с решением задачи, а затем вместе с Кедором возобновить разговоры о политике, чтобы Гихаил от злости улетел на Луну.
 
Входные данные
В первой строке дано число n (1 <= n <= 10) – кол-во функций. 
Во второй строке дано n чисел в диапазоне [0; 10^9] – таблицы истинности функций, переведенные в десятичную систему счисления. 
Выходные данные
Если порядок существует, в первой строке выведите “YES”, во второй лексикографически минимальную перестановку из всех возможных. Если порядка нет, то выведите “NO”.

Пример
Ввод Вывод
3
3 1 7
 YES
2 1 3
2
1 2
NO
 

(с)  Курбатов Е., 2017
 
битмаскиПереборРазбор случаев
✓ 3✗ 171 200средняяВойти и решать
Ski Course Rating#27302
Лыжный маршрут описывается M x N решеткой высот (1 <= M,N <= 500), каждая высота в интервале 0 .. 1,000,000,000.  
 
Некоторые из этих ячеек помечены как стартовые точки маршрута. Организаторы хотят вычислить рейтинг трудности каждой стартовой точке. Рейтинг трудности стартовой точки P – это минимальное число D такое, что корова сможет  успешно достичь как минимум T ячеек решётки  (1 <= T <= MN), если она стартует в P и может двигаться в соседнюю ячейку (на север, юг, запад или восток), только если абсолютная величина разности высот в этих ячейках не превосходит D. 
 
Вычислите рейтинг трудности для каждой стартовой точки и выведите их сумму.
 
 
INPUT FORMAT:
 
* Строка 1: Целые числа M, N, T.
 
* Строки 2..1+M: Каждая из этих M строк содержит N целых высот.
 
* Строки 2+M..1+2M: Каждая из этих M строк содержит N величин равных 0 или 1, где 1 означает, что это ячейка – стартовая точка


OUTPUT FORMAT:
 
* Строка 1: Сумма рейтингов трудности всех стартовых точек (заметим, что это число может не поместиться в 32-битное целое, даже если каждый рейтинг в отдельности поместится).
 

INPUT DETAILS:
 
Местность описывается решеткой из 3 х 5 высот.
Верхняя левая и правая нижняя ячейки являются стартовыми точками.
Из каждой стартовой точки мы должны быть способны добраться до 10 ячеек.
 
OUTPUT DETAILS:
Рейтинг трудности верхнего левого угла равен 4.
Рейтинг трудности правого нижнего угла равен 20.
 
Ввод Вывод
3 5 10
20 21 18 99 5
19 22 20 16 17
18 17 40 60 80
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1
 24

 
Бинарный поиск по ответуграфыПоиск компонент связности
—Войти и решать
Building a Ski Course#27301
Фермер Джон помогает превратить его большое поле в лыжный маршрут для предстоящих Му-олимпийских игр. Поле имеет размеры M x N (1 <= M,N <=100) и его целевое финальное состояние описывается решеткой из M x N символов таких как:
 
RSRSSS
RSRSSS
RSRSSS
 
Каждый символ описывает состояние снега на этом участке R – грубый, S – гладкий (организаторы считают, что в таком случае - чередования грубых и гладких участков, гонка будет интересней).
 
Для выполнения этой задачи ФД планирует модифицировать свой трактор так, чтобы тот мог «отштамповать» любой фрагмент размером B x B (B<=M,B<=N) грубым снегом или гладким снегом.
ФД хочет сделать B как можно большим. С B=1 он может подготовить поле, штампуя индивидуально квадраты в соответствии с заданным финальным состоянием. Однако для бОльших значений B может оказаться невозможным выполнить задачу. Каждый квадрат поля должен быть обработан трактором. Невозможно оставить ячейку поля в исходном состоянии.
 
Помогите ФД определить максимально возможное значение B, которое он сможет успешно использовать.
 
INPUT FORMAT:
 
* Строка 1: Два разделённых пробелом целых числа M и N.
 
* Строки 2..M+1: M строк ровно по N символов (каждый R или S),
        описывающих желаемое финальное состояние поля.

 
OUTPUT FORMAT:
 
* Строка 1: Максимальное значение B, которое ФД может использовать, чтобы создать нужное поле.
 
 
Ввод Вывод
3 6
RSRSSS
RSRSSS
RSRSSS
 3


 
OUTPUT DETAILS:
 
ФД может отштамповать R колонках 1-3, затем S в колонках 2-4, затем R в колонках 3-5, и наконец,  S в колонках 4-6.
 
Двумерные массивыКонструктив
✓ 0✗ 41 200средняяВойти и решать
Малыш и Карлсон#27293
Малыш может съесть банку варенья за А1 минут, корзину печенья за B1 минут, выпить бутылку молока за C1 минут. А Карлсон может сделать это за A2, B2, C2 минут соответственно. Напишите программу, вычисляющую, за какое минимальное время они смогут покончить с завтраком, состоящим из банки варенья, корзины печенья и бутылки молока?
 
В первой строке входного файла содержится три целых числа, разделенных пробелами – значения параметров A1, B1, C1. Во второй строке входного файла содержится три целых числа, разделенных пробелами – значения параметров A2, B2, C2. Все числа в диапазоне от 1 до 106.
В выходной файл вывести одно число – минимальное время завтрака с точностью 10−5.
 
Ввод Вывод
13 10 14
6 6 7
 12.00000

(с) Южно-Уральский открытый командный чемпионат, 2006
Бинарный поиск по ответуЗадачи на моделирование
✓ 5✗ 1231 200средняяВойти и решать
Квадратный корень и квадратный квадрат#27292
Найдите такое число x, что \(x^2 + \sqrt{x} = C\) , с точностью не менее 6 знаков после точки.
 
Входные данные
В единственной строке содержится вещественное число \(1 <=C <=10^{10}\).
 
Выходные данные
Выведите одно число — искомый \(x\).
 
Примеры
№ Входные данные Выходные данные
1 2.0000000000 1.000000000
2 18.0000000000 4.000000000
 
Бинарный поиск значения функцииБинарный поиск по ответу
✓ 415✗ 467500лёгкаяВойти и решать
Кубическое уравнение#27291
Даны четыре действительных числа: A, B, C, D. Найдите все корни уравнения Ax3+Bx2+Cx+D=0. Известно, что все корни этого уравнения не превосходят по абсолютной величине 1000. Известно, что любые два корня этого уравнения различаются не менее, чем на 10-6.
 
Входные данные
Программа получает на вход четыре действительных числа: A, B, C, D. Любые из этих четырех чисел, но не все одновременно, могут быть равны 0.
 
Выходные данные
Программа должна вывести от 0 до 3 действительных чисел: корни данного уравнения в порядке возрастания. Кратные корни должны быть выведены только один раз. Значения корней необходимо выводить с точностью до 6 знаков после точки.
 
Ввод Вывод
0 0 1000 -1 0.001
Бинарный поиск значения функцииБинарный поиск по ответу
✓ 30✗ 3381 000средняяВойти и решать
Поделиться
Класснуть