Информатика

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

Аксинья любит Григория, но она замужем за Степаном. Со своим мужем она несчастна, поэтому время, которое она проводит с ним можно характеризовать отрицательным показателем счастья Аксиньи (\(a_i < 0\)), а то время, которое она проводит с Григорием, - положительным показателем счастья (\(a_i > 0\)). Известно, что Аксинья проводит один день либо с мужем, либо с Григорием. 

Найдите максимальное суммарное счастье за L дней, в которые Аксинья будет проводить с мужем не более C дней.
 
Входные данные
В первой строке подается 3 числа: N – кол-во дней, L и C (\(1 <= L, C <= N <= 1 000 000\)).
Во второй строке содержится N чисел a_i (\(1 <= |a_i| <= 1 000 000 000\)).

Входные данные
Требуется вывести ответ на задачу.
 

 

Примеры
№ Входные данные Выходные данные
1 5 3 3
1 -1 2 -2 3		 3
"Два указателя"Префиксные суммы(минимумы, ...)
✓ 94✗ 501800средняяВойти и решать
Fenced In#29546
Коровы Фермера Джона боятся больших пространств. Поэтому разгородил своё поле на некоторое количество маленьких регионов, построив вертикальные (север-юг) и горизонтальные (восток-запад) изгороди.
Поле представляет собой прямоугольник с угловыми вершинами в точках (0,0) and (A,B). ФД построил n вертикальных изгородей (0≤n≤25,000) в различных позициях a1…an (0<ai<A); каждая изгородь проходит от точки (ai,0) до точки (ai,B). Он также построил m горизонтальных изгородей (0≤m≤25,000) в в различных позициях b1…bm (0<bi<B); каждая изгородь, проходит из (0,bi) в (A,bi). Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на (n+1)(m+1) регионов.
 
К несчастью, ФД забыл построить ворота в своих изгородях, сделав невозможным коровам покидать свой регион. Он хочет исправить ситуацию, удалив куски изгороди, чтобы позволить коровам перемещаться между соседними регионами. Он хочет выбрать некоторые пары соседних регионов и удалить всю длину изгороди между ними. А ещё он хочет обеспечить, чтобы коровы могли попасть в любую часть поля.
 
Например, ФД мог построить изгороди так:
 
+---+--+
|      |   |
+---+--+
|     |    |  
|     |    |
+---+--+
и открыть их так:
 
+---+--+
|          |  
+---+  +  
|          |  
|          |
+---+--+
Помогите ФД определить минимальную суммарную длину изгородей, которые он должен удалить, чтобы достичь своей цели.
 
ФОРМАТ ВВОДА:
Первая строка ввода содержит числа A, B, n, and m (1≤A,B≤1,000,000,000). Следующие n строк содержат a1…an. Следующие m строк содержат b1…bm.

ФОРМАТ ВЫВОДА:
Выведите минимальную длину изгороди, которую ФД должен удалить. Заметим что это число может не поместиться в 32-битное целое и Вам нужно использовать 64-битное целое (например, "long long" в C/C++ )
 
Ввод Вывод
15 15 5 2
2
5
10
6
4
11
3
 44
Алгоритмы сортировкиЖадный алгоритм
✓ 1✗ 41 200средняяВойти и решать
Динамика - 06#29513
Исполнитель Громозека выполяет некоторые действия с числом на экране. Громозека знает всего три команды, которым присвоены номера:
  1. Прибавить 1
  2. Прибавить 2
  3. Умножить на 3
Сколько существует программ, для которых при исходном числе 4 результатом является число18 и при этом траектория вычислений содержит число 7?
ЕГЭ_информатикаЕГЭ-13. Динамическое программирование
900средняяВойти и решать
Дом у дороги#29479
Министерство дорожного транспорта решило построить себе новый офис. Поскольку министр регулярно выезжает с инспекцией наиболее важных трасс, было решено, что офис министерства не должен располагаться слишком далеко от них.
 
Наиболее важные трассы представляют собой прямые на плоскости. Министерство хочет выбрать такое расположение для своего офиса, чтобы максимум из расстояний от офиса до трасс был как можно меньше.
 
Требуется написать программу, которая по заданному расположению наиболее важных трасс определяет оптимальное расположение дома для офиса министерства дорожного транспорта.
 
Входные данные
Первая строка входного файла содержит одно целое число n — количество наиболее важных трасс (1  ≤ n ≤ 104 ).
 
Последующие n строк описывают трассы. Каждая трасса описывается четырьмя целыми числами x1, y1, x2 и y2 и представляет собой прямую, проходящую через точки (x1, y1)  и (x2, y2) . Координаты заданных точек не превышают по модулю 104. Точки (x1 , y1)  и (x2 , y2)  ни для какой прямой не совпадают.
 
