Темы
Информатика(2656 задач)
--->
228 задач
<---
В первом классе Глеб увлекался шахматами. К тому моменту он знал только лишь как ходит пешка: она может бить по диагонали влево-вверх и вправо-вверх, и ходить на клетку вверх только если та клетка не занята другой фигурой. О том, что пешка может превращаться в ферзя Глеб не подозревает. Поэтому он придумал свой вариант шахмат.
Игра идёт на доске с N строками и M столбцами (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) по следующим правилам. В нижней строке, имеющей номер 1, стоят P белых пешек, белых фигур на доске больше нет. На остальной части доски стоят разные чёрные фигуры (их названия Глеб не знает). Ходят только белые, их цель — побить все чёрные фигуры.
Как и в настоящих шахматах, если пешка Глеба бьёт чёрную фигуру, то она становится на её место, а побитая фигура убирается с доски. Считается, что Глеб выиграл, если он сумел побить белыми пешками все чёрные фигуры, в противном случае он проиграл. Помогите ему по заданной конфигурации всех фигур определить, сможет ли он выиграть, и, в случае успеха, выведите правильную последовательность ходов белых пешек.
Сначала вводятся четыре целых числа N, M, P, K (1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 0 ≤ P ≤ M, 1 ≤ K ≤ 1000, K ≤ (M - 1)N). Далее записано P различных чисел — номера столбцов pj (1 ≤ pj ≤ M), в которых стоят белые пешки. Далее идут K различных пар целых чисел — координаты (строки и столбцы) чёрных фигур ri, ci (2 ≤ ri ≤ N, 1 ≤ ci ≤ M).
Если пешки не смогут съесть все фигуры, выведите единственное слово NO.
В противном случае в первую строку выведите YES, вторая строка должна содержать суммарное число перемещений C, последующие C строк — описание ходов пешек, по одному ходу на каждую строку. Каждый ход задаётся двумя координатами r, c пешки (номерами строки и столбца), которая будет ходить, и символом m, принимающем три значения: L, R, F — побить вперед и влево, побить вперед и вправо, сделать шаг вперед соответственно. Данные о ходе следует выводить разделёнными одним пробелом, сначала координаты, потом тип хода.
Если последовательностей ходов несколько, выведите любой из них. Обратите внимание, что минимизировать количество перемещений не требуется.
2 2 2 1 1 2 2 2
YES 1 1 1 R
3 3 2 2 1 3 3 1 3 3
NO
Вася идет из школы домой вдоль проспекта, по которому ходят трамваи. Мама считает, что ему после школы полезно дышать свежим воздухом, поэтому настаивает, чтобы не менее K метров он прошел пешком. Вася при этом хочет попасть домой как можно быстрее (обязательно выполнив требование мамы).
Вдоль проспекта расположено N трамвайных остановок, которые находятся в точках a1, a2, ..., aN (все координаты задаются в метрах). Школа находится около 1-й остановки, а дом — около остановки номер N. Мальчик идет пешком со скоростью v метров в минуту. Трамвай едет со скоростью w метров в минуту (временем стоянки трамвая на остановках пренебрежем). В нулевой момент времени и далее с интервалом T минут от первой остановки в сторону Васиного дома отправляются трамваи. Вася выходит из школы также в момент времени 0. Сесть в трамвай и выйти из него можно только на остановке. При этом, если Вася приходит на остановку раньше трамвая, на который хочет сесть, то ему придется подождать, пока тот не подъедет. Вася идет пешком и едет на трамвае только в направлении от школы к дому.
Напишите программу, которая определит, когда Вася сможет оказаться дома.
Сначала вводится число N — количество остановок (1 ≤ N ≤ 2000). Далее заданы координаты остановок a1, a2, ..., aN (0 ≤ a1 < a2 < ... < aN ≤ 109). Далее вводится интервал движения трамваев T (1 ≤ T ≤ 2000). Затем расстояние, не меньше которого Вася должен пройти пешком K (0 ≤ K ≤ 2000). Затем заданы скорости Васи v и трамвая w (1 ≤ v ≤ w ≤ 10 000). Все вводимые числа целые. K не превышает длины пути от школы до дома.
В первую строку выведите не менее чем с пятью знаками после десятичной точки одно число — минимальное время, когда Вася сможет оказаться дома, пройдя пешком не менее K метров. Далее нужно вывести информацию о пути Васи. Занумеруем промежутки между соседними остановками числами от 1 до N - 1 (то есть промежуток между первой и второй остановками имеет номер 1, между второй и третьей — 2 и так далее). Следующая строка должна содержать количество промежутков, пройденных Васей пешком. Далее выведите номера этих промежутков в возрастающем порядке.
3 0 10 30 5 10 1 5
16.000000 1 1
4 0 3 8 11 1 6 1 3
7.666667 2 1 3
Каждый раз, когда в мире происходит значимое событие, наша реальность разветвляется на несколько — в зависимости от исхода этого события. После этого существует уже не только наша основная реальность, но и ответвившиеся от неё в моменты появления разных исходов.
Однажды один архимаг решил сделать мир лучше. Такая грандиозная задача не под силу одному архимагу, поэтому он решил найти самого себя ещё в K реальностях и выполнить эту задачу вместе. Проведённое теоретическое исследование показало, что, кроме реальности, в которой находится именно он, существует ещё N - 1 реальностей. Для удобства они были занумерованы числами от 1 до N, при этом его собственная реальность имеет номер 1, а посетить ему необходимо реальности с номерами 2, 3, ..., K + 1.
Как уже говорилось, каждая реальность когда-то ответвилась от некоторой другой, за исключением одной Начальной реальности, которая существовала всегда (её номер может оказаться каким угодно; считается, что она появилась в момент времени 0). Исследование показало, что реальность с номером i ответвилась от реальности с номером Pi в момент времени Ti. Из каждой реальности с номером i архимаг может переместиться
Требуется найти минимальное количество энергии, которое потребуется архимагу, чтобы, начав в реальности с номером 1, посетить все реальности с номерами от 2 до K + 1 (в любом порядке) и затем вновь вернуться в 1. Любую реальность при этом разрешается посещать сколько угодно раз.
Сначала вводятся два целых числа N и K (0 ≤ K < N ≤ 100 000): количество доступных реальностей и количество реальностей, которые необходимо посетить. Далее идёт N пар целых чисел, i-я пара — это Pi и Ti (1 ≤ Pi ≤ N, 0 ≤ Ti ≤ 106; для Начальной реальности Pi = Ti = 0).
Гарантируется, что ответвившаяся реальность появилась строго позже породившей (Ti > TPi), и что маг может при желании добраться до любой из N реальностей.
Выведите единственное число E — минимальную возможную энергию, которая потребуется архимагу для путешествия.
5 2 4 2 4 6 1 9 0 0 1 7
30
На День учителя Вася решил купить букет цветов. В магазине продаются ромашки по A рублей за штуку и гладиолусы по B рублей за штуку (A < B). У Васи есть C рублей. Он хочет составить букет из максимально возможного количества цветов, и при этом потратить как можно больше денег. Другими словами, из всех букетов с максимально возможным количеством цветов он хочет выбрать самый дорогой, но не дороже C рублей. Помогите ему вычислить стоимость такого букета.
Вводятся три целых числа A, B, C (1 ≤ A < B ≤ 100, 0 ≤ C ≤ 1000).
Выведите одно число — стоимость самого дорогого букета из максимального количества цветов.
В первом тесте искомый букет состоит из четырёх ромашек и одного гладиолуса. Во втором — только из трёх ромашек.
2 3 11
11
3 5 10
9
Компания из M человек пришла в пиццерию. Посовещавшись, они решили заказать одну большую пиццу с K начинками. Пицца представляет собой круг, поделённый на K равных секторов, в каждом из которых находится своя начинка. Пиццу подают ещё не разрезанной.
Друзья попросили официанта разрезать пиццу на M равных секторов, по одному куску на человека, так, чтобы как можно большему количеству людей достался кусок по крайней мере с двумя начинками.
Помогите официану определить, какому именно количеству людей достанется больше одной начинки, если резать пиццу наиболее оптимально.
Вводятся два целых числа K, M (1 ≤ K ≤ 100, 1 ≤ M ≤ 100) — количество начинок в пицце и количество человек в компании соответственно.
Выведите количество человек, которым достанется более одной начинки в наилучшем случае.
В первом тесте каждому достанется по две начинки, если резать как угодно, но не по границам секторов с начинками.
Во втором тесте не важно как резать: в любом случае обоим достанется по половине пиццы, в каждой из которых будет больше одной начинки.
3 3
3
3 2
2