Алексей Денисович, успешный front-end разработчик, который может написать сайт для Google.
Но у него возникли сложности с красивым от отображением html-текста на экране.
Помогите Алексею Денисовичу проверить, корректно ли он написал html-текст.
Назовем открывающимся тегом строку: “<x>”, где x - любое слово, составленное из строчных букв латинского алфавита.
Каждому открывающемуся тегу ДОЛЖЕН соответствовать закрывающийся тег вида: “</x>”,
где x - то же слово, что и было использовано в открывающимся теге.
Важно помнить:
Пустая строка — html-текст.
Строка вида: “<div>hello</div>” — html-текст, где hello - любое слово, составленное из строчных букв латинского алфавита.
Строка вида: “<div><a></a></div>” — html-текст.
Если a, b — строки, содержащие html-текст, то a + b — html-текст.
Необходимо проверить, является ли введенная строка корректным html-текстом. Html-текст является корректным, если:
Для каждого открывающегося тега есть соответствующий закрывающийся, причем открывающийся тег ВСЕГДА находится до закрывающегося.
Не нарушена вложенность тегов, а именно отсутствуют пересекающиеся теги, т.е, <div><span></div></span> - недопустимо.
Не существует случая, когда тег находится внутри тега, т.е. <div<a>> - недопустимо.
Если html-текст корректен по всем правилам описанным выше, то выводится YES, иначе NO.
Формат входных данных
Входные данные состоят из единственной непустой строки - html-текста, длина которой не превосходит 1000 символов.
Формат выходных данных
Если html-текст корректен, то выводится YES, иначе NO.
Вам дано n одномерных отрезков ненулевой длины(каждый отрезок представляется
двумя целыми числами — координатами его концов).
Давайте определим функцию f(x) как количество отрезков,
покрывающих точку x (отрезок покрывает точку x,
если l≤x≤r где l — левый конец отрезка, а r — правый).
Пару точек x1 и x2 назовём парным максимумом,
если они по отдельности принадлежат большему числу отрезков,
чем любая другая точка. Другими словами, если для любого x
отличного от x1 и x2 выполняется f(x) < f(x1)иf(x) < f(x2).
Ваша задача определить, сколько существует пар целочисленных точек, которые могут стать парными максимумами, если удалить несколько (возможно ни одного) отрезков.
Формат входных данных
Первая строка каждого набора содержит целое число n.
Далее следует n строк, i-я содержит два целых числа li,
ri - концы отрезков.
Формат выходных данных
Вам необходимо вывести одно целое число - количество парных пар целочисленных точек,
которые могут стать парными максимумами.
Где-то в далекой системе есть N различных планет,
расположенных в трехмерном пространстве.
Каждая планета представляет собой сферу идеальной формы.
У каждой планеты есть известный радиус ri и центр с координатами xi, yi, zi.
Также в этой галактике есть чёрная дыра, которая также представляет собой сферу некоторого радиуса.
Вам стало интересно, какой радиус должна иметь чёрная дыра, находящаяся в центре этой системе (координаты 0,0,0),
чтобы разом поглотить все находящиеся в этой системе планеты.
Считается, что чёрная дыра может поглотить планету, если все точки в этой планете находятся внутри чёрной дыры.
Вычислите минимальный возможный радиус чёрной дыры, которая может поглотить все планеты с точностью до 5 символов.
Формат входных данных
В первой строке записано единственное число n(1 ≤ n ≤ 1000) — количество планет.
В следующих n строках записано через пробел четыре целых числа xi,yi,zi(|xi|, |yi|, |zi| ≤ 106) и ri(1 ≤ ri ≤ 106)
, где xi,yi,zi — координаты i-ой введённой планеты, а ri — её радиус.
Формат выходных данных
Выведите одно число - минимальный радиус черной дыры, которая может поглотить все планеты с точностью до 5 символов.
Утенок Даки решил открыть свою доставку товаров в родной галактике.
Для успешного запуска бизнеса необходимо привлечь клиентов.
Поэтому утенок решил сделать упор на скидки и качество услуг.
Даки закончил разработку программы лояльности и уверен,
что она поможет привлечь клиентов.
Но как бы не была привлекательна цена,
если скорость доставки будет плохой, то все клиенты уйдут.
Галактика утенка имеет множество планет, между которыми существуют специальный космические дороги,
позволяющие перемещаться по ним в обе стороны.
Как и по дорогам на планетах, в космосе преодоление дороги занимает некоторое время.
Но помимо обычных дорог, в галактике время от времени появляются “кротовые норы”
(англ. wormholes), каждая нора имеет свое сопротивление,
поэтому для её преодоления необходимо затратить какое-то время,
но их особенность заключается в том, что они позволяют переместиться
минуя космические дороги. Норы существуют очень долго, поэтому считается,
что они почти вечные.
Недавно ученые выяснили природы “кротовых нор” и научились предсказывать время
и место их появления, а так же время необходимое для её преодоления.
К сожалению, путешествовать по ним возможно только в одном направлении.
Даки решил вложиться в это исследование, благодаря чему получил ранний доступ к
системе предсказания появления нор. Поэтому утенок хочет использовать информацию о
новых норах, чтобы доставлять заказы быстрее конкурентов и тем самым
завоевать весь рынок космической доставки в галактике.
На данный момент у Даки имеется список всех планет в галактике и дорог соединяющих
эти планеты, а так же время необходимое для перемещения по ним.
Помимо такой общеизвестной информации, система предсказаний
предоставляет информацию о появлении “кротовых нор”,
которая содержит в себе планеты соединенные этой норой,
время необходимое для перемещения с ее помощью и когда появится нора.
Формат входных данных
Первая строка содержит 3 целых числа:
N, A, B – количество планет, планету с которой выполняется доставка и планету-цель,
соответственно.
Далее следует строка с 2 целыми числами:
M – количество кротовых нор и K – количество обычных путей.
Последующие M строк содержат 4 целых числа: Ai, Bi – две планеты,
между которыми появляется нора, ti – время её появления и dti – время необходимое
для перемещения по ней из Ai в Bi.
Далее идут K строк в таком формате:
Aj, Bj, tj – две планеты и время пути между ними.
Считаем, что изначально время равно 0. Все планеты нумеруются от 1 до N включительно.
Обычные дороги существуют в любое время.
Формат выходных данных
Выведите единственное число – самое раннее время в которое заказ
будет доставлен к планете B. Если доставить заказ невозможно, выведите − 1
У нас есть квадрат 3×3, заполненный числами. А вам нужно вычислить ближайший к нему магический квадрат.
Дистанция между квадратами вычисляется, как сумма модулей разниц между соответствующими клетками квадратов.
Пусть первый квадрат - это F, второй - S, тогда дистанцией будет ∑|F[y][x] − S[y][x]|.
А под магическим квадратом мы понимаем любой квадрат 3×3, заполненный 9 различными последовательными числами таким образом, что сумма чисел в каждой строке, каждом столбце и на обеих диагоналях была одинакова
Пример квадратов:
35791113151719 - не является магическим квадратом, так как числа не образуют единую последовательность.
294753618 - удовлетворяет всем условиям. Числа можно собрать в последовательность: 1,2,...,9
Формат входных данных
На вход программе подаётся три строки, каждая из которых содержит по три числа ai.
Формат выходных данных
В первой строке вывести разницу между квадратами.
А в следующих трёх - сам получившийся магический квадрат.
Если существует несколько квадратов с одинаковой разницей, то вывести любой.
На городской трассе сломались некоторые участки дороги. И для ремонта этой дороги необходимо знать где же она сломалась. Однако ремонтники ребята хитрые и хотели обманом получить больше денег за меньшую работу.
У них возник план: докладывать администрации об участках починенной дороги, несмотря на то, что некоторые участки они учитывают несколько раз.
К сожалению или к счастью, администрация раскрыла этот план, и хочет наказать их таким же способом.
Администрация смотрит все возможные пары докладов и штрафует на рубль за каждый метр пересечения. Вычислите сумму получившегося штрафа.
Так как ответ может получиться довольно большим, выведите его по модулю 109 + 7.
Формат входных данных
В первой строке на вход даётся целое число n - количество докладов
В следующих n строках находятся два целых числа ai и bi - концы участка.
Формат выходных данных
Выведите единственное целое число — сумму получившегося штрафа по модулю 109 + 7.
Некий воитель с копьём на лошади, известный как Лансьер,
должен пройти путь от стартовой позиции до конечной на шахматной доске.
Лансьер может двигаться двумя способами:
Как обычный конь, с шагами в форме буквы "Г" и возможностью перепрыгивать другие фигуры.
Как ладья, с шагами по вертикали или горизонтали на любое количество клеток, но без возможности перепрыгивать другие фигуры.
Изображение ниже показывает, каким образом передвигается шахматный конь:
Шахматная доска представляет собой матрицу n ⋅ n, где "." обозначает свободную клетку, а "#" - занятую какой-либо фигурой.
Стартовая позиция Лансьера обозначена символом "L", конечная - символом "F".
Определите, сможет ли Лансьер добраться до требуемой позиции, и если да, то выведите минимальное количество ходов, которые ему необходимо совершить,
а если нет, выведите -1.
Формат входных данных
В первой строке вводится единственное число n(2 ≤ n ≤ 1000) - размерность шахматной доски
В следующих n строках вводится n символов "." или "#", обозначающие свободные или занятые клетки,
а также символы "L" и "F" обозначающие начальную и конечную позицию Лансьера. Задачей гарантируется,
что обязательно существует ровно одна начальная и одна конечная позиция.
Формат выходных данных
Выведите одно число - минимальное возможное количество ходов Лансьера из начальной позиции в конечную,
а если невозможно достигнуть конечной позиции - выведите -1
Мальчику Мише подарили колоду, содержащую n карт. На каждой карте записано некоторое натуральное число ai. После перетасовки их, он разложил карты на столе в линию.
Он решил, что линия карт является монотонной, если существует такое i, выбрав которое все карты от 1 до i являются одной четностью, а от i + 1 до n другой. При этом допускается ситуация, когда на столе только одна четность. Например, линии из карт [2, 4, 3, 1, 5]; [3, 9, 13, 21, 4]; [2, 4, 6, 8, 10] являются монотонными, а линия [2, 3, 4, 5, 6] нет.
Он хочет убрать несколько (возможно, ноль) карт со стола, чтобы линия стала монотонной. Но он хочет оставить максимально длинную линию, поэтому он уберет минимальное количество карт. Сам Миша хоть и любит карты, но не любит ничего вычислять, поэтому он просит Вас написать программу, которая рассчитает, какое минимальное количество карт ему надо убрать со стола, чтобы получилась монотонная последовательность.
Формат входных данных
В первой строке задано натуральное число n — количество карт в колоде.
В следующей строке записано n натуральных чисел ai — последовательно расположенные карты на столе.
Формат выходных данных
Выведите одно целое число — минимальное количество карт, которое необходимо убрать из колоды.
Ограничения
1 ≤ n ≤ 105
1 ≤ ai ≤ 109
Пояснение к примеру
В первом примере мы можем убрать число 2, тем самым сделаем слева [4], а справа [3, 5, 9]
Во втором примере мы можем убрать числа 7 и 8, тем самым сделаем слева [4, 6, 2], а справа [5, 3]
Это интерактивная задача.
Параллельно с выполнением вашего решения жюри запускает проверяющую программу,
с которой вы обмениваетесь сообщениями через стандартный ввод и вывод.
Подробнее о протоколе взаимодействия написано ниже.
Также в конце условия вы можете посмотреть корректные примеры взаимодействия с
проверяющей программой на разных языках программирования.
Илья собирает коллекцию фантиков от конфет.
Каждый фантик он кладет в альбом,
причем все фантики он складывает в порядке возрастания их
размеров (размер указан на каждом фантике).
Каждый день он пополняет свою коллекцию одним новым фантиком.
В начале каждого дня он дает вам фантик и просит помочь ему определить
перед каким БОЛЬШИМ СПРАВА в альбоме фантиком ему необходимо
поставить новый. Если такого фантика не существует или если фантик
с таким размером уже имеется в коллекции, вам необходимо вывести NO.
Формат входных данных
При запуске решения на вход в первой строке подаются целые числа n и k - количество уже имеющихся фантиков
и количество дней. (1 ≤ n ≤ 2 ⋅ 105, 1 ≤ k ≤ 105)
Во второй строке подается n целых чисел - ai
коллекция фантиков в порядке возрастания, которая может содержать повторяющиеся
размеры фантиков. (1 ≤ ai ≤ 2 ⋅ 105)
Далее ввод и вывод будут чередоваться. Илья k раз будет давать вам фантик,
то есть одно целое число bi - его размер, а вам надо будет после каждого раза ответить
перед каким фантиком надо расположить текущий. (1 ≤ bi ≤ 109)
Формат выходных данных
Каждый вопрос и вывод ответа должен заканчиваться символом перевода строки \n,
а также необходимо выполнить сброс буфера:
На шахматном поле расположились черные Кони. Сейчас ход черных. Вам надо определить, существует ли безопасное для белого Короля место.
Место считается безопасным, если ни один черный Конь на этом ходу не бьет Короля, расположенного в этом месте.
Короля можно расположить на любую свободную клетку.
Конь умеет перепрыгивать через другие фигуры. Изображение ниже показывает, каким образом передвигается шахматный конь:
Формат входных данных
Первая строка входных данных содержит одно целое число t(1 ≤ t ≤ 100) — количество наборов входных данных.
Для каждого набора входных данных дается матрица 8 ⋅ 8, где "." - пустое место, "#" - Конь.
Формат выходных данных
Для каждого набора входных данных в отдельной строке выведите:
В маленькой IT компании сейчас ведётся проект, который нужно закрыть в кратчайшие сроки.
Для этого были привлечены два специалиста: один занимается кодированием, а второй — развертыванием.
Чтобы закрыть проект, нужно разработать и развернуть на сервере N фичей,
у каждой фичи есть два времени:
время, необходимое для кодирования и время,
необходимое для развертывания.
Каждый специалист может работать только с одной фичей в один момент времени.
Также, специалист не может перейти к следующей фиче, не закончив работу с текущей.
Разработка фичи обязательно должна начинаться с кодирования, и только после того, как фича была закодирована, её можно начинать развёртывать.
Чтобы закрыть проект в кратчайшие сроки нужно распределить разработку и развёртывание фич оптимальным способом.
Напишите программу, которая найдет оптимальный порядок обработки фич и выведет минимальное время.
Формат входных данных
В первой строке записано целое число N(1 ≤ N ≤ 105) — количество фич.
Следующие N строк содержат описание фич.
Каждая строка содержит два целых числа t1 и t2(1 ≤ t1, t2 ≤ 109) —
время, необходимое на кодирование и развертывание фичи соответственно.
Формат выходных данных
В первой строке выведите минимальное время, необходимое для обработки всех фич.
В мире монстра Василия вся пища представляет из себя строки, которые состоят из символов.
У каждого символа есть свое целое число - сытность.
А сытностью строки называется сумма сытностей её символов.
Сегодня у монстра на обед строка s длины n.
Василий достаточно странное существо, поэтому в еде у него есть несколько правил:
Живот Василия не резиновый, поэтому съесть он может строку, длинной не более чем k символов.
Он начинает есть только один раз, и только подряд идущие символы.
Василий очень привередлив и не будет есть два одинаковых подряд идущих символа.
То есть если он съел символ и далее увидел следующий такой же символ, он сразу же прекращает есть.
Василий просит вас найти строку с максимальной сытность, которую он бы мог съесть.
Формат входных данных
В первой строке целое число M - размер алфавита,
алфавит может состоять только из цифр и строчных и заглавных латинских букв.
В следующих М строках располагаются
символ si и целое число ai - его сытость (1 ≤ ai ≤ 100).
В следующей строке два целых числа
n и k(1 ≤ k ≤ n ≤ 106) - длина строки и размер живота Василия.
В последней строке строка s длины n.
Формат выходных данных
Вам необходимо вывести одно целое число - сытность найденной строки.