Выходные данные
Выходной файл должен содержать два разделенных пробелом вещественных числа: координаты точки, в которой следует построить офис министерства дорожного транспорта. Координаты по модулю не должны превышать 109, гарантируется, что хотя бы один такой ответ существует. Если оптимальных ответов несколько, необходимо выведите любой из них.
 
Ответ должен иметь абсолютную или относительную погрешность не более 10−6, что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно x, а в правильном ответе оно равно y. Ответ будет засчитан, если значение выражения | x − y | /  max(1, |y| )  не превышает 10−6.
 
 
Ввод Вывод
4
0 0 0 1
0 0 1 0
1 1 2 1
1 1 1 2
 0.5000000004656613 0.4999999995343387
7
376 -9811 376 -4207
6930 -3493 6930 -8337
1963 -251 1963 -5008
-1055 9990 -684 9990
3775 -348 3775 1336
7706 -2550 7706 -8412
-9589 8339 -4875 8339
 4040.9996151750674 12003.999615175067

 Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2011, 2 день, Задача D 
Вычислительная геометрияТернарный поиск
✓ 2✗ 381 300средняяВойти и решать
Палиндром#29473
Палиндром - это строка, которая читается одинаково как справа налево, так и слева направо. 
 
На вход программы поступает набор больших латинских букв (не обязательно различных). Разрешается переставлять буквы, а также удалять некоторые буквы. Требуется из данных букв по указанным правилам составить палиндром наибольшей длины, а если таких палиндромов несколько, то выбрать первый из них в алфавитном порядке.
 
Входные данные
В первой строке входных данных содержится число N (1 <= N <= 100000). Во второй строке задается последовательность из N больших латинских букв (буквы записаны без пробелов).
 
Выходные данные
В единственной строке выходных данных выдайте искомый палиндром.
 
Ввод Вывод
3
AAB
 ABA
6
QAZQAZ
 AQZZQA
6
ABCDEF
 A
Алгоритмы обработкиИспользование сортировки
✓ 294✗ 532700средняяВойти и решать
Анаграммы#29469
Слово называется анаграммой другого слова, если оно может быть получено перестановкой его букв.
 
Формат входных данных
Даны два слова на отдельных строках. Слова состоят из строчных латинских букв и цифр. Длины слов не превышают 255.
 
Формат выходных данных
Требуется вывести "YES"  – если введенные слова являются анаграммами друг друга, "NO"  – если нет.
Использование сортировкиСтроки
✓ 288✗ 366600лёгкаяВойти и решать
Роза ветров#29448
При выборе места строительства жилого комплекса при металлургическом комбинате необходимо учитывать "розу ветров" (следует расположить жилой комплекс так, чтобы частота ветра со стороны металлургического комбината была бы минимальной). Для этого в течении года проводилась регистрация направления ветра в районе строительства. Данные представлены в виде массива, в котором направление ветра ветра за каждый день (365) кодируется следующим образом: 
1 - северный (N),
2 - южный (S)
3 - восточный (E)
4 - западный (W)
5 - северо-западный (NW)
6 - северо - восточный (NE)
7 - юго-западный (SW)
8 - юго-восточный (SE).
Определить, как должен быть расположен жилой комплекс по отношению к комбинату

Входные данные: 
В первой строке подается 365 значений от 1 до 8 (направление ветра)

Выходные данные:
Вывести соответствующие буквы (аббревиатуру - смотри список выше), с какой стороны следует построить жилой комплекс
 
Алгоритмы обработкиОдномерные массивы
✓ 96✗ 1 017800средняяВойти и решать
Спортсмен-победитель#29438
Имеется информация о времени (в секундах) прохождения трассы 25 спортсменов, участвовавших в лыжной гонке. Выведите результат спортсмена-победителя гонки.

Входные данные
Входная строка содержит 25 чисел, разделенных одним пробелом - время каждого спортсмена.

Выходные данные
Выведите на экран результат спортсмена-победителя гонки. Гарантируется, что победитель гонки единственный.
 
Пример
№ Входные данные Выходные данные
1 78 35 79 47 104 53 58 86 108 94 90 27 33 88 17 15 37 98 14 67 76 45 94 97 46  14
Алгоритмы обработкиОдномерные массивы
✓ 6 253✗ 8 543200лёгкаяВойти и решать
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
✓ 224✗ 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
"Два указателя"Хеш
✓ 832✗ 2 010500лёгкаяВойти и решать
Пары точек#28344
На прямой находятся N точек. Требуется подсчитать количество пар индексов (i, j) таких, что i не равно j и |ai - aj|  <= D.

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

Формат выходных данных
Выведите на экран ответ на задачу.
"Два указателя"Использование сортировки
✓ 530✗ 2 802600лёгкаяВойти и решать
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лёгкаяВойти и решать
Поделиться
Класснуть