Информатика

1 132 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
49#33264
Камера снимает видео без звука с частотой 24 кадра в секунду, при этом изображения используют палитру, содержащую 224 = 16 777 216 цветов.  Параллельно записывается звук в формате стерео. 1 минута видеоряда в среднем занимает 36 Мбайт, 1 минута звуковой дорожки занимает в среднем 6 Мбайт. Для хранения, видео преобразуют так, что для изображений используется палитра в 256 цветов, а звук перезаписывается в формате моно с частотой дискретизации 16 кГц и глубиной кодирования 16 бит. Другие преобразования и иные методы сжатия не используются. Сколько Мбайт составляет средний вес 1 минуты преобразованного видео со звуком? (Ответ округлите до ближайшего целого числа).
Кодирование звука, видео
1 300труднаяВойти и решать
*Упорядочивания#33257
Сегодня у Кэрол выходной. Но даже в этот прекрасный весенний день она не отдыхает, а тренируется и готовится к сражениям со скруллами. Одним из важных навыков является умение быстро ориентироваться в незнакомых местах. Для того, чтобы отточить это умение, Кэрол пригласила своего наставника Йон-Рогга.
Кэрол и Йон-Рогг будут играть в следующую игру. Сначала Йон-Рогг нарисует на бумаге карту убежища скруллов. Карта представляет из себя n помещений, пронумерованных от 1 до n. Некоторые пары помещений соединены двусторонними переходами. Убежище устроено так, что от любого помещения до любого другого можно добраться, перемещаясь по коридорам. Для того, чтобы игра не была слишком сложной, Йон-Рогг нарисует ровно n − 1 переход между помещениями. Иными словами, карта убежища представляет собой дерево.
Известно, что для перевозки грузов между помещениями в убежище скруллы используют специальных роботов. Роботы довольно примитивны и плохо ориентируются в убежище. Для решения этой проблемы скруллы выбрали в каждом переходе ровно одно направление, вдоль которого могут перемещаться роботы.
После того, как Йон-Рогг нарисует на бумаге карту убежища, он также для каждого перехода отметит, в каком направлении по нему перемещаются роботы. Иными словами, Йон-Рогг ориентирует ребра нарисованного дерева.
Чтобы структурировать карту убежища, Кэрол должна составить список, состоящий из всех номеров помещений в некотором порядке. При этом должно выполняться следующее условие: в любом переходе роботы перемещаются от помещения, которое идет в списке раньше, к помещению, которое идет с писке позже. Более формально, Кэрол должна составить такую перестановку номеров помещений p1p2 . . . pn, для которой верно, что если роботы могут перемещаться по переходу от помещения pi к помещению pj , то i < j.
Пока Кэрол бьется над своим заданием, Йон-Роггу стало интересно, сколько всего решений существует у этой задачи. Иными словами, Йон-Роггу интересно, сколько перестановок удовлетворяют условию, описанному выше. Помогите ему узнать это. Так как ответ может быть очень большим, Йон-Рогг попросил вас сообщить лишь его остаток от деления на 998 244 353.

Входные данные: Первая строка входных данных содержит единственное целое число n — количество помещений в убежище, нарисованном Йон-Роггом (1 <= n <= 3 000).
Каждая из следующих n − 1 строк содержит два целых числа a, b — номера помещений, соединенных очередным коридором (1 <= a, b <= n). Роботы перемещаются по коридору в направлении от помещения a к помещению b.
Гарантируется, что убежище представляет собой дерево, то есть от любого помещения можно добраться до любого другого, двигаясь по переходам (возможно, в направлении, противоположном направлению движения роботов в этом переходе).

Выходные данные: Выведите остаток от деления на 998 244 353 количества различных перестановок p1p2 . . . pn, для которых верно, что если роботы перемещаются по переходу от помещения pi к помещению pj , то i < j.
 
Примеры
№ Входные данные Выходные данные
1
3
1 2
1 3
 2
2
4
2 3
3 1
2 4
 3

Замечание
В первом тесте из примера Кэрол может выписать две перестановки: {1, 2, 3} или {1, 3, 2}.
Во втором тесте Кэрол может выписать три перестановки: {2, 3, 1, 4}, {2, 3, 4, 1} или {2, 4, 3, 1}.
 
