Василий возводит башню. На построение одного этажа уходит килограмм железа и килограмм дерева. Килограмм железа стоит $$$X$$$ рублей, а килограмм дерева $$$Y$$$ рублей. Вася хочет знать максимальное количество этажей башни, которое он сможет построить, если у него есть $$$N$$$ рублей на покупку материалов.
В первой строке содержится целое число $$$N$$$ — бюджет Васи на покупку железа и дерева $$$(1\leq N\leq 10^9)$$$.
Во второй строке содержится целое число $$$X$$$ — стоимость килограмма железа $$$(1\leq X\leq 10^9)$$$.
В третьей строке содержится целое число $$$Y$$$ — стоимость килограмма дерева $$$(1\leq Y\leq 10^9)$$$.
В единственной строке выведите одно число — максимальное количество этажей, которое сможет построить Василий.
3 2 1
1
5 1 10
0
В УрФУ проводится турнир по игре Камень-ножницы-бумага-ящерица-Спок. Вас назначили судьей. В игре участвуют 2 человека. Каждый из них может в качестве своего хода выбрать один из пяти вариантов:
- Камень (Rock)
- Ножницы (Scissors)
- Бумага (Paper)
- Ящерица (Lizard)
- Спок (Spock)
- Ножницы режут бумагу
- Бумага заворачивает камень
- Камень давит ящерицу
- Ящерица травит Спока
- Спок ломает ножницы
- Ножницы отрезают голову ящерице
- Ящерица ест бумагу
- Бумага содержит улики против Спока
- Спок испаряет камень
- Камень затупляет ножницы
Для наглядности посмотрите на схему ниже. Стрелки на ней идут от побеждающих к проигрывающим.
Даны ходы двух людей. Ваша задача — определить исход поединка.
В первой строке вводится ход первого игрока - это одно из пяти слов:
- Rock
- Scissors
- Paper
- Lizard
- Spock
Если первый игрок победит второго, то выведите «First» (без кавычек).
Если второй игрок победит первого, то выведите «Second» (без кавычек).
Если же будет ничья, то выведите «Tie» (без кавычек).
Rock Paper
Second
Rock Rock
Tie
Lizard Spock
First
Артем не поступил в университет, так что ему пришлось отправиться в армию. Для обучения новобранцев выделили три танка с номерами от 1 до 3. Изначально команде Артема поручили управлять $$$k$$$-ым танком. Но сегодня вышло $$$n$$$ приказов. В каждом приказе написаны числа $$$a_i$$$ и $$$b_i$$$, это означает, что команды, управляющие танками с номерами $$$a_i$$$ и $$$b_i$$$ должны поменяться танками. Приказы выполняются поочередно в порядке от первого к последнему. В каком танке после выполнения всех приказов будет сидеть Артем?
В первой строке через пробел вводятся целые числа $$$n, k$$$ — количество приказов и начальный танк Артема $$$(1\leq n\leq 10^5, 1\leq k\leq 3)$$$.
В $$$i$$$-й из следующих $$$n$$$ строк содержатся два целых числа $$$a_i, b_i$$$ — содержание $$$i$$$-го приказа $$$(1\leq a_i, b_i\leq 3, a_i \neq b_i)$$$.
Выведите единственное число — номер танка, в котором будет находится Артем после $$$n$$$ выполнения приказов.
2 1 1 2 2 3
3
В примере изначально Артем находится в первом танке. После выполнения первого приказа, команды на первом и втором танках меняются местами. Теперь Артем находится во втором танке. После выполнения второго приказа, команды второго и третьего танков меняются местами, Артем переходит со второго танка на третий. Поэтому правильный ответ — 3.
Дима выучил ленивое дерево отрезков, он был восхищен идеей отложенных операций, которая там используется. Он решил использовать эту тактику для решения домашних работ в течение $$$n$$$ дней. У Димы в вузе есть $$$k$$$ разных предметов, пронумерованных от 1 до $$$k$$$. В каждый из $$$n$$$ дней ему приходит задание по одному из этих предметов. То есть в $$$i$$$-ый день он получает задание $$$a_i$$$, где $$$a_i$$$ - номер предмета по которому пришло задание в $$$i$$$-ый день
Дима может провести свой день двумя способами. Он может сделать все накопившиеся домашние работы по одному из $$$k$$$ предметов или не делать ничего.
Помогите Диме составить план выполнения домашних заданий таким образом, чтобы он был занят домашней работой минимально возможное число дней, и при этом к концу $$$n$$$ дней все выданные домашние задания были выполнены.
В первой строке через пробел вводятся целые числа $$$n$$$ и $$$k$$$ — количество дней и количество различных предметов $$$(1\leq n, k\leq 10^5)$$$.
Во второй строке дано $$$n$$$ чисел, разделённых пробелами, где $$$i$$$-е число равно $$$a_i$$$ — номеру предмета, по которому дано задание в $$$i$$$-ый день $$$(1\leq a_i\leq k)$$$. Возможна ситуация, когда задания по некоторым предметам не выдаются Диме ни разу.
В единственной строке выведите $$$n$$$ чисел, разделённых пробелами, где $$$i$$$-е число должно быть равно 0, если Дима должен бездельничать в $$$i$$$-й день, либо номеру предмета, если Диме стоит выполнить все домашние задания по данному предмету в этот день. Если существует несколько возможных вариантов ответа, выведите любой.
3 3 1 2 3
1 2 3
4 2 1 1 1 1
0 0 0 1
В первом примере Диме каждый день дают задание по новому предмету, поэтому он вынужден каждый день выполнять новое домашнее задание.
Во втором примере Диме четыре дня подряд дают задание типа по предмету номер $$$1$$$, поэтому он может выполнить их все в последний день. В таком случае он сможет бездельничать целых три дня.
После квалификационного тура довольные, но голодные программисты зашли в ресторан «Уральские блинчики» и заказали себе несколько фирменных блинчиков. Для того чтобы приготовить блинчик, повар должен прожарить каждую из его сторон на сковороде.
Фирменный блинчик имеет форму квадрата со стороной $$$1$$$. Сковорода повара имеет форму прямоугольника ширины $$$m$$$ и высоты $$$n$$$. Она разбита на $$$n \cdot m$$$ клеток. К сожалению, некоторые из клеток подгорели, и в них нельзя класть блинчики. При этом не подгоревшие клетки образуют связную область, то есть из любой не подгоревшей клетки можно попасть в любую другую, перемещаясь каждый раз в соседнюю неподгоревшую клетку. Соседними называются такие две клетки, что либо они находятся в одной и той же строке и в соседних столбцах, либо в одном и том же столбце и в соседних строках.
В некоторые из не подгоревших клеток повар положил блинчики (не более одного на клетку), и они уже поджарились с одной стороны. Теперь их нужно перевернуть на другую сторону. Для этого можно поддеть любой блинчик лопаткой снизу и перевернуть его, переместив при этом на соседнюю клетку. Перемещать блинчики за пределы сковороды нельзя. Естественно, если перевернуть блинчик дважды, он снова будет расположен прожаренной стороной вниз. Если переместить блинчик на клетку, где уже лежит другой блинчик, они образуют стопку. Одновременно на одной из клеток могут находится сколько угодно блинчиков, но переворачивать можно только верхний из них.
Сумеет ли повар добиться того, чтобы каждый блинчик лежал прожаренной стороной вверх, и на каждой клетке лежало не более одного блинчика? При этом нельзя перемещать блинчики на подгоревшие клетки, даже временно.
В первой строке через пробел даны целые числа $$$n$$$ и $$$m$$$ — размер сковороды ($$$1 \le n, m \le 100$$$).
Далее даны $$$n$$$ строк длины $$$m$$$ каждая, описывающих сковороду. Строки состоят из символов «.» (код $$$46$$$), «#» (код $$$35$$$) и «P» (код $$$80$$$). Символ «.» обозначает, что клетка свободна; символ «#» обозначает, что клетка подгоревшая; символ «P» обозначает, что клетка занята блинчиком.
Гарантируется, что на сковороде есть хотя бы один блинчик, и что не подгоревшие клетки образуют связную область.
Если повар сможет перевернуть все блинчики на неподжаренную сторону, следуя условиям задачи, в единственной строке выведите «YES» (без кавычек). Иначе, выведите «NO» (без кавычек).
1 3 P.P
NO
2 2 PP PP
YES
2 2 PP P#
NO
Валя учится в школе в четвёртом классе. Все эти годы он составлял оптимальный маршрут от дома до здания школы. Эту задачу осложняет то, что время ходьбы по одному и тому же маршруту не всегда одинаковое: оно зависит от того, как долго придётся стоять на светофорах. Чтобы не стоять слишком долго, выгодно переходить на перекрёстках, где зелёный свет горит то в одном, то в другом направлении. Стоя на таком перекрёстке Валя и придумал эту задачу.
Представьте, что вы стоите на перекрёстке, и в обе стороны горит красный свет. На всех светофорах стоит счётчик, показывающий, сколько секунд осталось ждать. В одну сторону счётчик показывает $$$A$$$ секунд, в другую — $$$B$$$ секунд. Каждую секунду числа на обоих счётчиках одновременно уменьшаются на $$$1$$$. Как только один из счётчиков достигнет нуля, загорится зелёный свет.
Пока ещё горит красный, интересны все такие моменты, когда числа на счётчиках будут различаться в целое число раз, то есть когда их частное — целое число. Посчитайте, сколько раз такое случится.
В единственной строке через пробел вводятся целые числа $$$A$$$ и $$$B$$$ — числа на первом и втором счётчиках соответственно ($$$1 \le A, B \le 10^9$$$).
В единственной строке выведите одно целое число — количество раз, когда числа на счётчиках будут различаться в целое число раз до того, как один из них достигнет нуля.
3 30
2
16 4
4
Вам дан текст. Текст — это строка, состоящая из строчных латинских букв и пробелов, завершающаяся точкой. Словом называется непустая строка, состоящая из строчных латинских букв, такая, что перед первой буквой слова находится начало текста или пробел, а после последней буквы слова находится точка или пробел. Гарантируется, что между каждой парой соседних слов стоит ровно один пробел. Гарантируется, что точка в тексте содержится ровно одна. Она следует строго за последним словом. Пробела между последним словом и точкой быть не может. Гарантируется, что в тексте есть по крайней мере одно слово.
В тексте авторы переставили некоторые буквы внутри слов местами, при этом не изменяя первую и последнюю букву слов. У вас имеется словарь всех возможных слов, которые могли встречаться в тексте до того, как буквы были переставлены. Никакие другие слова не могли встречаться в исходном тексте. Ваша задача — написать программу, которая сможет восстановить исходный текст (то, каким он был до перестановки букв).
В первой строке вводится текст, полученный после некоторой перестановки символов некоторых слов. Гарантируется, что суммарная длина текста не превышает $$$5\cdot 10^5$$$ символов.
В следующей строке вводится целое число $$$n$$$ — количество слов в словаре $$$(1\leq n\leq 5\cdot 10^5)$$$.
Каждая из следующих $$$n$$$ строк содержит одно слово из словаря. Гарантируется, что суммарная длина всех слов в словаре не превышает $$$5\cdot 10^5$$$ символов. Также гарантируется, что все слова в словаре различны.
Выведите единственную строку — исходный текст до перестановки символов. Если существует несколько возможных вариантов ответа, выведите любой из них. Если не существует ни одного корректного варианта ответа, выведите «No solution» (без кавычек).
hello wolrd. 2 hello world
hello world.
hello wlrd. 2 hello world
No solution
tihs is vrey sceret txet. 7 text secret serect scret is very this
this is very secret text.
«Катамари» — это магический шар, к которому прилипает всё, что его касается. Он катится по Земле, собирая всё большие и большие объекты, пока не вырастет достаточно громадным, чтобы стать новым небесным телом.
В этот раз катамари занесло на прямоугольное клетчатое поле размера $$$n$$$ строк на $$$m$$$ столбцов. Будем говорить, что клетка, находящаяся в строке $$$i$$$ в столбце $$$j$$$, имеет координаты $$$(i, j)$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$). В каждой клетке расположен какой-нибудь объект. Размер объекта, находящегося в клетке с координатами $$$(i, j)$$$, равен $$$a_{ij}$$$. При этом мир настолько разнообразен, что для любого числа существует не более трёх объектов такого размера.
Ваша задача — прицепить все объекты, перекатывая катамари по полю. Начать можно в любой клетке. Две клетки называются соседними, если номера их столбцов совпадают, а номера строк отличаются на единицу, либо если номера их строк совпадают, а номера столбцов отличаются на единицу. Перемещаться из клетки можно только в соседнюю клетку, выходить за пределы поля нельзя. При этом одну клетку нельзя посещать дважды.
Необходимо также выполнить следующее ограничение: размеры объектов, прицепленные к катамари, должны нестрого возрастать. Иными словами, для любых двух объектов разного веса, меньший из них должен быть приклеен раньше, чем больший.
Составьте такой маршрут для катамари, чтобы каждый объект был собран, и все ограничения были выполнены.
В первой строке через пробел вводятся два целых числа $$$n$$$ и $$$m$$$ — размеры поля ($$$1 \leq n, m \leq 100$$$).
Следующие $$$n$$$ строк описывают поле. В каждой из них содержится $$$m$$$ целых чисел $$$a_{ij}$$$, разделённых пробелом ($$$1 \leq a_{ij} \leq 10^4$$$) — размеры объектов в соответствующих клетках.
Гарантируется, что для любого числа существует не более трёх объектов такого размера.
Если составить требуемый маршрут невозможно, в единственной строке выведите $$$-1$$$.
Иначе, выведите $$$n \cdot m$$$ строк. В $$$k$$$-й строке через пробел выведите два числа $$$i_k$$$ и $$$j_k$$$ — координаты $$$k$$$-й клетки маршрута. Маршрут должен обходить всё поле, не посещая одну клетку дважды, а размеры объектов в порядке обхода должны составлять неубывающую последовательность. Если возможных ответов несколько, выведите любой из них.
2 4 1 4 8 16 2 4 16 16
1 1 2 1 2 2 1 2 1 3 1 4 2 4 2 3
3 3 1 2 2 1 2 3 1 3 3
-1
На соревнованиях по программированию не раз встречались задачи про Малыша и Карлсона, делящих между собой сладости. Чтобы не повторяться, каждый автор задачи хочет добавить в своё условие изюминку, которая бы выделила задачу на фоне остальных. То Малыш и Карлсон делят многослойный торт, то они играют в игру на плитке шоколада. Дошла очередь и до самих героев: какую задачу можно придумать, если бы Малыш и Карлсон жили в параллельной вселенной?
Малыш и Карлсон из параллельной вселенной — образованные и воспитанные люди. Они не страдают от лишнего веса, и каждый из них готов отдать другу половину всех сладостей. Сегодня они выиграли в командном соревновании по программированию большой торт (в параллельной вселенной команды состоят из двух человек). Торт имеет форму выпуклого $$$N$$$-угольника. Малыш и Карлсон тут же решили поделить его на две равные по площади части, причём сделать это надо с математической точностью.
Для этого они ввели декартову систему координат и измерили координаты вершин торта. Все координаты оказались целыми числами. Осталось провести прямолинейный разрез. Чтобы не допустить даже малейшей погрешности, было принято решение выбрать две точки $$$A$$$ и $$$B$$$ с целочисленными координатами и сделать разрез по прямой, проходящий через эти две точки.
После долгого соревнования Малыш и Карлсон устали, поэтому они обратились к своим братьям и сёстрам из параллельной вселенной за помощью. Найдите две различные точки $$$A$$$ и $$$B$$$, чтобы прямая, проходящая через них, разделила торт на две равные по площади части. Координаты точек должны быть целыми числами, не превышающими $$$10^{18}$$$ по модулю.
В первой строке находится целое число $$$N$$$ — количество вершин многоугольника ($$$3 \leq N \leq 10^3$$$).
В следующих $$$N$$$ строках через пробел записаны целые числа $$$x_i$$$ и $$$y_i$$$ — координаты $$$i$$$-й вершины многоугольника ($$$-10^5 \leq x_i, y_i \leq 10^5$$$).
Гарантируется, что вершины задают выпуклый многоугольник в порядке обхода против часовой стрелки, никакие две точки не совпадают и никакие три точки не лежат на одной прямой.
Если решения не существует, в единственной строке выведите $$$-1$$$.
Иначе, выведите две строки. В первой строке через пробел выведите целые числа $$$x_a$$$ и $$$y_a$$$ — координаты точки $$$A$$$ ($$$-10^{18} \le x_a, y_a \le 10^{18}$$$). Во второй строке в аналогичном формате выведите координаты точки $$$B$$$. Точки не должны совпадать.
4 0 3 3 0 3 6 0 7
-1 4 4 4