Сегодня на паре Евгений узнал о новом для себя множестве чисел – комплексных числах.
Для начала он узнал о том, что такое мнимая единица. Мнимой единицей называют такое число $$$i$$$, что $$$i^2 = -1$$$.
Комплексным числом называют число вида $$$a + i \cdot b$$$, где $$$a$$$ и $$$b$$$ – действительные числа, $$$i$$$ – мнимая единица. Число $$$a$$$ называют действительной частью комплексного числа, $$$b$$$ – мнимой его частью.
Для удобства преподаватель сегодня использовал только те комплексные числа, у которых действительная и мнимая часть являются целыми числами. Евгений научился складывать комплексные числа, ведь что может быть проще: результатом суммы чисел $$$a + i \cdot b$$$ и $$$c + i \cdot d$$$ будет новое число, действительная часть которого равна $$$a + c$$$, а мнимая равна $$$b + d$$$, то есть $$$$$$(a + i \cdot b) + (c + i \cdot d) = (a + c) + i \cdot (b + d).$$$$$$
Однако посчитать действительную и мнимую части произведения двух комплексных чисел Евгений не смог. Помогите Евгению – напишите программу, которая будет находить действительную и мнимую части произведения двух заданных комплексных чисел.
В единственной строке содержатся числа $$$a, b, c, d$$$ $$$(-1000 \le a, b, c, d \le 1000)$$$, разделенные пробелом, описывающие два комплексных числа $$$a + i \cdot b$$$ и $$$c + i \cdot d$$$.
В единственной строке выведите два числа – действительную и мнимую части получившегося произведения.
2 1 3 6
0 15
2 -2 2 2
8 0
Закончив обучение в магистратуре и поступив в аспирантуру, Игорь не смог забросить олимпиады. Он решил вести тренировки по спортивному программированию в своём любимом вузе.
Игорю разрешили проводить тренировки по воскресеньям в новом кабинете. Чтобы организовать первую тренировку, Игорь сделал опрос в беседе 'кто придет на тренировку?' с двумя вариантами ответа: 'к $$$10$$$ часам', 'к $$$12$$$ часам', причём каждый участник мог выбрать оба варианта. По итогам опроса оказалось, что за $$$10$$$ часов было дано $$$A$$$ голосов, за $$$12$$$ часов $$$B$$$ голосов, посмотрев на таблицу ответов, Игорь увидел, что $$$C$$$ студентов проголосовало и за $$$10$$$, и за $$$12$$$ часов, поскольку они могут в любое время.
В любимом вузе Игоря строго-настрого соблюдаются санитарно-профилактические нормы, и на занятии не должно присутствовать больше, чем $$$D$$$ студентов в одном помещении.
Помогите Игорю определить, сможет ли он провести тренировку, если распределит студентов с учетом их пожеланий, или он не сможет разместить студентов в кабинете, и первую тренировку придется отменить.
На вход дано четыре целых числа $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$ $$$(0\leq A,B,C,D\leq 10^5, C\leq A \text{ и } C\leq B)$$$ — количество проголосовавших за $$$10$$$ часов, количество за $$$12$$$ часов, количество проголосовавших за $$$10$$$ и $$$12$$$ часов и то, сколько может находиться студентов в одном помещении одновременно.
Выведите 'Yes', если получится провести тренировку, и 'No', если провести тренировку нельзя.
15 15 10 20
Yes
15 15 10 10
Yes
15 15 10 9
No
Антон недавно поступил в университет, и многое для него в новинку. Так, например, сегодня на программировании он изучал битовые операции, в частности, операцию побитового исключающего «или» двух чисел (xor). Данная операция существует во всех современных языках программирования, например, в языках $$$C\!+\!+$$$, $$$Python$$$ и $$$Java$$$ она обозначена как «$$$ ^\wedge $$$», в $$$Pascal$$$ – как «xor». Пример применения операции «xor»: $$$10101_2 \oplus 10001_2 = 00100_2$$$. Можно заметить, что «xor» аналогичен сложению соответствующих битов чисел по модулю 2. У Антона есть два $$$N-$$$значных двоичных числа (возможно, содержащие лидирующие нули). Помогите ему найти результат побитового исключающего «или» двух этих чисел, отбросив лидирующие нули.
В первой строке содержится число $$$N$$$ $$$(1 \le N \le 10^5)$$$ – количество цифр в каждом из чисел.
Во второй строке содержится первое двоичное число.
В третьей строке содержится второе двоичное число.
В единственной строке выведите двоичное число – результат исключающего «или» без лидирующих нулей.
2 11 10
1
4 0011 1100
1111
В первом примере $$$11_2 \oplus 10_2 = 01_2 = 1_2$$$.
Владислав работает в компании «Сулец Компани», которая занимается обработкой текстов. Сегодня он получил задание – реализовать обработчик латинского текста, который бы преобразовывал его в текст, написанный шрифтом Брайля.
Буквы и знаки препинания в шрифте Брайля кодируются с помощью последовательностей из 6 точек. Ниже приведены аналоги символов, использующихся в данной задаче. Пробелу соответствуют 6 белых точек.
Помогите Владиславу – напишите программу, которая будет переводить текст, состоящий из строчных латинских букв, некоторых знаков препинания и пробелов, в шрифт Брайля.
В единственной строке содержится текст, состоящий из строчных латинских букв, пробелов и знаков препинания (точка, запятая, восклицательный и вопросительный знаки). Длина текста не превосходит $$$10^5$$$. Гарантируется, что в строке встретятся только символы, указанные в условии задачи.
Выведите три строки – исходный текст, закодированный шрифтом Брайля. Чёрные точки следует выводить как «.», белые точки – как «*».
acm icpc!
.*....***.......** ********.***.***.. ****.*******.***.*
Игорь закончил магистратуру и решил подать документы в аспирантуру в свой любимый вуз, чтобы стать классным молодым учёным.
Всего в вузе есть $$$n$$$ бюджетных мест в аспирантуре. Вуз отбирает только лучших из лучших студентов, учитывая их достижениям за время обучения. При подаче документов учитываются все грамоты, публикации и гранты студента. Если в результате учета достижений, у студентов окажется равное количество баллов, тогда этим студентам придется написать вступительные экзамены, чтобы поступить на бюджет.
Эта новость очень обрадовала Игоря, ведь у Игоря было накоплено много грамот, он участвовал в олимпиадах и писал небольшие статьи в сборники. Собрав все свои достижения и посчитав свои баллы (их получилось $$$k$$$), Игорь подал документы. Теперь он ждет не дождется рейтинговых таблиц.
Вам предстоит определить судьбу Игоря, если Игорь поступает без вступительных экзаменов, выведите 'enter', если Игорю придется сдавать вступительный экзамен, выведите 'entrance exams', иначе выведите 'no chance'.
В первой строке записано два целых числа: $$$n$$$ $$$(1\leq n\leq 10^5)$$$ — количество бюджетных мест, и $$$k$$$ $$$(0\leq k\leq 10^9)$$$ — количество баллов Игоря.
Во второй строке записано целое число $$$m$$$ ($$$1\leq m\leq 10^5$$$) — количество других абитуриентов.
В третьей строке записано $$$m$$$ целых чисел $$$k_i$$$ $$$(0\leq k_i\leq 10^9,1\leq i \leq m)$$$ — баллы за достижения других абитуриентов.
Выведите в единственной строке 'enter', если Игорь поступает без вступительных экзаменов, 'entrance exams', если Игорю придется сдавать вступительный экзамен, 'no chance', если Игорь не сможет поступить в аспирантуру.
6 50 9 10 20 30 40 50 60 70 80 90
enter
4 50 9 10 20 30 80 90 40 50 60 70
no chance
6 50 9 10 20 30 50 50 60 70 80 90
entrance exams
Игорь и Ира решили поехать на дачу, ведь там куча дел: прополоть и полить грядки, собрать урожай, окучить картошку и много-много всего.
Приехав на свой участок, они увидели, что их плохой сосед Т. передвинул забор и забрал кусок земли в виде треугольника. Игорь был возмущен данным событием и записал координаты вершин этого треугольника. Помогите Игорю посчитать площадь земли, которую захватил плохой сосед Т.
На вход дается три строки. В каждой строке записано 2 целых числа $$$x_i,y_i$$$ $$$(-10^5\leq x_i,y_i\leq 10^5)$$$ - координаты вершин треугольника. Гарантируется, что треугольник невырожденный.
Выведите одно вещественное число — площадь земли бессовестно занятой плохим соседом Т. с точностью до 6 знаков после запятой.
0 0 0 1 1 0
0.50000000
Игорь и Ира решили поехать на дачу, ведь там куча дел: прополоть и полить грядки, собрать урожай, окучить картошку, проверить сохранность забора и много-много всего.
На огороде у Игоря и Иры растет множество разных культур — $$$n$$$ штук. Пришло время уборки урожая. Игорь будет хранить урожай в одинаковых ящиках. Игорь посчитал, сколько получилось собрать килограмм каждой культуры - $$$a_i$$$. Кроме того в один ящик помещается $$$b_i$$$ килограмм каждой культуры.
Игорь не хочет складывать в один ящик разные овощи, ведь так не получится их сохранить за зиму. Помогите Игорю посчитать, сколько потребуется ящиков, чтобы сохранить весь урожай.
В первой строке задано одно целое число $$$n$$$ $$$(0\leq n\leq 10^5)$$$ — количество культур на огороде Игоря и Иры.
В каждой следующей строке записано два целых числа $$$a_i$$$ и $$$b_i$$$ $$$(1\leq a_i,b_i\leq 10^5)$$$ — количество урожая в килограммах $$$i$$$ культуры и то, сколько килограммов можно хранить в одном ящике.
Выведите одно целое число — количество ящиков, которое потребуется Игорю для хранения всего урожая.
3 10 2 20 4 40 3
24
6 7 10 1 8 6 3 3 6 1 6 1 1
7
После тяжёлого дня, выпив очередную кружку чая с валерианой, Дима Н. лёг спать. Ему снится сон: множество разноцветных прямых на ярко-чёрном фоне. Причём сон был вполне нормальным, никакие две прямые не совпадали.
На следующий день Дима пошёл к психиатру, а тот задал вполне корректный вопрос: какая прямая имеет минимальное количество пересечений с другими? Он не сумел найти ответ, и теперь его судьба печальна.
Не допустите его ошибку, найдите ответ заранее.
Первая строка содержит одно число N - количество прямых (1 ≤ N ≤ 105). Следующие N строк содержат целые числа А и B, задающие одну прямую уравнением y = A * x + B (-109 ≤ A, B ≤ 109).
Выведите одно число – количество пересечений у искомой прямой.
3
1 2
1 3
2 3
1
5
1 1
1 2
1 3
2 2
2 3
2
Дана последовательность, состоящая из символов двух типов. Эта последовательность должна быть преобразована в правильную скобочную последовательность путем последовательной замены всех символов по следующему правилу:
- выбираются два символа разного типа,
- символ, стоящий в последовательности левее, заменяется на открывающую скобку,
- символ, стоящий правее, — на закрывающую.
Определите количество способов осуществить такое преобразование. Способы, отличающиеся только последовательностью замен, считаются одинаковыми.
Правильной скобочной последовательностью называется строка, состоящая из символов '(' и ')', определяющаяся следующим образом:
- пустая строка является правильной скобочной последовательностью;
- если A – правильная скобочная последовательность, то строка (A) – также правильная скобочная последовательность;
- если A и B – правильные скобочные последовательности, то строки AB и BA также являются правильными скобочными последовательностями.
В единственной строке содержится непустая строка, состоящая из строчных букв «a», «b», длина которой от 1 до 100 букв включительно. Символ «a» обозначает символ первого типа, а символ «b» — символ второго типа.
Выведите в отдельной строке одно целое число — ответ на задачу.
aabb
1
Игорь и Ира решили поехать на дачу, ведь там куча дел: прополоть и полить грядки, собрать урожай, окучить картошку, проверить сохранность забора, уточнить наличие ящиков для хранения урожая и много-много всего.
Приехав на дачу, Игорь и Ира увидели, что никого из соседей не было. У Игоря и Иры все соседи на даче очень вежливые люди. Игорю стало интересно, кто из соседей уезжает с дачи каждый день, а кто остается ночевать. Для этого Игорь будет в течение дня записывать в блокнот следующие события:
- $$$+$$$ $$$k$$$ – сосед из домика под номером $$$k$$$ приехал на свою дачу.
- $$$-$$$ $$$k$$$ – сосед из домика под номером $$$k$$$ сел в машину и собирается уехать.
Дачные участки стоят вдоль узкой дороги и пронумерованы от $$$1$$$ до $$$N$$$. Когда соседи приезжают на дачу, они всегда хотят встать рядом со своим участком $$$k$$$, ведь так гораздо удобней. Они могут это сделать только в том случае, если перед участками с $$$1$$$-го по $$$k-1$$$-й не стоят машины. Если соседи не могут проехать к своему дому, тогда они оставляют свою машину на общей парковке перед дачами.
Если сосед хочет уехать и его машина стоит на парковке, то он без проблем садится в машину и уезжает, если сосед хочет уехать и его машина стоит рядом с его участком, тогда он садится в машину и уезжает только в том случае, если на дороге не стоят машины перед участками с $$$1$$$ по $$$k-1$$$, иначе он сидит и ждет, как вежливый сосед, пока не уедут все машины, которые мешают, если этого не получилось, то он остается на даче.
Соседи могут возвращаться и уезжать с дачи несколько раз.
Помогите Игорю – определите, кто из соседей в конце дня остался ночевать на даче, кто – уехал домой, а кто из соседей вообще не приезжал на дачу.
Первая строка содержит два целых числа $$$N$$$, $$$M$$$ ($$$1\leq N, M \leq 10^5$$$) – количество соседей и количество записей.
В следующих $$$M$$$ строках содержатся записи в блокноте Игоря:
$$$+$$$ $$$k$$$ $$$(1\leq k\leq N)$$$ – на дачу с номером $$$k$$$ приехал сосед.
$$$-$$$ $$$k$$$ $$$(1\leq k\leq N)$$$ – с дачи номер $$$k$$$ уезжает сосед.
Гарантируется, что перед операцией '+' соседа нет ни на участке, ни в машине рядом с участком.
Для каждого $$$i$$$ соседа выведите в $$$i$$$ строке 'YES' (без кавычек), если сосед смог уехать домой, 'NO' (без кавычек), если сосед не уехал и остался ночевать на даче, '-1' (без кавычек) если сосед не приезжал на дачу.
5 7 + 3 + 4 + 2 - 4 - 3 + 1 - 1
YES NO NO YES -1
Игорь закончил магистратуру, и, как порядочный студент, решил устроиться на работу по специальности в его любимом городе.
В любимом городе Игоря есть хорошие IT-компании: Accelcomp, Тензор, Akvelon, Fogsoft, Confirmit, Krista и многие другие.
У Игоря есть $$$n$$$ друзей, которые тоже хотят устроиться на работу. Собравшись всей своей дружной компанией, ребята выбрали $$$n+1$$$ IT-компанию из своего родного города.
Игорь и его друзья хотят устроиться в разные компании, чтобы после испытательного срока поделиться впечатлением от работы в IT. Каждый друг Игоря, как и сам Игорь, высказали, хотят ли они работать в определенной компании. Сможете ли вы посчитать сколькими разными способами они смогут устроиться на работу?
В первой строке записано $$$n$$$ $$$(1\leq n \lt 10)$$$ — количество друзей Игоря.
Следующие $$$n+1$$$ строк описывают предпочтения Игоря и его друзей. В строке с номером $$$i$$$ содержится $$$n + 1$$$ число $$$k_{ij}$$$ $$$(1\leq i,\;j \leq n + 1)$$$. Если $$$k_{ij}= 0$$$, то человек с номером $$$i$$$ не хочет работать в компании с номером $$$j$$$, если же $$$k_{ij} = 1$$$, то человек $$$i$$$ хочет работать в компании $$$j$$$.
В единственной строке выведите количество вариантов трудоустройства студентов с учетом их пожеланий.
2 1 1 1 1 1 1 1 1 1
6
2 1 1 0 0 1 1 0 0 1
1
2 1 1 0 0 1 0 1 0 0
0
Игорь подал документы в аспирантуру своего любимого ВУЗа и решил немного прогуляться в парке.
В парке растут $$$n$$$ очень красивых деревьев, имеющих идеальную форму. Поскольку листовая крона деревьев очень густая, она не пропускает капли дождя. А сами листья при этом создают тень в виде круга, в центре которого расположен ствол дерева.
Гуляя по парку, Игорь, как истинный математик, решил записать в свой блокнот информацию о деревьях в виде координат центра и радиуса тени дерева. За начало координат Игорь решил взять один из углов прямоугольной автобусной остановки, а координатные оси расположил параллельно ее сторонам. Когда все данные уже были записаны в блокнот, а Игорь шел в сторону остановки, начался сильный дождь. Игорь хочет добраться до остановки, пробежав под дождем как можно меньшее расстояние.
Сможете ли вы определить это расстояние?
В первой строке записано два целых числа $$$x_1, y_1$$$ ($$$-10^5\leq x_1, y_1\leq 10^5$$$) — координаты вершины прямоугольной остановки, противоположной вершине, выбранной в качестве начала координат.
Во второй строке задано два целых числа $$$x_2, y_2$$$ ($$$-10^5\leq x_2, y_2\leq 10^5$$$) — координаты Игоря.
В третьей строке записано число $$$n$$$ ($$$1\leq n\leq 10^3$$$) — количество деревьев в парке.
В каждой из последующих $$$n$$$ строк записано по три целых числа $$$a_i$$$ $$$b_i$$$, $$$r_i$$$ ($$$-10^5\leq a_i,\; b_i\leq 10^5$$$, $$$1 \leq r_i \leq 10^5$$$) — координаты и радиус кроны $$$i$$$-го дерева.
Выведите одно вещественное число с точностью до 4 знаков после запятой — минимальное расстояние, которое Игорю придется пройти под дождем.
2 2 10 10 2 8 8 1 5 5 2
5.31370850
2 2 10 10 4 8 10 2 4 10 2 4 6 2 4 2 2
0.00000000
2 2 10 10 2 8 8 1 6 6 2
5.48528137
Гарантируется, что
- не существует двух деревьев, стволы которых расположены в одной точке;
- не существует дерева, расположенного внутри остановки;
- Игорь находится вне остановки.