Топологическая сортировка
✓ 3✗ 121 300средняяВойти и решать
Все кратчайшие маршруты#33229
Учёный-ботаник получил карту дорог страны Лимония. Чтобы составить план исследования этой страны, ему требуется найти кратчайшие расстояния между каждой парой городов этой страны (можно ехать только по проложенным дорогам). Помогите учёному – напишите программу, которая решает эту задачу.
 
Входные данные
В первой строке вводится количество городов N ( 1 ≤ N ≤ 100 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему дорог между городами: положительное число означает расстояние между городами, ноль говорит о том, что дороги нет.
 
Выходные данные
Программа должна вывести все кратчайшие маршруты между всеми городами в следующем формате:
 
(1->3): 1 2 3 (23)
 
Сначала выводятся номера начального и конечного города (в скобках), затем – последовательность номеров городов, составляющая оптимальный маршрут, затем (в скобках) длина этого маршрута. Если между какими-то городами нет дороги, нужно вывести число 0.
 
Ввод Вывод
4
0 0 0 0
0 0 2 1
0 2 0 4
0 1 4 0
(1,2): 0 
(1,3): 0 
(1,4): 0 
(2,3): 2 3 (2)
(2,4): 2 4 (1)
(3,4): 3 2 4 (3)

Алгоритм Флойдакратчайшие пути
✓ 1✗ 901 200средняяВойти и решать
Про любовь...#29478
Паук и паучиха плывут по озеру на двух веточках. Плавать они не умеют, поэтому смогут встретиться только тогда, когда веточки соприкоснутся.


 

Считая, что веточки имеют форму отрезков, и что они плывут с постоянными скоростями, определите, сколько осталось ждать встречи несчастным членистоногим.

 
Входные данные
Входной файл содержит 12 чисел: x1, y1, x2, y2, x3, y3, x4, y4, v1x, v1y, v2x, v2y. Координаты вершин первого отрезка: (x1, y1) и (x2, y2), координаты вершин второго отрезка: (x3, y3) и (x4, y4), скорость первого отрезка (v1x, v1y), скорость второго отрезка (v2x, v2y). Все числа целые и не превосходят по модулю 104. В начальный момент времени веточки не соприкасаются. Гарантируется, что веточки имеют ненулевую длину.
 
Выходные данные
Выведите в выходной файл время до ближайшего момента, когда веточки соприкоснутся, с ошибкой не более 10−4. Если веточки не соприкоснутся никогда, выведите число -1.
 
Ввод Вывод
0 0 -1 3
4 4 7 7
3 0
0 -1
 1.6
0 0 -1 3
4 4 7 7
1 0
0 -3
 -1
 
Тернарный поиск
✓ 11✗ 1001 300средняяВойти и решать
Архимедова спираль#29477
Дима недавно поступил на работу в НИИ Плоских Кривых. Как следует из названия этого научно- исследовательского института, он занимается различными исследованиями в области плоских кривых. Недавно Димин начальник Георгий столкнулся с весьма интересной кривой, которая, как выяснилось после некоторого исследования, известна под названием Архимедовой спирали. Архимедова спираль плоская кривая, изображающая траекторию точки M, которая равномерно движется вдоль луча OK с началом в O, в то время как сам луч OK равномерно вращается вокруг точки O (см. рисунок). Другими словами, расстояние до начала координат ρ = OM линейно зависит от угла поворота φ луча OK. При этом повороту луча OK на один и тот же угол соответствует одно и то же приращение расстояния ρ. 
 
Движение точки M можно задать с помощью ряда параметров:
 
• начального угла поворота α луча OK (измеряется в градусах против часовой стрелки относительно положительного направления оси OX);
 
• угловой скорости вращения ω луча OK (измеряется в градусах за единицу времени);
 
• начального расстояния R от точки M до начала координат (точки O);
 
• скорости движения V точки M по лучу OK.
 
Если, задав эти параметры, не ограничить время движения точки M, то получится бесконечная кривая, исследовать которую достаточно трудно. Поэтому Дима решил ограничиться исследованием некоторой части этой кривой той, которая получается при движении точки M от нулевого момента времени до момента времени T. Задача, которую решает Дима состоит в поиске прямоугольника минимальной площади со сторонами, параллельными осям координат, в который ее можно вписать.
 
Требуется написать программу, которая найдет искомый прямоугольник

 
Входные данные
Входной файл содержит четыре целых числа: ω (1 ≤ ω ≤ 100), V (1 ≤ V ≤ 100), R (0 ≤ R ≤ 100) и T (1 ≤ T ≤ 1000). В этой задаче считается, что начальный угол поворота α равен нулю.
 
Выходные данные
В первой строке выходного файла выведите два вещественных числа — координаты левого нижнего угла искомого прямоугольника, а во второй строке — координаты правого верхнего угла искомого прямоугольника.
 
Ответ будет считаться правильным, если значение каждой из координат будет отличаться от истинного значения не более чем на 10-5.
Тернарный поиск
✓ 9✗ 261 200средняяВойти и решать
Шаблон с ? и *#28419
Шаблоном называется строка, состоящая из английских букв (a, ..., z, A, ..., Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * – на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.
 
Имеются два шаблона. Требуется найти строку минимальной длины, которая удовлетворяет обоим шаблонам, либо выдать сообщение, что такой строки не существует.
 
Входные данные
Заданные шаблоны записаны в первых двух строках входных данных. Длина каждого шаблона не превосходит 80 символов.

Выходные данные
Выведите строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение "No solution!"
 
Примеры
№ Входные данные Выходные данные
1
AB?
*BC
 ABC
Динамическое программирование
✓ 21✗ 1741 200средняяВойти и решать
Расстояние между точками#28346
На окружности заданы N точек, надо найти пару точек, расстояние между которыми (по хорде окружности) максимально. 

Входные данные
В первой строке задано N (1 <= N <= 100 000).
В следующей строке даны N пар вещественных чисел. Сначала описывается координата x, потом – y.

Выходные данные
Вывести два числа – номера точек, расстояние между которыми максимально. Сначала идет наименьшее число, потом наибольшее.
 
Ввод Вывод
3
1.4142 1.4142
0 2
-1.4142 -1.4142		 1 3

 
"Два указателя"геометриясортировки
✓ 1✗ 4141 400средняяВойти и решать
Trapped in the Haybales#28323
Фермер Джон получил груз из N больших стогов сена (1≤N≤4000) и разместил эти стога в различных точках дороги, ведущей к его амбару. К несчастью, он совсем забыл, что Беси пасётся вдоль этой дороги и может оказаться в ловушке из этих стогов.
Каждый стог с номером j имеет размер Sj и уникальную позицию Pj, задающую его положение вдоль одномерной дороги. Беси начинает движение в некоторой позиции, где не было стога и может передвигаться свободно вдоль дороги, вплоть до позиции, где размещён стог сена, но она не может перейти эту позицию. В качестве исключения, если она движется в некотором направлении D единиц расстояния, она набирает достаточно скорости, чтобы протаранить любой стог сена с высотой строго меньше, чем D. Конечно, после того, как она сделает это, перед ней открывается пространство с другими стогами сена, которые она тоже может протаранить.
 
Беси может выйти на свободу как после самого левого, так и после самого правого стога сена. Пожалуйста, определите общую длину дороги, состоящую из тех позиций, из которых Беси не сможет выбраться. Например, если Беси не может выбраться если она начинает с позиции между стогами в позициях 1 и 5, тогда ответ будет 4 (поскольку эти позиции ограничивают область размером 4).
 
ФОРМАТ ВВОДА:
Первая строка ввода содержит NN. Каждая из последующих NN строк описывает стог и содержит два целых числа, определяющих его размер и позицию, каждое в диапазоне 1…109.

ФОРМАТ ВЫВОДА:
Выведите целое число, определяющее длину части дороги из которой Беси не сможет сбежать.
 
Ввод Вывод
5
8 1
1 4
8 8
7 15
4 20
 14
Задачи на моделирование
✓ 3✗ 61 200средняяВойти и решать
Тандемный префикс#27306
Егор Кубратов очень огорчен задачами с codeforces и олимпиады Иннополиса, поэтому теперь он сам придумывает задачи и сам же их решает. Сегодня он придумал следующую задачу:
 
“Тандемный префикс – это подстрока, образованная конкатенацией двух непустых, не обязательно одинаковых префиксов строки и не являющаяся префиксом строки*. Вам необходимо найти длиннейший тандемный префикс данной строки. Если вариантов несколько, выведите тот, вхождение которого самое раннее. Если тандемного префикса не существует, то выведите -1”
 
*Имеется в виду, что тандемный префикс не является подстрокой, начинающейся в первом символе строки. То есть по составу букв он может являться каким-то префиксом, но только если начинается не в первой позиции. Например, в строке “aaa” подстрока [2;3] является тандемным префиксом.
 
Входные данные
В первой строке дана строка, состоящая из строчных латинских букв. Длина строки не превышает 105.
 
Выходные данные
Выведите ответ, если он существует. Иначе выведите -1.
 
Ввод Вывод
abcabac aba

Подстроки abca и abcab являются конкатенациями двух префиксов, но они сами являются префиксами, что противоречит определению тандемного префикса, поэтому aba – единственный тандемный префикс данной строки.

(с) Курбатов Е., 2017
Z-функция. Префикс-функциястроковые суфф. структуры
✓ 1✗ 91 300средняяВойти и решать
Fencing the Herd#27299
Фермер Джон нуждается в вашей помощи. Он решил построить изгородь в форме прямой, чтобы ограничить движение своих коров. Он рассматривает несколько вариантов размещения изгороди и с вашей помощью хочет определить наиболее подходящий. Подходящим считается вариант, когда все коровы находятся по одну сторону изгороди. Изгородь не считается подходящей, если хоть одна корова расположена на изгороди. ФД будет задавать вам вопросы про варианты изгороди, на которые вы должны отвечать YES, если изгородь подходит и NO, в противном случае.
 
Кроме того, ФД может добавить новых коров в стадо. С того момента, как корова добавлена, она должна быть по одну сторону от изгороди со всеми другими коровами.
 
Входные данные 
Первая строка ввода содержит N (1 <= N <= 100000) и Q (1 <= Q <= 100000) разделённые одним пробелом. Это, соответственно, начальное количество коров в стаде и количество запросов.
Следующие N строк описывают начальное положение стада. Каждая строка содержит два целых числа x и x (разделённые пробелом), представляющие позицию очередной коровы.
Оставшиеся Q строк содержат запросы, либо добавляющие новую корову в стадо, либо проверяющие изгородь на применимость. Строка вида 1 x y означает, что новая корова добавляется в стадо на позицию x y. Строка вида 2 A B C означает, что ФД хочет проверить изгородь, описываемую прямой Ax+By=C.
Все позиции коров уникальны (-109 <= x, x <= 109). Кроме того, -109 <= A, B <= 109 и -1018 <= C <= 1018. Никогда не будет изгороди с A = B = 0.
 
Выходные данные
Для каждой изгороди выведите YES, если она подходит и NO, в противном случае.
 
Ввод Вывод
3 4
0 0
0 1
1 0
2 2 2 3
1 1 1
2 2 2 3
2 0 1 1
YES
NO
NO
 
Прямая 2x + 2y = 3 оставляет начальные 3 коровы по одну сторону. Однако корова (1,1) на другой стороне, поэтому после её добавления такая изгородь уже не подходит. Прямая Y=1 не подходит, поскольку коровы (0,1) и (1,1) находятся на ней.
 
Предупреждение: ввод-вывод для этой задачи очень большой. В С++ можно использовать scanf или ios_base::sync_with_stdio(false). В Java надо не использовать java.util.Scanner. Не делайте flush вывода (например? используя std::endl) после каждого запроса.
Вычислительная геометрия
✓ 0✗ 11 300средняяВойти и решать
МАРШРУТЫ#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средняяВойти и решать
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средняяВойти и решать
Линейная классификация#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средняяВойти и решать
Крепкий дом#27001
Джон Доу хочет построить крепкое здание, чтобы никто и никогда не нашел его. У него есть кирпичи 1х2, 1х3 и "уголки", то есть квадратики 2х2,  у которых отсутствует одна клетка. Для уточнения смотрите на рисунки.
Стеной назовем клеточный прямоугольник, который заполняют кирпичи. Кирпичи должны ложиться по линиям сетки, их можно как угодно поворачивать. Кирпичи не могут накладываться друг на друга и на каждой клетке должен лежать кирпич.
Джон считает стену крепкой, если нельзя провести такую прямую, что по обе стороны от нее есть кирпичи и она не пересекает ни одного кирпича. Касание кирпичей не считается пересечением. Вам требуется спроектировать крепкую стену, величиной NхM. Можно поворачивать кирпичи на углы, кратные 90 градусам.

Формат входных данных
Вводятся числа N и M  (1 <=N, M <= 100) высота и ширина требуемой стены.

Формат выходных данных
Выведите N строк, содержащих по M символов от «A» до «Z», описывающие стену. Каждый кирпич должен описываться одинаковыми символами (кирпичи, имеющие общую сторону должны описываться различными символами). Не должно существовать прямой, по обе стороны которой были бы кирпичи и она не пересекала бы ни один из кирпичей. Если стену с заданными ограничениями построить невозможно, выведите «impossible».
Частичные решения, работающие при N, M <=6 получат не менее 40 баллов.
Двумерные массивы
✓ 0✗ 11 300средняяВойти и решать
Простые вычисления#26997
Вам даны числа X и N. Посчитайте значение выражения:
 


Формат входных данных
В первой строке через пробел записаны действительное число X и натуральное число N (-1000 <= X<=1000, 1<=N <=1012). Число X содержит в своей записи не более 8 знаков после десятичной точки.

Формат выходных данных
Вывести значение суммы с двумя знаками после десятичной точки. 
Частичные решения, работающие при N<=107 получат не менее 40 баллов.
 
Ввод Вывод
1.24 5 -0.04
Вычисление по заданной формуле
✓ 0✗ 421 300средняяВойти и решать
Эвакуация#24913
Через T минут армия читаури под предводительством Локи атакует Землю. Мстители никак не успевают помешать открытию портала в Нью-Йорке, поэтому Капитан Америка принял решение эвакуировать из города всех его жителей. Ему необходимо выяснить, успеют ли жители города эвакуироваться до начала вторжения.
 
Окрестности Нью-Йорка можно представить как набор небольших городов, связанных между собой дорогами с односторонним движением. Каждая дорога характеризуется своей длиной и пропускной способностью. Длина дороги l означает, что въехав на нее в момент времени t, автомобиль окажется в конце этой дороги через l минут, в момент времени t + l. Пропускная способность дороги s означает, что каждую минуту на эту дорогу могут въехать не больше, чем s автомобилей. Приехав в какой-нибудь город, любой автомобиль может сразу продолжить путь, въехав на какую-то дорогу, выходящую из этого города, а может остановиться в этом городе на любое количество минут, и только потом уехать из него. 

Капитан Америка уже решил, в каком именно городе должны оказаться жители Нью-Йорка после эвакуации. Также ему известно, сколько автомобилей необходимо для эвакуации всего города.  Теперь ему необходимо выяснить успеют ли все жители эвакуироваться до прибытия захватчиков и, если да, какое минимальное количество времени у них на это уйдет, а если нет  какому минимальному числу автомобилей с горожанами не удастся доехать до безопасного города.

Формат входного файла
Первая строка входного файла содержит четыре целых числа n, m, K и T (1 ≤ n x T ≤ 10 000, 1 ≤ m, K ≤ 10 000)  количество городов в окрестностях Нью-Йорка, количество дорог между ними, количество автомобилей, которым необходимо попасть из Нью-Йорка в безопасный город и время до вторжения захватчиков соответственно. Следующие m строк содержат описания дорог между городами.
Каждая дорога описывается четырьмя целыми числами u, v, l и s (1 ≤ u, v ≤ n, u != v, 1 ≤ s ≤ 3 000, 1 ≤ l ≤ 200)  город, из которого выходит эта дорога, город, в который она ведет, ее длина и пропускная способность соответственно.

Между двумя городами может существовать только одна дорога, ведущая в каком-то направлении. Нью-Йорком считается город с номером 1, а безопасным городом  город с номером n. в момент времени 0 все автомобили находятся в Нью-Йорке.

Формат выходного файла
Если все жители Нью-Йорка успеют добраться до безопасного города не более, чем за T минут, выведите в выходной файл минимальное количество минут, которое им на это понадобится. В противном случае выведите минимальное количество автомобилей, которым не удастся попасть в безопасное место за T минут. Да, не нужно выводить, какой из этих случаев имеет место :-).
 
Ввод Вывод
5 5 10 10
1 2 2 2
2 3 1 1
2 4 1 1
4 5 2 4
3 5 2 4		 9
Обход в глубину
✓ 0✗ 61 300средняяВойти и решать
Тессеракт#24912

Коварный Локи напал на Землю, использовав Тессеракт для того, чтобы переместиться из Асгарда. Понимая ценность этого артефакта, он решает защитить его от использования кем-либо, кроме себя. Для этого он решает немного изменить его внутреннюю структуру так, чтобы только он знал, как её можно восстановить.

После внимательного исследования, внимание Локи привлекла цепочка маленьких кубиков внутри Тессеракта. Среди этих кубиков были крайне похожие друг на друга, что идеально подходило для небольшого, но важного для работы изменения Тессеракта. Проявив восхвалённую в легендах коварность, Локи, в надежде на невнимательность людей, решил внести два изменения таких, чтобы после каждого из них, артефакт выглядел бы таким же, как и раньше.

Всего цепочка, которую собирается менять Локи, состоит из \(n\) кубиков. Среди них есть похожие, на чём и собирается сыграть Локи. Он берёт какой-то отрезок кубиков в этой цепочке, вырывает его, разворачивает и вставляет обратно. При этом, он выбирает отрезок таким образом, чтобы внешне цепочка не изменилась. Затем он повторяет то же самое с другим отрезком, который содержал в себе первый, но не совпадал с ним. Очевидно, после этих двух операций цепочка уже не будет совпадать с исходной, и артефакт будет испорчен.

Чтобы оценить вероятность быть уличённым в порче Тессеракта, Локи решил выяснить, сколькими способами он мог выбрать первый отрезок.

Рассмотрим, к примеру, цепочку \(aabaa\), в которой одинаковыми буквами обозначены похожие кубики. Тогда настоящий Тессеракт содержит цепочку \(a_1a_2ba_3a_4\). Локи может, например, проделать следующую последовательность действий: \(a_1a_2ba_3a_4 \to a_2a_1ba_3a_4 \to a_4a_3ba_1a_2\). Внешне ничего не изменилось, однако цепочка уже другая.

Формат входных данных
В первой и единственной строке задана цепочка, состоящая из маленьких латинских букв, длиной не более \(100{\,}000\).

Формат выходных данных
Единственное число — количество различных первых действий Локи.

Z-функция. Префикс-функция
✓ 0✗ 51 200средняяВойти и решать
Поезд#24691
Вам дан массив целочисленных чисел размера n.Необходимо реализовать структуру данных,которая могла бы исполнять следующие операции:
1)Прибавлять всем числам на отрезке [l;r] величину d.
2)Получить сумму чисел на отрезке [l;r].
3)Получить минимум из чисел на отрезке [l;r].
INPUT
На ввод приходит число n – размер массива.В следующей строке,через пробел, даны n чисел - ai.
Далее задается число m - количество запросов.В следующих m строках запросы трех видов:
1)add l r d - прибавление на отрезке [l;r] числа d.
3)rsq l r - запрос суммы на отрезке [l;r].
3)rmq l r - запрос минимума на отрезке [l;r].
OUTPUT
Ответы для запросов второго и третьего типов через пробел.
P.S. 0 < n, m < 100001 ai < 1000000001.
P.S.S. Гарантируется,что ответ вмещается в 64-битный тип данных.
INPUT
5
1 2 3 4 5
3
rsq 1 5
add 2 3 1
rmq 2 4
OUTPUT
15 3


(с) Никита Максимов, 2017г.
Дерево отрезков, RSQ, RMQ
✓ 1✗ 61 300средняяВойти и решать
Поделиться
Класснуть